6.6 The Euclidean Algorithm 99(c) Use (a) to give a new proof of Lemma 6.5.2.6.5.3Imagine numbers written in basea, with at mostpdigits. Put two num-
bers in the same box if they arise by a cyclic shift from each other. How many
will be in each class? Give a new proof of Fermat’s Theorem this way.
6.5.4Give a third proof of Fermat’s “Little” Theorem based on Exercise 6.3.5.
[Hint: Consider the producta(2a)(3a)···((p−1)a).]6.6 The Euclidean Algorithm
So far, we have discussed several notions and results concerning integers.
Now we turn our attention to the question of how to do computations in
connection with these results. How do we decide whether or not a given
number is a prime? How do we find the prime factorization of a number?
We can do basic arithmetic—addition, subtraction, multiplication, divi-
sion with remainder—efficiently, and we will not discuss this here.
The key to a more advanced algorithmic number theory is an algorithm
that computes thegreatest common divisorof two positive integersaand
b. This is defined as the largest positive integer that is a divisor of both
aandb. (Since 1 is always a common divisor, and no common divisor is
larger than either integer, this definition makes sense: There is always at
least one common divisor, and in the set of common divisors there must be
a greatest element.) The greatest common divisor ofaandbis denoted by
gcd(a, b). Thus
gcd(1,6) = 1, gcd(2,6) = 2, gcd(3,6) = 3,gcd(4,6) = 2, gcd(5,6) = 1, gcd(6,6) = 6.We say that two integers arerelatively primeif their greatest common
divisor is 1. It will be convenient to define gcd(a,0) =afor everya≥0.
A somewhat similar notion is theleast common multipleof two integers,
which is the least positive integer that is a multiple of both integers. It is
denoted by lcm(a, b). For example,
lcm(1,6) = 6, lcm(2,6) = 6, lcm(3,6) = 6,lcm(4,6) = 12, lcm(5,6) = 30, lcm(6,6) = 6.The greatest common divisor of two positive integers can be found quite
simply by using their prime factorizations: Look at the common prime
factors, raise each to the smaller of the two exponents, and take the product
of these prime powers. For example, 900 = 2^2 · 32 · 52 and 54 = 2· 33 , and
hence gcd(900,54) = 2· 32 = 18.