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.

Write a comment

0