GCD (Greatest Common Divisor) of 2 positive numbers is defined to be the highest common divisor between a and b.
This is the highest number that divides both the numbers a and b. This is also known as HCF(Highest Common Factor).
Properties
First we define some of the properties of common divisor
if x is common divisor between a and b then x divides a and b that is
a = mx
b = px
from the above it is clear that (a-b) = x(m-p). so if x divides a and b then x divides a-b
so GCD(a,b) can be computed by finding GCD(a-b,b) when $a > b$
if a = b then the highest number that devide a,b is a
so GCD(a,a) = a
we further define GCD between a number a and zeo to be a that is
GCD(a,0) = a
Computation
so to compute GCD of a b we can keep subtracting b from a till we reach a or $< a$. If we reach a
then we decide a as gcd and stop. if we find less than a we intechange a and b and proceed.
The above method must stop as the larger number becomes smaller in each step.
for example for GCD of 1001 and 104
GCD (1001,104)
= GCD(1001-104,104) =GCD(897,104)
= GCD(897-104,104) = GCD(793,104)
= GCD(793-104,104) = GCD(689,104)
= GCD(689-104,104) = GCD(585,104)
= GCD(585-104,104) = GCD(481,104)
= GCD(481-104,104) = GCD(377,104)
= GCD(377-104,104) = GCD(273,104)
= GCD(273-104,104) = GCD(169,104)
= GCD(169-104,104) = GCD(65,104)
= GCD(104,65) = GCD(104-65,65)
= GCD(39,65) = GCD(65,39)
= GCD(65-39,39) = GCD(26,39)
= GCD(39,26) = GCD(39-26,26)
= GCD(13,26)
= GCD(26,13)
= GCD(26-13,13) = GCD(13,13) = 13
so we see that 13 is the GCD.
However this approach is very slow and takes a lot of steps.
Further reducing a by b may times does not serve any purpose and we can reduce a by a multiple of b
We are interested in the remainder when a is divided by b. The remainder is between 0 to b-1 both
inclusive.
For example, 17 mod 3 = 2 as 17 = 3 * 5 + 2
using the remainder method we have
1001 = 104*9 + 65
104 = 65*1 + 39
65 = 39*1 + 26
39 = 26*1 + 13
26 = 13*2 + 0
When the last remainder is zero the previous remainder is the GCD.
As we see that the GCD computation is much faster going in this way rather than repeated subtraction.
The above method was developed by Euclid and is called Euclidean Algorithm.
Now we define properties
if GCD(a,b) =1 then a and b are called co-primes. a and b need not be prime themselves. for example
GCD(6,35) = 1 so 6 and 35 are coprimes but neither 6 not 35 is a prime.
If a and b are non-zero integers and d is the greatest common divisor then there exists integers
x and y such that
ax+by = d
In addition the smallest positive integer that can be expressed as ax+by is the greatest common divisor of a and b
Every integer of the form ax +by is multiple of the greatest common divisor.
The above is called Bezout's identiy also known as Bezout Theorem
We mention this (at cost of duplicating) below formally along with the proof
For every pair of integers a and b there exists integers m and n such that
GCD(a,b) = am + bn
Proof:
This can be proved by a couple of methods
method 1)
By working through Euclidean algorihm we see that next a,b are of the form am + bn of the
starting a,b and hence each $a_n, b_n$ and hence the last a and hence the GCD(a,b).
Method 2)
However this can be proved using pigeon hole principle also as below.
We know that au is divisible by Gcd(a,b) so au mod b is divisible by Gcd(a,b)
Let gcd(a,b ) = k and
$\frac{b}{gcd(a,b)} = t$
Now taking an mod b( n from 1 to $\frac{b}{gcd(a,b)-1} that is t -1 ) there are t-1 remainders
they are $kn_1, kn_2, kn_3$ so on
there are t-1 remainders and all are divisible by k
no remainder can be zero
because na (n from 1 to t-1) cannot be a product of b.
no 2 remainder can be same if they are then difference is a multiple of b
so there has to a n such that one of the remainder is k
as all t- 1 remainders has to be different and values from 1 to n-1 so one remainder has to be 1
an = k mod b or an + bm = k
