Structure and Interpretation of Computer Programs

43

 This theorem was proved in 1845 by Gabriel Lamé, a French mathematician and engineer known

chiefly for his contributions to mathematical physics. To prove the theorem, we consider pairs (a

k

 

,b

k

), where a

k

> b

k

, for which Euclid’s Algorithm terminates in k steps. The proof is based on the

claim that, if (a

k+1

, b

k+1

)   (a

k

, b

k

)   (a

k-1

, b

k-1

) are three successive pairs in the reduction

process, then we must have b

k+1

> b

k

 + b

k-1

. To verify the claim, consider that a reduction step is

defined by applying the transformation a

k-1

 = b

k

, b

k-1

 = remainder of a

k

 divided by b

k

. The second

equation means that a

k

 = qb

k

 + b

k-1

 for some positive integer q. And since q must be at least 1 we

have a

k

 = qb

k

 + b

k-1

 > b

k

 + b

k-1

. But in the previous reduction step we have b

k+1

 = a

k

. Therefore, 

b

k+1

 = a

k

> b

k

 + b

k-1

. This verifies the claim. Now we can prove the theorem by induction on k, the

number of steps that the algorithm requires to terminate. The result is true for k = 1, since this merely

requires that b be at least as large as Fib(1) = 1. Now, assume that the result is true for all integers less

than or equal to k and establish the result for k + 1. Let (a

k+1

, b

k+1

)   (a

k

, b

k

)   (a

k-1

, b

k-1

) be

successive pairs in the reduction process. By our induction hypotheses, we have b

k-1

> Fib(k - 1) and 

b

k

> Fib(k). Thus, applying the claim we just proved together with the definition of the Fibonacci

numbers gives b

k+1

 > b

k

 + b

k-1

> Fib(k) + Fib(k - 1) = Fib(k + 1), which completes the proof of

Lamé’s Theorem. 

44

 If d is a divisor of n, then so is n/d. But d and n/d cannot both be greater than   n. 

45

 Pierre de Fermat (1601-1665) is considered to be the founder of modern number theory. He

obtained many important number-theoretic results, but he usually announced just the results, without

providing his proofs. Fermat’s Little Theorem was stated in a letter he wrote in 1640. The first

published proof was given by Euler in 1736 (and an earlier, identical proof was discovered in the

unpublished manuscripts of Leibniz). The most famous of Fermat’s results -- known as Fermat’s Last

Theorem -- was jotted down in 1637 in his copy of the book Arithmetic (by the third-century Greek

mathematician Diophantus) with the remark ‘‘I have discovered a truly remarkable proof, but this

margin is too small to contain it.’’ Finding a proof of Fermat’s Last Theorem became one of the most

famous challenges in number theory. A complete solution was finally given in 1995 by Andrew Wiles

of Princeton University. 

46

 The reduction steps in the cases where the exponent e is greater than 1 are based on the fact that,

for any integers x, y, and m, we can find the remainder of x times y modulo m by computing separately

the remainders of x modulo m and y modulo m, multiplying these, and then taking the remainder of the

result modulo m. For instance, in the case where e is even, we compute the remainder of b

e/2

 modulo 

m, square this, and take the remainder modulo m. This technique is useful because it means we can

perform our computation without ever having to deal with numbers much larger than m. (Compare 

exercise 1.25.) 

47

 Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them

other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The

smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers

chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the

chance that cosmic radiation will cause the computer to make an error in carrying out a ‘‘correct’’

algorithm. Considering an algorithm to be inadequate for the first reason but not for the second

illustrates the difference between mathematics and engineering. 

48

 One of the most striking applications of probabilistic prime testing has been to the field of

cryptography. Although it is now computationally infeasible to factor an arbitrary 200-digit number,

the primality of such a number can be checked in a few seconds with the Fermat test. This fact forms

---