The Euclidean Algorithm

The algorithm finds (a, b) assuming 0 < a < b

Apply the Division Algorithm repeatedly: Suppose that

If rn is the last non-zero remainder in this sequence, then
rn = (0, rn) = (rn, rn-1) = . . . = (r3, r2) = (r1, a) = (a, b).

Example: Apply this method to find (51, 288). 

   288 = 51*5 + 33,
    51 = 33*1 + 18,
    33 = 18*1 + 15,
    18 = 15*1 + 3,
    15 = 3*5.
According to the algorithm, 3 = (288, 51). The same equations can be used to find x and y such that 3 = 288x + 51y. Starting with the last but one equation and eliminating successive remainders, we obtain 
    3 = 18 - 15
      = 18 - (33 - 18)
      = 2*18 - 33
      = 2(51 - 33) - 33
      = 2*51 - 3*33
      = 2*51 - 3(288 - 5*51)
      = 288(-3) + 51*17.
Thus, 3 = 288x + 51y with x = -3 and y = 17.

The Euclidean Algorithm can be formulated in "pseudo-code":

Input a, b with 0 < a < b
Set r = b % a 
(that is, r is the remainder of the division b / a)

while r > 0 do
   Set b = a
   Set a = r
   Set r = b % a
Output a
Note that (a, b) = (-a, b) = (a, -b) = (-a, -b).
Thus, the Euclidean Algorithm can be used to find (a, b) even if one (or both) of the integers is negative.

Relatively prime numbers

Definition 2
If (a, b)=1, then a and b are said to be relatively prime.

Theorem 5
(a, b)=1 if and only if there exists integers x and y such that 1 = ax+by.
Proof. Assume d=(a, b)=1. By Theorem 3, d=ax+by for some x and y.
On the other hand, if 1=ax+by, then (a, b) | 1 and, since (a, b) is a positive integer, it follows that (a, b)=1.

Corollary 2
If d = (a, b) and A and B are defined by the equations a = Ad, b = Bd, then (A, B)=1.
Proof. Since d=(a, b), there exist integers x and y such that d=ax+by. Therefore,

and (A, B)=1 by Theorem 5.

Theorem 6
If a | bc and (a, b)=1, then a | c.
Proof. Since (a, b)=1, there exist integers x and y such that 1=ax+by. Therefore, c=acx+bcy. But a | bc by hypothesis, and so a | (acx+bcy) by Theorem 1(v). Therefore, a | c.

Corollary 3
If p is a prime and p | bc, then p | b or p | c.
Proof. If p | b there is nothing to prove. If p does not divide b, then (p, b)=1 since only positive divisors of p are 1 and p itself. But then p | c by Theorem 6.

Corollary 4
If p is a prime and p | a1a2 . . . an, then p | ai for some i.
The proof can be easily done by induction on n.

Corollary 5
If p, p1, p2, . . . , pn are primes and p | p1p2 . . . pn then p=pi for some i.
Proof. By Corollary 4, p | pi for some i. But p > 1 and the only positive divisors of pi are 1 and pi. Therefore, p=pi.

Theorem 7
If a | c,   b | c, and (a, b)=1, then ab | c.
Proof. Since a | c and b | c, there exist integers r and s such that ar = c = bs. From this it follows that b | ar. But (a, b)=1 and so, by Theorem 6, b | r. Thus, bt=r for some integers t, and c = ar = abt. Therefore, ab | c.