Mathematics for Computer Science

Chapter 8 Number Theory274

However, Turing remained a puzzle to the very end. His mother was a devout

woman who considered suicide a sin. And, other biographers have pointed out,

Turing had previously discussed committing suicide by eating a poisoned apple.

Evidently, Alan Turing, who founded computer science and saved his country, took

his own life in the end, and in just such a way that his mother could believe it was

an accident.

Turing’s last project before he disappeared from public view in 1939 involved the

construction of an elaborate mechanical device to test a mathematical conjecture

called the Riemann Hypothesis. This conjecture first appeared in a sketchy paper by

Bernhard Riemann in 1859 and is now one of the most famous unsolved problems

in mathematics.

8.10 Euler’s Theorem

The RSA cryptosystem examined in the next section, and other current schemes

for encoding secret messages, involve computing remainders of numbers raised to

large powers. A basic fact about remainders of powers follows from a theorem due

to Euler about congruences.

Definition 8.10.1.Forn > 0, define^11

.n/WWDthe number of integers inŒ0::n/, that are relatively prime ton.

This functionis known as Euler’sfunction.^12

For example,.7/D 6 because all 6 positive numbers inŒ0::7/are relatively

prime to the prime number 7. Only 0 is not relatively prime to 7. Also,.12/D 4

since 1, 5, 7, and 11 are the only numbers inŒ0::12/that are relatively prime to 12.

More generally, ifpis prime, then.p/Dp 1 since every positive number in

Œ0::p/is relatively prime top. Whennis composite, however, thefunction gets

a little complicated. We’ll get back to it in the next section.

Euler’s Theorem is traditionally stated in terms of congruence:

Theorem(Euler’s Theorem).Ifnandkare relatively prime, then

k.n/1 .modn/: (8.15)

(^11) Since 0 is not relatively prime to anything,.n/could equivalently be defined using the interval
.0::n/instead ofŒ0::n/.
(^12) Some texts call it Euler’stotient function.