The GCD of a pair of positive integers a and b (denoted here as gcd(a, b)) is simply the largest positive integer that divides both a and b. The Euclidean algorithm is a simple way to compute the GCD. The Euclidean algorithm is based on the observation that for any positive integers a and b there exist integers q and r with 0 ≤ r < b such that
a = b × q + r
Note that r is simply the remainder when you divide a by b. From this it is easy to show that u is a common divisor of a and b if and only if u is a common divisor of b and r. Since the set of common divisors are identical, it follows that the greatest common divisors are also identical, i.e.,
gcd(a, b) = gcd(b, r)
To get the Euclidean algorithm, one simply applies the above result recursively to gcd(b, r) until we get to rn-1 and rn such that gcd(rn-1, rn) = 0. When this happens, we can conclude that gcd(a, b) = rn. (We would, of course, use mathematical induction to prove this formally.)
One important property of gcd(a, b) that can be derived from the above is that there exist positive or negative integers k and l such that
gcd(a, b) = k × a + l × b
Using this, the book presents a simple proof of the fundamental theorem of arithmetic. The proof starts by using the above property to show that if a prime p divides a × b then it divides either a or b. One can then easily show that purportedly different prime factorizations of a number are in fact identical.
Finally, the book introduces Euler's function. Two integers a and b are said to be relatively prime if
gcd(a, b) = 1
Euler's function, usually denoted φ(n), is the number of integers from 1 to n that are relatively prime with n. Note, in particular, φ(1) = 1 and φ(p) = p - 1 when p is prime. The book claims that Euler's function is a number-theoretical function of great importance (though it does not expand on this claim immediately).
One interesting property of Euler's function is the generalization of Fermat's little theorem: if n is any integer and a is relatively prime with n then
aφ(n) ≡ 1 (mod n)
2 comments:
Hi Pandu,
I was given What is Mathematics" in high school, and enjoyed in thoroughly. A note on Euclid's algorithm and the fundamental theorem - Euclid's algorithm is fudamental to the proof, all known proofs will use that or its equivalent. This is because the fundamental theorem is not trivial, and doesnt hold in all rings, for example in the ring a +b*sqrt(5). See http://www.dpmms.cam.ac.uk/~wtg10/meta.fta.html for a nice discussion of this.
Very interesting. (Small typo in your comment: the ring has elements of the form a+b*sqrt(-5).)
Post a Comment