Problem 25: =========== 7469 = 3 * 2387 + 308 2387 = 7 * 308 + 231 308 = 1 * 231 + 77 231 = 3 * 77 Hence gcd(7469,308) = 77 We can write 77 = 308 - 1* 231 = = 308 - 1*(2387 - 7 * 308) = -1 * 2387 + 8 * 308 = = -1 * 2387 + 8 * (7469 - 3 * 2387) = 8 * 7469 - 25 * 2387 which is the requited linear combination Problem 26: =========== Suppose (a,b) = g , then g divides a and b; since g divides b, it also divides bc. Therefore g | (a,bc). This shows that if (a,b) = g > 1, then (a,bc) cannot equal 1, because it is divisible by g>1. A similar conclusion holds if (a,c)>1. We have therefore shown (by contraposition): If (a,bc)=1, then (a,b)=1 and (a,c)=1. Now we must show the converse, namely: If (a,b)=1 and (a,c)=1, then (a,bc)=1. Since (a,b)=1, we can write 1 as a linear combination of a and b with integer coefficients x,y: 1 = xa + yb Similarly, since (a,c)=1, we can write 1 = ua + vc Multiplying the two equnations, we get 1 = (xa + yb)(ua + vc) = (xua+yub+xvc) a + (yv) bc Therefore the gcd (a,bc) must be 1: if it were g>1, then g would divide the linear combination (xua+yub+xvc) a + (yv) bc, which is however 1. Problem 27: =========== The calculation is completely analogous to #25; the only difference being that the division with remainder is carried out in Z[i] differently, namely as explained in #22. 16+2i = q (14+31i) + r (If you start that way, you get q=0 and r=16+2i, which will make the next step of your solution the first step of the solution for those who started with 16+2i and 14+31i in different order, namely: 14+31i = q (16+2i) + r (**) q is obtained by rounding (14+31i)/(16+2i)= (14+31i)*(16-2i)/(16*16+2*2) = (286 + 468i) / 260 = 1.1 + 1.8i So q = 1 + 2i, and we find r from (**): 14+31i = (1+2i)(16+2i) + 2-3i Next step: 16+2i = q (2-3i) + r (with new q and r of course) exact quotient: (16+2i)/(2-3i) = (16+2i)*(2+3i)/(4+9) = (26 + 52i)/13 = 2+4i So we have the exact quotient in the ring Z[i] already, which leaves the remainder 0: 16+2i = (2+4i)(2-3i) Therefore the preceding remainder, namely 2-3i is a gcd of 14+31i and 16+2i. Going back through the algorithm, we can also write it as a linear combination (with coefficients in Z[i] of course): 2-3i = 1 * (14+31i) - (1+2i)*(16+2i)