Euclid Algorithm

This algorithm allows to calculate the GCD of two numbers a and b.
In integer division a = b×q + r, every divider of b and r divides a, and every divider of a and b divides r = a - b×q.
The GCD of a and b is then the GCD of b and r.

For instance 32 = 12×2 + 8, GCD(32,12) = GCD (12,8)
Repeating then :
12 = 8×1 + 4, GCD(12,8) = GCD (8,4)
8 = 4×2 + 0 and that's all, 8 is a multiple of 4, and GCD is 4.
Hence GCD(32,12) = 4.

 a0 = a, b0 = b, a>b>0 then repeat :
    |  an = bn×qn + rn    avec 0≤rn<bn 
    |  an+1 = bn, bn+1 = rn 
 The last non null remainder is the GCD(a,b) 
This algorithm always ends because the sequence of rn strictly decreases.

If we write the remainders as r = a - b×q and calculating backwards, we get :
GCD = 4 = 12 - 8×1
Then replacing the remainder 8 by its value : 8 = 32 - 12×2
4 = 12 - (32 - 12×2)×1 = 12×(1 + 2×1) - 32×1 = 12×3 - 32×1
and finally  GCD(a,b) = a.u + b.v  : that is the Bézout theorem ! with here u = -1 and v = 3.
And also solution of a.u + b.v = p with p = GCD(a,b) as well
And finally the calculation of inverse of a modulo b if GCD(a,b) = 1 : a.u = 1 - b.v ≡ 1 (mod b).

These backwards calculation could as well be done forwards with the extended Euclid algorithm :

 a0 = a, b0 = b, a>b>0
and let P -2 = 0 ,Q -2 = 1 ,P -1 = 1 ,Q -1 = 0 by convention 
Then repeat from i = 0 :
    |  ai = bi×qi + ri    avec 0≤ri<bi
    |  Pi = qiPi-1 + Pi-2
    |  Qi = qiQi-1 + Qi-2
    |  ai+1 = bi, bi+1 = ri
 Last non null remainder rn is GCD(a,b)
 (-1)n.a.Qn + (-1)n+1.b.Pn = rn

By definition : a/b = a0/b0 = q0 + r0/b0 = q0 + 1/(q1 + r1/b1) = q0 + 1/(q1 + 1/(q2 + r2/b2)) = ...
We recognize here the continued fraction of a/b. Last term is rn/bn = 1/(qn+1 + 0)
The Pi / Qi are the convergent of the continued fraction :
P0 = q0, Q0 = 1 then P1 = q1q0 + 1, Q1 = q1, And recursively : Pi / Qi = q0 + 1/(q1 + 1/(... + 1/qi))
Specifically the last convergent : Pn+1 / Qn+1 = a/b

Relations with Pi, Qi can be written as matrix equations :

(Pi    Qi  ) = (qi  1) × (Pi-1  Qi-1)
(Pi-1  Qi-1)   (1   0)   (Pi-2  Qi-2)
Calculating the discriminant shows that quantity PiQi-1 - Pi-1Qi is constant, apart the sign. As P -1Q -2 - P -2Q -1 = 1 :
 PiQi-1 - Pi-1Qi = (-1)i-1  (loop invariant)
This relation proves (Bézout theorem) that GCD(Pi, Qi) = 1
Pn+1 / Qn+1 = a/b = (a/p) / (b/p) with p = GCD(a,b).
Let Pn+1 = a/p and Qn+1 = b/p
Then : Pn+1Qn - PnQn+1 = (-1)n results into Qna/p - Pnb/p = (-1)n
That is :  (-1)n.Qna/p + (-1)n+1.Pnb/p = 1  QED.

Note : We can directly get the (-1)n with a modified algorithm :

 a0 = a, b0 = b, a>b>0
and P -2 = 0 ,Q -2 = 1 ,P -1 = 1 ,Q -1 = 0 
Then repeat from i = 0 :
    |  ai = bi×qi + ri    avec 0≤ri<bi
    |  Pi = -qiPi-1 + Pi-2
    |  Qi = -qiQi-1 + Qi-2
    |  ai+1 = bi, bi+1 = ri
 The last non null remainder rn is GCD(a,b)
 a.Qn + b.Pn = rn
The condition a>b can even be discarded, the 1st division gives if a<b :
a = 0×b + a and the next step is OK, dividing b by a.
The condition on signs could also be discarded if the signed division used satisfies :
a = b.q + r, 0≤|r|<|b|, with a,b,q,r Z instead of N. But speak of GCD(-3,2) = -1 seems strange !

A script for calculating GCD and solving ax + by = c.
Note : once the GCD is known, the LCM is  a×b / GCD(a,b) .

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Française Previous topic Next topic