- MODERN NUMBER THEORY 189
with an odd number of sides will be those whose number of sides is a product of
distinct numbers from the following short list: 3, 5, 17, 257, 65,537.^2
Fermat's last theorem: the cases ç = 4 and ç = 3. We pointed out above that
Fermat's method of infinite descent can be used to prove Fermat's last theorem
for ç = 4, as shown by Euler in 1738. In a textbook of algebra published in 1770
(see Struik, 1986, pp. 36-40), Euler also gave a proof of the impossibility for the
case ç = 3, which is much more difficult. In 1772 Euler proved that every positive
integer is the sum of at most four square integers and conjectured that no sum
of fewer than ç nth powers could be an nth power, a conjecture that was finally
refuted for ç — 5 in 1966.^3
Fermat's little theorem.. A second assertion of Fermat, which Euler proved in 1736
(see Struik, 1986, p. 35), is known as Fermat's little theorem. It asserts that if ñ is a
prime number that does not divide a number a, then ñ does divide ad - 1 for some
positive integer d; moreover, the smallest d for which this statement is true divides
ñ — 1. In particular, ñ divides áñ_1 - 1. Fermat's discovery of this theorem has
an interesting history (Fletcher, 1989). Through Mersenne Fermat had received a
challenge in 1640 from Bernard Frenicle de Bessy (ca. 1612-1675) to find the first
perfect number having at least 20 digits. It was known that 2^30 (2^31 - 1) was a
perfect number having 19 digits.^4 Fermat did not succed in doing this; but after
studying the problem, he noted that if ç is composite, then 2" — 1 is also and
that if ç is a prime, then 2" — 2 is divisible by 2n, that is, ç divides 2n_1 — 1.
Moreover, he said, all other prime divisors of 2" — 2 leave a remainder of 1 when
divided by 2n. These theorems, in Fermat's view, were the secret of discovering
perfect numbers, and he asserted that there were none having 20 or 21 digits. In a
letter to Frenicle in October 1640, Fermat stated his "little" theorem—so called to
distinguish it from his greater, "last" theorem. It is by no means a "little" result.
Euler extended this result and showed that m divides a(a*(m' — 1), where
the number of positive integers less than m and relatively prime to m (now called
Euler's ö-function). That function provides the theoretical basis for constructing
the RSA^5 codes that are an essential part of communications security. Thus, the
completely "useless" topic of perfect numbers actually inspired a number-theoretic
result of great practical value.
Residues modulo a prime. Euler defined an integer ç to be a ë-power residue with
respect to ("modulo," as we now say, using Euler's Latin term) a prime ñ if there
is an integer a such that ñ divides áë — ç. This concept has proved to be a rich
source of investigation in number theory. In particular, the case ë = 2 (quadratic
residues) has led to some deep theorems. In works published in 1751 and 1783,
(^2) Heinrich Wefelscheid informs me that one Johann Hermes (1846-1912), a student in Konigsberg
from 1866 to 1870, actually attempted to work out the case 65,537 and published his method
in the Gottinger Nachrichten in 1894. The Australian mathematician Joan Taylor has used a
computer to complete Hermes' project and found that the algebraic expression for cos(2w/65537)
occupies 12.5 megabytes and contains an integer of 19,717 digits.
(^3) In connection with this result, we note that Fermat had stated a positive conjecture: Every
positive integer is the sum of at most ç n-gonal numbers, that is, three triangular numbers, four
squares, five pentagonal numbers, and so on. This result was first proved for the general case by
Augustin-Louis Cauchy (1789-1856) in 1813.
(^4) Specifically, it is 2,305,843,008,139,952,128.
(^5) Invented in 1977 and named from the initials of its three inventors, Ronald L. Rivest, Adi
Shamir, and Leonard Adleman.