1.10. DIVISION 23

Now d divides n and m so there are numbers k, l such that dk = m, dl = n. From the aboveequation,

r = n− qm = dl − qdk = d (l − qk)

Thus d divides both m and r. If k divides both m and r, then from the equation of 1.1 itfollows k also divides n. Therefore, k divides d by the definition of the greatest commondivisor. Thus d is the greatest common divisor of m and r but m+ r < m+ n. This yieldsanother pair of positive integers for which d is still the greatest common divisor but thesum of these integers is strictly smaller than the sum of the first two. Now you can do thesame thing to these integers. Eventually the process must end because the sum gets strictlysmaller each time it is done. It ends when there are not two positive integers produced.That is, one is a multiple of the other. At this point, the greatest common divisor is thesmaller of the two numbers.

Procedure 1.10.4 To find the greatest common divisor of m,n where 0 < m < n, replacethe pair {m,n} with {m, r} where n = qm + r for r < m. This new pair of numbers hasthe same greatest common divisor. Do the process to this pair and continue doing this tillyou obtain a pair of numbers where one is a multiple of the other. Then the smaller is thesought for greatest common divisor.

Example 1.10.5 Find the greatest common divisor of 165 and 385.

Use the Euclidean algorithm to write

385 = 2 (165) + 55

Thus the next two numbers are 55 and 165. Then

165 = 3× 55

and so the greatest common divisor of the first two numbers is 55.

Example 1.10.6 Find the greatest common divisor of 1237 and 4322.

Use the Euclidean algorithm

4322 = 3 (1237) + 611

Now the two new numbers are 1237,611. Then

1237 = 2 (611) + 15

The two new numbers are 15,611. Then

611 = 40 (15) + 11

The two new numbers are 15,11. Then

15 = 1 (11) + 4

The two new numbers are 11,42 (4) + 3

The two new numbers are 4, 3. Then

4 = 1 (3) + 1