Section 2.4 Number Theory
143
26. To find gcd(420, 66) using the binary GCD algorithm takes the following steps (compare with Example 27).
You can do these steps in your head!
420
66
Fact 1
Save the 2 factor to multiply at the end
210
33
Fact 2
105
33
Fact 3
36
33
Fact 2
18
33
Fact 2
9
33
Fact 3
[Because gcd(a, b) = gcd(b, a), it doesn’t matter whether the
larger number is first or second or whether the even number is
first or second.]
9
12
Fact 2
9
6
Fact 2
9
3
Fact 3
3
3
Fact 3
0
3
One number is now 0, so the other number is a factor in the gcd, therefore gcd(420, 66) = 2*3 = 6 (the
factor of 2 comes from the very first step).
Use the binary GCD algorithm to find gcd(24, 20).
27. Use the binary GCD algorithm to find gcd(308, 165) [see Exercise 7].
28. Use the binary GCD algorithm to find gcd(2420, 70) [see Exercise 8].
S e c t i o n 2 . 4 nuMber Theory
In Section 2.1 we proved several elementary number theory results, such as “The
product of two even integers is even.” These proofs relied on basic definitions and
the standard proof techniques (direct proof, proof by contraposition, and proof by
contradiction). Now that we have some additional ammunition, we can prove more
number theory results. Number theory is fun because conjectures can be stated
easily—after all, only integers are involved—yet sometimes it can be quite difficult to prove. As an extreme case, Fermat’s last theorem states that there are no
positive integers x, y, and z for which
x
n
+ y
n
= z
n
for any integer n > 2. (There are solutions for n = 2, such as 3
2
+ 4
2
= 5
2
.) Pierre
de Fermat stated this result around 1637 but—although many false “proofs” were
published in the interim—it took until 1995 before a proof was found, using very
complicated mathematics, by Dr. Andrew Wiles of Princeton University. We are
interested in number theory, however, because of its usefulness in computer security (see Section 5.6).