Euclidean algorithm

The GCD of A and B in Z is the GCD of B and R.

 

Here R is the remainder of A and we have the relationship

A = BQ + R (*)

(Q is the quotient of A, A>B>R>0).

 

The GCD of A and B is denoted as (A,B),

then Euclidean algorithm is represented as (A,B)=(B,R)

 

Let (A,B)  = g.

Then we have

A = ga (1),

B = gb (2),

(a,b)=1 (3).

 

Substituting (1) and (2) into (*), we get

A = BQ + R  

⇔  

R = A - BQ

    = ga - gbQ

    = g(a-bQ).

 

Here, if (b,a-bQ) = 1, then we can conclude (B,R) = g.

 

Let (b,a-bQ) =d ≠ 1. Then we have

b = db',

a-bQ = dr',

(b',r') = 1.

 

Therefore

B = gb = gdb', 

R = gdr'. 

 

Therefore

A = BQ + R  

   = gdb'Q + gdr'

   = gd(b'Q+r')

 

Therefore

A and B have the common divisor gd, which is contradictory to (A,B) = g.

 

Therefore

we obtain (b,a-bQ) = 1, or (B,R) = g.

 

 

Thus (A,B) = (B,R).

 

Q.E.D.