- Answers to Exercises 267
product above has the same remainder when divided bypas the product
r 1 r 2 ···rp− 1. But this product is just (p−1)!. Hencepis a divisor of (p−
1)!ap−^1 −(p−1)!=(p−1)!(ap−^1 −1). Sincepis a prime, it is not a divisor
of (p−1)!, and so it is a divisor ofap−^1 −1.
6.6 The Euclidean Algorithm
6.6.1. gcd(a, b)≤a, butais a common divisor, so gcd(a, b)=a.
6.6.2. (a) Letd= gcd(a, b). Thend|aandd|b, and henced|b−a.Thus
dis a common divisor ofaandb−a, and henced≤gcd(a, b). A similar
argument shows the reverse inequality. (b) By repeated application of (a).
6.6.3. (a) gcd(a/ 2 ,b)|(a/2) and hence gcd(a/ 2 ,b)|a. So gcd(a/ 2 ,b)
is a common divisor ofaandb, and hence gcd(a/ 2 ,b)≤gcd(a, b). The
reverse inequality follows similarly, using that gcd(a, b) is odd, and hence
gcd(a, b)|(a/2).
(b) gcd(a/ 2 ,b/2) | (a/2) and hence 2gcd(a/ 2 ,b/2) | a. Similarly, we
have 2gcd(a/ 2 ,b/2)|b, and hence 2gcd(a/ 2 ,b/2)≤gcd(a, b). Conversely,
gcd(a, b)|aand hence^12 gcd(a, b)|a/2. Similarly,^12 gcd(a, b)|b/2, and
hence^12 gcd(a, b)≤gcd(a/ 2 ,b/2).
6.6.4. Consider each prime that occurs in either one of them, raise it to
the larger of the two exponents, and multiply these prime powers.
6.6.5.Ifaandbare the two integers, and you know the prime factorization
ofa, then take a prime factor ofa, dividebby this prime repeatedly to
determine its exponent in the prime factorization ofb, and raise this prime
to the smaller of its exponent in the prime factorizations ofaandb. Repeat
this for all prime factors ofa, and multiply these prime powers.
6.6.6. By the descriptions of the gcd and lcm above, each prime occurs
the same number of times in the prime factorization of both sides.
6.6.7. (a) Straightforward. (b) Letz= gcd(a, b, c), and letA =a/z,
B=b/z,C=c/z. ThenA,B, andCare relatively prime and form a
Pythagorean triple. One ofAandBmust be odd, since if both of them
were even, thenCwould be even as well, and so the three numbers would
not be relatively prime. Suppose thatBis odd. ThenAmust be even.
Indeed, the square of an odd number gives a remainder of 1 when divided
by 4, so if bothAandBwere odd, thenC^2 =A^2 +B^2 would give a
remainder of 2 when divided by 4, which is impossible. It follows thatC
must be odd.
SoAis even, and we can write it in the formA=2A 0. Write the equation
in the form
A^20 =