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.
a_{0} = a, b_{0} = b, a>b>0 then repeat :
| a_{n} = b_{n}×q_{n} + r_{n} avec 0≤r_{n}<b_{n} | a_{n+1} = b_{n}, b_{n+1} = r_{n} The last non null remainder is the GCD(a,b) |
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 :
a_{0} = a, b_{0} = 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 : | a_{i} = b_{i}×q_{i} + r_{i} avec 0≤r_{i}<b_{i} | P_{i} = q_{i}P_{i-1} + P_{i-2} | Q_{i} = q_{i}Q_{i-1} + Q_{i-2} | a_{i+1} = b_{i}, b_{i+1} = r_{i} Last non null remainder r_{n} is GCD(a,b) (-1)^{n}.a.Q_{n} + (-1)^{n+1}.b.P_{n} = r_{n} |
By definition : a/b = a_{0}/b_{0} = q_{0} + r_{0}/b_{0} =
q_{0} + 1/(q_{1} + r_{1}/b_{1}) =
q_{0} + 1/(q_{1} + 1/(q_{2} + r_{2}/b_{2})) = ...
We recognize here the continued fraction of a/b.
Last term is r_{n}/b_{n} = 1/(q_{n+1} + 0)
The P_{i} / Q_{i} are the convergent of the continued fraction :
P_{0} = q_{0}, Q_{0} = 1 then
P_{1} = q_{1}q_{0} + 1, Q_{1} = q_{1},
And recursively : P_{i} / Q_{i} = q_{0} + 1/(q_{1} + 1/(... + 1/q_{i}))
Specifically the last convergent : P_{n+1} / Q_{n+1} = a/b
Relations with P_{i}, Q_{i} can be written as matrix equations :
(P_{i } Q_{i }) = (q_{i} 1) × (P_{i-1} Q_{i-1}) (P_{i-1} Q_{i-1}) (1 0) (P_{i-2} Q_{i-2})Calculating the discriminant shows that quantity P_{i}Q_{i-1} - P_{i-1}Q_{i} is constant, apart the sign. As P_{ -1}Q_{ -2} - P_{ -2}Q_{ -1} = 1 :
Note : We can directly get the (-1)^{n} with a modified algorithm :
a_{0} = a, b_{0} = b, a>b>0
and P_{ -2} = 0 ,Q_{ -2} = 1 ,P_{ -1} = 1 ,Q_{ -1} = 0 Then repeat from i = 0 : | a_{i} = b_{i}×q_{i} + r_{i} avec 0≤r_{i}<b_{i} | P_{i} = -q_{i}P_{i-1} + P_{i-2} | Q_{i} = -q_{i}Q_{i-1} + Q_{i-2} | a_{i+1} = b_{i}, b_{i+1} = r_{i} The last non null remainder r_{n} is GCD(a,b) a.Q_{n} + b.P_{n} = r_{n} |
A script for calculating GCD and solving ax + by = c.
Note : once the GCD is known, the LCM is a×b / GCD(a,b) .