268 16. Answers to Exercises
Letpbe any prime number dividingA 0. Thenpmust divide either (C+
B)/2or(C−B)/2. Butpcannot divide both, since then it would also
divide the sumC+ 2 B+C− 2 B=Cas well as the differenceC+ 2 B−C− 2 B=B,
contradicting the assumption thatA,B, andCare relatively prime.
The primepmay occur in the prime decomposition ofA 0 several times,
sayktimes. Then in the prime decomposition ofA^20 ,poccurs 2ktimes. By
the argument above,pmust occur 2ktimes in the prime decomposition of
one of (C+B)/2 and (C−B)/2, and not at all in the prime decomposition
of the other. So we see that in the prime decomposition of (C+B)/2 (and
similarly in the prime decomposition of (C−B)/2), every prime occurs
to an even power. This is the same as saying that both (C+B)/2 and
(C−B)/2 are squares; say, (C+B)/2=x^2 and (C−B)/2=y^2 for some
integersxandy.
Now we can expressA,B, andCin terms ofxandy:
B=C+B
2
−
C−B
2
=x^2 −y^2 ,C=C+B
2
+
C−B
2
=x^2 +y^2 ,A=2A 0 =2
√
C+B
2
C−B
2
=2xy.We geta,b, andcby multiplyingA,B, andCbyz, which completes the
solution.
6.6.8. gcd(a, a+ 1) = gcd(a,1) = gcd(0,1) = 1.
6.6.9. The remainder of Fn+1 divided by Fn is Fn− 1. Hence
gcd(Fn+1,Fn) = gcd(Fn,Fn− 1 )=···= gcd(F 3 ,F 2 ) = 1. This lastsn− 1
steps.
6.6.10. By induction onk. True ifk= 1. Suppose thatk>1. Let
b=aq+r,1≤r<a. Then the Euclidean Algorithm for computing
gcd(a, r) lastsk−1 steps; hencea≥Fkandr≥Fk− 1 by the induction
hypothesis. But thenb=aq+r≥a+r≥Fk+Fk− 1 =Fk+1.
6.6.11. (a) Takes 10 steps. (b) Follows from gcd(a, b) = gcd(a−b, b). (c)
gcd
(
10100 − 1 , 10100 − 2
)
takes 10^100 −1 steps.6.6.12. (a) Takes 8 steps. (b) At least one of the numbers remains odd
all the time. (c) Follows from Exercises 6.6.2 and 6.6.3. (d) The product of
the two numbers drops by a factor of two in one of any two iterations.
6.7 Congruences
6.7.1. m= 54321−12345 = 41976.
6.7.2. Only (b) is correct.
6.7.3. a≡b (mod 0) should mean that there exists an integerksuch
thata−b=0·k. This means thata−b= 0, that is,a=b. So equality
can be considered as a special case of congruence.