2.2 The Euclidean Algorithm
Definition: Let a,b,d If d|a and d|b, we say d is a common divider of a and b.
Definition2: Let a, b , not both 0. If d is the largest positive integer dividing both a and b, we say d is
the greatest common divider of a and b, denoted by d=gcd(a,b).
Ex: The common dividers of 45 and 75 are
± 1, ± 3, ± 5 and ± 15.
Thus, gcd(45,75) = 15
Ex2: Claim gcd(3.0) = 3
- Dividers of 3 are ± 1, ± 3
- All integers are dividers of 0, (since 0=0 x a,
Thus their common dividers are ± 1, ±3, and gcd(3,0)=3
We also have gcd(-3,0)=3
In general, for with a≠0, gcd(a,0) = a|
To keep the above, we define gcd(0,0)=0, although 0 is NOT the largest common divider of 0 and 0.
Ex: Prove that gcd(a,b) = gcd(5a+4b, a+b)
If a=b=0, then gcd(a,b) = 0 = gcd(5a+4b, a+b). Thus we can assume now that a,b are not both 0.
Let d = gcd(5a+4b, a+b).
Since d|(5a+4b) and d|(a+b), by Prop2.1 (ii)
d|(5a+4b) – 4(a+b), i.e. d|a
Since d|(a+b) and d|a, by Prop2.11 (ii)
d|(a+b) – a, i.e. d|b
Thus d is a common dividor of a and b.
Let e be any common divider of a and b. Since e|a and e|b, by Prop2.11 (ii)
e|(5a+4b) and e|(a+b)
Since e|(5a+4b), e|(a+b) and d = gcd(5a+4b, a+b), we have e ≤ d.
Since d|a, d|b and d ≥ e for any common divider, e of a and b, we have d = gcd(a,b).
Thus, gcd(a,b) = gcd(5a+4b, a+b) Proposition 2.21
If a=qb+r, then gcd(a,b) = gcd(b,r)