From Mathematics to Generic Programming (2015)

5. The Emergence of Modern Number Theory

Mathematicians have tried in vain to this day
to discover some order in the sequence of prime numbers,
and we have reason to believe that it is a mystery
into which the human mind will never penetrate.
Leonhard Euler

In the previous chapter, we saw how the fledging field of number theory, which had fascinated the ancient Greeks, was revived in medieval Europe after a long period of dormancy. But number theory in its modern sense really emerged a few hundred years later, in 17th-century France. For this chapter, we are going to put programming aside for a bit and learn some of the results discovered by 17th-century French mathematicians, which we’ll use for some important computer applications later on.

5.1 Mersenne Primes and Fermat Primes

Mathematicians of the Renaissance rekindled the ancient Greeks’ fascination with prime numbers. They wondered whether there were certain predictable patterns of primes. They were particularly interested in primes of the form 2ⁿ -1, since (as we saw in Section 3.4) this was the source of perfect numbers. Mathematicians from the 15th to the 18th centuries, like the Greeks before them, felt that these numbers had special importance. Letters of the 17th-century mathematicians Fermat, Mersenne, and Descartes contain many references to perfect numbers, as well as a closely related concept, amicable numbers. In the 18th century, the great mathematician Leonhard Euler still found the subject to be of primary importance.

As we saw in Chapter 3, the Greeks knew that they could generate perfect numbers from primes of the form 2ⁿ - 1. They knew that numbers of that form are prime for n = 2, 3, 5, and 7, and possibly 13. In 1536, Hudalricus Regius showed that the expression was nonprime for n = 11, by finding

2¹¹ - 1 = 2047 = 23 x 89

Pietro Cataldi added several more values of n to the list in 1603—17, 19, (23), (29), 31, and (37)—but half of these (shown in parentheses) were incorrect. Pierre de Fermat discovered that

In his 1644 book Cogitata Physico Mathematica, the French mathematician Mersenne states that for n ≤ 257, 2ⁿ - 1 is prime if and only if

n = 2, 3, 5, 7, 13, 17, 19, 31, (67), 117, (257)

Two of these were wrong (shown in parentheses), and he missed 89 and 107. Because of Mersenne’s conjecture, primes of this form became known as Mersenne primes. We still do not know whether there is an infinite number of them, but even today Mersenne numbers are still used to search for large primes.

Marin Mersenne (1588–1648)

Starting around 1624, when Cardinal Richelieu became chief minister, France began to rise as a military, political, cultural, and scientific power. While scholars at traditional universities still interpreted Aristotle’s ancient works, philosophers like Descartes in France, working outside of the university system, were revolutionizing the way people thought about the world. Richelieu created the first modern state, with a carefully organized central bureaucracy and military, and even official control of the French language. By 1660, France had become the undisputed leader of Europe, and French became the dominant language for diplomats and aristocrats in most Western countries for the next 250 years.

It was during this period that Marin Mersenne, a French polymath and a member of the strict religious order of Minims, had an enormous impact on science. Although educated by the intellectual Jesuits and an accomplished classical scholar and mathematician, Mersenne chose the extreme asceticism of the Minims, who held no property (even in common), ate a strict vegan diet, and drank no alcohol. Mersenne’s humility extended to his professional life; while other scientists proclaimed their own importance, his cause was to help others disseminate their work and learn about each other’s results. Mersenne did some important work on the theory of sound and other areas, but his greatest contribution was the creation of a shared scientific community.

Scientific journals did not yet exist, but Mersenne served as a “virtual scientific journal,” by exchanging letters with friends and informing them of each other’s results. Mersenne’s friends included people like Galileo, Huygens, Torricelli, Descartes, Fermat, and Pascal. In fact, Mersenne arranged for publication of Galileo’s work in Protestant Holland, despite Galileo’s condemnation by the Catholic Church. Later in Mersenne’s life, scholars would meet together in his cell in a kind of informal weekly conference. When his letters were published after his death, they were in essence the world’s first scientific proceedings.

In a letter to Mersenne in June 1640, Fermat wrote that his factorization of 2³⁷ - 1 depends on the following three discoveries:

1. If n is not a prime, 2ⁿ - 1 is not a prime.

2. If n is a prime, 2ⁿ - 2 is a multiple of 2n.

3. If n is a prime, and p is a prime divisor of 2ⁿ - 1, then p - 1 is a multiple of n.

We’ll look at the proof of discovery 1 in a bit, but for now let’s assume that all three statements are true.

Fermat reasoned that if 2³⁷ - 1 is not prime, it must have a prime factor p, which must be odd. By observation 3, p-1 is a multiple of 37, which is equivalent to saying that

p = 37u + 1

Also, since p is odd, p - 1 = 37u must be even, so u must be even. That means we can express u as 2v, which gives us:

p = 74v + 1

Fermat therefore narrowed the factoring task from trying all possible numbers to just those primes produced by this formula. Testing these in sequence:

What about v = 1? No, 75 is not a prime.

What about v = 2? No, 149 is prime, but is not a divisor of 2³⁷ - 1.

What about v = 3? Yes! 223 is prime, and is a divisor of 2³⁷ - 1.

So 2³⁷ - 1 is not prime.

* * *

Now let’s look at Fermat’s proof of discovery 1, which we state in its contrapositive¹ form.

¹ Any implication p q is logically equivalent to its contrapositive, which is the expression ¬q ¬p. See “Implication and the Contrapositive” in Appendix A for more details.

Theorem 5.1: If 2ⁿ - 1 is prime, then n is prime.

Proof. Suppose n is not prime. Then there must be factors u and v such that

n = uv, u > 1, v > 1

Then

where the last step uses Equation 3.1, the difference of powers formula. Since u > 1, we know that both of the following are true:

So 5.1 shows that we have factored 2ⁿ - 1 into two numbers each greater than 1. But this contradicts the condition of the theorem is that 2ⁿ - 1 is prime. So the initial assumption in our proof must be false, and n must be prime.

As for discoveries 2 and 3, Fermat never shared the proofs. In a letter to his friend Frenicle, Fermat wrote that “he would send [the proof] if he did not fear being too long.” We shall return to them soon.

Pierre de Fermat (1601–1665)

Pierre de Fermat was a lawyer and provincial magistrate from Toulouse in the south of France. He was a Renaissance man in the tradition of Montaigne, interested in a variety of subjects including classical literature, and fluent in Latin and Greek. The last of the great amateur mathematicians, Fermat became interested in number theory after reading Bachet’s translation of Diophantus’ ancient Greek text Arithmetic. Although he made enormous contributions to mathematics, he never personally interacted with other mathematicians. In fact, Mersenne repeatedly invited him to visit Paris, but as far as we know, Fermat never went.

Fermat often boasted of his results while keeping his methods secret. He would often say that he had a proof of something, yet come up with an excuse not to provide it. When he did publicize a result, he would try to divulge as little as possible about how he did it.

During his life, Fermat never published his work, although he corresponded with Mersenne and others through letters. After Fermat’s death, his son published the edition of Diophantus with Fermat’s marginal notes. These notes contained many theorems, which were gradually confirmed by other mathematicians in later years. The last to be solved—which became known as Fermat’s Last Theorem—was the statement that aⁿ + bⁿ = cⁿ has no solutions in positive integers for n > 2. It was finally proved in 1994 by Andrew Wiles.

Fermat notoriously wrote “the proof is too large to fit in the margin” next to his statement of the Last Theorem. As mentioned earlier, this was his common pattern; he often gave similar excuses to avoid sharing his proofs. Although all but one of his conjectures have been confirmed, some of the proofs are so complex and lengthy that later mathematicians such as Gauss have been skeptical that Fermat actually discovered them.

In addition to his work on number theory, Fermat made major contributions to other areas of mathematics. He invented analytic geometry—the study of equations of curves—before Descartes, but described the work in an unpublished manuscript. He also co-invented probability theory in the course of a lengthy correspondence with Blaise Pascal.

Fermat made a lot of conjectures for which he left no proofs, but every one has since been proven true except one:

2ⁿ + 1 is prime n = 2ⁱ

(The double-arrow symbol is read “if and only if”; see Appendix A for details.) Since then, numbers of this form (2²ⁱ + 1) have been known as Fermat primes. It’s easy to prove a part of his conjecture:

Theorem 5.2: 2ⁿ + 1 is prime n = 2ⁱ.

Proof. Suppose n ≠ 2ⁱ. Then one of n’s factors must be odd, so we can express that factor as 2q + 1. This is > 1, so we can express n as

n = m(2q + 1)

Substituting m(2q + 1) for n and then using the formula for sum of odd powers (Equation 3.4), we factor 2ⁿ + 1:

But factoring 2ⁿ + 1 contradicts the premise of the conjecture; it can’t have nontrivial factors if it’s prime. So our initial assumption in the proof is false, and n = 2ⁱ.

What about other primes of the form 2²ⁱ + 1? Fermat states that 3, 5, 17, 257, 65537, 4294967297, and 18446744073709551617 are prime, and so are all the rest of this form. Unfortunately, he was wrong about two of his examples—only the first five are prime—and about his conjecture. In 1732, Euler showed that

2³² + 1 = 4294967297 = 641 × 6700417

In fact, we know that for 5 ≤ i ≤ 32, the numbers are composite. Are there any more Fermat primes besides these five? As of this writing, no one knows.

5.2 Fermat’s Little Theorem

We now come to one of the most important results in number theory.

Theorem 5.3 (Fermat’s Little Theorem):

If p is prime, a^p^–1 – 1 is divisible by p for any 0 < a < p.

Fermat claimed to have a proof of the theorem in 1640, but did not publish it. Leibniz discovered a proof some time between 1676 and 1680, but did not publish it either. Finally, Euler published two different proofs in 1742 and 1750. We will prove the theorem here, but first we need to derive several other results. While these may at first seem to be unrelated, we will see shortly how they come together.

Leonhard Euler (1707–1783)

Leonhard Euler (pronounced “OILer”) was born in a well-educated middle-class family in Switzerland. A talented and well-rounded student with an amazing memory, he studied with Johann Bernoulli, the greatest mathematician of the time and a friend of Euler’s father. (Bernoulli himself was a student of Leibniz, the co-inventor of calculus.)

For most of the 18th century, Czar Peter the Great and his successors conducted a period of dramatic reform that “Europeanized” Russian society and culture. One of the results of these reforms was the creation of the Imperial Academy of Sciences in St. Petersburg, which recruited European scholars. It was there in 1727 that Euler, at age 20, got a job doing mathematical research. Within 10 years, his results in mathematics, mechanics, and even shipbuilding established his reputation as one of the top scientific minds in Europe. By the time Frederick the Great recruited him to come to Berlin in 1741, Euler was an international superstar. At the time, kings and queens considered associating with scientists and other intellectuals to be an important way to increase their own status. Throughout Euler’s years in Berlin, the French and Russian royal courts competed to woo him away. Eventually, in 1766, he returned to St. Petersburg, where he spent the rest of his career.

Euler’s contributions to mathematics (and physics) were enormous. He worked in many areas; he founded modern graph theory and made fundamental discoveries in number theory. However, his greatest achievement was the development of modern analysis—calculus and differential equations—from the individual techniques invented by Newton and Leibniz to a systematic discipline. His three books on calculus (Introduction to Analysis of the Infinite, Differential Calculus, and Integral Calculus) were the definitive texts for nearly a century and still deserve careful study.

Euler wrote the first book on popular science, Letters to a German Princess, in which he explains the Newtonian view of the world to a lay person. He also wrote an elementary algebra textbook intended for non-mathematicians, which is still in print.

Euler was so prolific that after his death, the Russian Academy of Sciences took 60 years to publish all the additional work he had submitted. He was generally regarded as the greatest mathematician in the world in his time, and after 200 years, we still share Laplace’s view that “he is the master of us all.”

Our first step is another proposition from Euclid:

Theorem 5.4 (Euclid VII, 30): The product of two integers smaller than a prime p is not divisible by p.

(Another way to say this is that if p is prime and a and b are smaller than p, then ab is not divisible by p.) If some number x is divisible by some other number y, then x is a multiple of y: x = my. If x is not divisible by y, then dividing x by y leaves a remainder r: x = my + r. So we can restate the proposition like this:

p is prime ∧ 0 < a, b <p ab = mp + r ∧ 0 < r < p

Proof. Assume the contrary, that ab is a multiple of p. Then for a given a, let b be the smallest integer such that ab = mp. Then since p is prime, we know dividing p by b leaves a remainder v < b:

p = bu + v ∧ 0 < v < b

Multiplying both sides of the equation by a and then substituting with ab = mp gives

But this means that v is an integer smaller than b such that av is a multiple of p. That’s a contradiction, since we chose b to be the smallest such number. So our assumption is false, and ab is not divisible by p.

This approach was actually a common pattern for proofs in ancient Greek mathematics: choose the smallest of something, and then show that certain assumptions would lead to a smaller one.

* * *

Next, we prove a result about remainders:

Lemma 5.1 (Permutation of Remainders Lemma): If p is prime, then for any 0 < a <p,

where

0 < r_i < p ∧ i ≠ j r_i ≠ r_j

In other words, if we take all the multiples of a from 1a to (p - 1)a, and express each multiple in the form qp + r, every remainder r will be unique and the set of remainders will be a permutation of {1,..., p - 1}. (We know each remainder is less than p, so we have p-1 unique numbers in the range [1, p-1].)

Example: If p = 7 and a = 4, then the lemma says that

{4, 8, 12, 16, 20, 24} = {0 · 7 + 4, 1 · 7 + 1, 1 · 7 + 5, 2 · 7 + 2, 2 · 7 + 6, 3 · 7 + 3 }

so the remainders are

{4, 1, 5, 2, 6, 3}

which is a permutation of {1,..., 7 - 1}.

Proof. Suppose r_i = r_j and i < j; that is, two of the remainders are equal. Then we could take the difference of the two corresponding elements in the set, and the remainders r_i and r_j would cancel:

Since the ith and jth elements of the set are the products ai and aj, we could equivalently write the difference of these two elements as aj - ai. That is:

But this is of the form ab = mp, which implies that the product of two integers smaller than p is divisible by p. Since this contradicts Euclid VII, 30, which we just proved, our assumption must be false, and the remainders must be unique.

5.3 Cancellation

Now we will look at some results that deal with the notion of cancellation. If we are multiplying two numbers x and y, they cancel (i.e., their product is 1) when one is the multiplicative inverse of the other.

Cancellation and Modular Arithmetic

One way to view cancellation is in the context of modular arithmetic, which was introduced by Carl Gauss, whom we shall meet in Chapter 8. Although Euler did not use this technique in his proof of Fermat’s Little Theorem, you may find it useful to understand the logic.

A good analogy for modular arithmetic is a standard 12-hour clock. If it’s 10 o’clock, and you have to do something that’s going to take 5 hours, you’ll be done at 3 o’clock. In a sense, you’re saying that 10 + 5 = 3. More precisely, you’re saying that (10 + 5) mod 12 = 3. (Mathematicians would call noon “0,” though.) Of course, we can do modular arithmetic in any base. Here are a couple of examples using 7:

(6 + 4) mod 7 = 3

(3 x 3) mod 7 = (3 + 3 + 3) mod 7 = 2

Notice in the latter case that we could also calculate our product in the traditional way, then express it in terms of multiples of the modular base and a remainder:

(3 × 3) = 9 = (1 × 7) + 2

In other words, a value modulo n is equivalent to the remainder after using n as a divisor.

In elementary arithmetic (for example, arithmetic of rational numbers), if the product of two terms x and y is 1, then they are said to cancel, and x and y are called inverses of each other. The same is true in modular arithmetic, only the inverses will both be integers. For example,

(2 × 4) mod 7 = 1

so 2 and 4 cancel, and are each other’s inverse.

A negative number x mod n is equal to the positive number n-x; it’s the position you’d get to if you “turned the clock back” by x hours. In particular, -1 mod n = n – 1.

Just as with elementary arithmetic, we can write multiplication tables for modular arithmetic. Here’s one for integers modulo 7:

First we express the product as a multiple of 7 and a remainder; the modular product is then just the remainder. For example, 5 × 4 = 20 = (2 × 7) + 6 = 6 mod 7, so there is a 6 in the table at the intersection of row 5 and column 4. Observe that every row is a permutation of every other row, and that every row contains a 1. Recall that if the product is 1, the two factors are inverses. In the table above, we see, for example, that 2 and 4 are inverses since 2 × 4 = 1 mod 7. Here’s a version of the table with the inverse of each factor on the left shown in the column on the right:

Formally, for integer n > 1 and integer u > 0, we call v a multiplicative inverse modulo n if there is an integer q such that uv = 1 + qn. In other words, u and v are inverses if their product divided by n yields a remainder of 1. We will rely heavily on this in the following proofs.

* * *

The next result relies on this generalized notion of cancellation:

Lemma 5.2 (Cancellation Law): If p is prime, then for any 0 < a < p there is a number 0 < b < p such that ab = mp + 1.

In other words, a and b cancel modulo p.

Example: Suppose again that p = 7 and a = 4. Is there a value of b that satisfies the equation ab = mp + 1? Let’s try all the values of b until we find one that works:

Proof. By the Permutation of Remainders Lemma, we know that one of the possible products in the set

a · {1, ..., p – 1}

will have a remainder of 1. In this case we have p - 1 unique remainders greater than 0 and less than p, so one of them must be 1. Therefore, there must be another element b that cancels a.

Note that 1 and p -1 are self-canceling elements—that is, if you multiply each by itself, the result is 1 mod p, or (equivalently) the result can be expressed in the form mp + 1. It’s obvious that 1 · 1 can be expressed in this form, since it’s 0p + 1. What about p-1?

(p - 1)² = p² - 2p + 1 = (p - 2)p + 1 = mp + 1

In fact, 1 and p - 1 are the only self-canceling elements, which we’ll now demonstrate.

Lemma 5.3 (Self-Canceling Law):

For any 0 < a < p, a² = mp + 1 a = 1 ∨ a = p – 1

Proof. Assume there is a self-canceling a that’s neither 1 nor p - 1:

a ≠ 1 ∧ a ≠ p – 1 1 < a < p – 1

Rearranging the condition of the proof, we have

a² - 1 = mp

Factoring the expression on the left, we have

(a- 1)(a + 1) = mp

But since by our assumption 0 < a - 1, a + 1 < p, which means we have a product of two integers smaller than p that is divisible by p, a contradiction with Euclid VII, 30 (see p. 70). So our assumption is false, and the only self-canceling elements are 1 and p-1.

We are almost ready to prove Fermat’s Little Theorem, but we still need one more result: Wilson’s theorem, announced by Edward Waring in 1770, who attributed it to his student, John Wilson. At the time, Waring stated that he was unable to prove the theorem since he did not have the right notation—in response to which Gauss later remarked, “One needs notion, not notation.”

Theorem 5.5 (Wilson’s Theorem): If p is prime, there exists an integer m such that

(p- 1)! = mp + (p- 1)

or in other words

(p - 1)! = (p - 1) mod p

Proof. By definition,

(p- 1)! = 1 · 2 · 3 . . . (p- 1)

By the Cancellation Law, every number a between 1 and p - 1 has a number b in that range that’s its inverse; by the Self-Canceling Law, only 1 and p - 1 are their own inverses. So every other number in the product except 1 and p - 1 is cancelled by its inverse; that is, their product divided byp has remainder 1. In other words, we could express all the cancelled terms together—all the terms between 1 and p-1—as np+1 for some n. We still have our uncanceled terms 1 and p - 1, so our product now becomes

Then m = np - n satisfies the theorem.

Exercise 5.1. Prove that if n > 4 is composite, then (n – 1)! is a multiple of n.

5.4 Proving Fermat’s Little Theorem

Finally, using the results we’ve just derived, we can prove Fermat’s Little Theorem:

If p is prime, a^p^–1 – 1 is divisible by p for any 0 < a < p.

Proof. Consider the expression . We can move the a terms outside the product, so we have

Wilson’s Theorem can be written as

Therefore we can make the above substitution into Equation 5.2, giving

Now let’s return to the expression . Its expansion contains all the terms {a, 2a, 3a,..., (p-1)a}, which by the Permutation of Remainders Lemma (p. 71) is the same as {q₁p + r₁,..., q_p–1p + r_p–1}. So we can write

When we expand the product on the right, we get a sum containing many terms with p, and one that is the product of all r_i. We group all the p terms together; they give us some multiple up. What remains is the product of all r_i:

Now we can apply Wilson’s Theorem again to the product on the right, then again group multiples of p:

where w = u + v + 1. We know expressions 5.3 and 5.4 are equal, and need only some simple rearrangement:

Again, we can combine multiples of p on the right, giving our desired result:

a^p-1 -1 = np

So a^p-¹ - 1 is divisible by p.

We also observe that a^p-2 is an inverse of a, since a^p-2 · a = a^p-1, which Fermat’s Little Theorem tells us is mp + 1. (Remember that being an inverse with respect to p means having a remainder of 1 after dividing by p.)

* * *

What about the converse of Fermat’s Little Theorem? To prove that, we need one more intermediate result:

Lemma 5.4 (Non-invertibility Lemma): If n = uv ∧ u, v > 1, then u is not invertible modulo n.

Proof. Let n = uv and w be an inverse of u (i.e., wu = mn + 1). Then

So if we define z = (w - mv), then

(w - mv)n = zn = v

Since n > v, then zn > v, which is a contradiction with zn = v. So u cannot have an inverse.

Definition 5.1. Two numbers m and n are coprime if gcd(m, n) = 1. Equivalently, m and n are coprime if they have no common factors greater than 1.

The Non-invertibility Lemma tells us that when we are dealing with numbers modulo n, where n is not prime, there are invertible elements and non-invertible elements; elements that are not coprime to n are not invertible.

Theorem 5.6 (Converse of Fermat’s Little Theorem): If for all a, 0 < a < n,

a^n-1 = 1 + q_an

then n is prime.

Proof. Suppose n is not prime; that is, n = uv. Then by the Non-invertibility Lemma, u is not invertible. But by the condition of the theorem, uⁿ^-1 = uⁿ^-2u = 1 + q_un. In other words, u has an inverse un-2, which is a contradiction. So n must be prime.

5.5 Euler’s Theorem

Like any great mathematician, Euler was not satisfied with just proving Fermat’s Little Theorem; he wanted to see if it could be generalized. Since Fermat’s Little Theorem was only for primes, Euler wondered whether there was a similar result that would include composite numbers. But composite numbers do strange things in modular arithmetic. To illustrate this, let’s take a look at the multiplication table modulo 10, which we’ve annotated by showing inverses of the left-hand factor on the right-hand side of the table:

The table should look a bit familiar, because it’s just like the traditional 10×10 multiplication table, if you keep only the last digit of each product. For example, 7 × 9 = 63, which is 3 mod 10. Immediately we can see differences from the table we did for 7, which was prime (see p. 74). For one thing, the rows are no longer permutations of each other. More importantly, some rows now contain 0. That’s a problem for multiplication—how can the product of two things be 0? That would mean that we get into a situation where we can never escape zero—any product of the result will be zero.

The other property we noted earlier about primes—that only 1 and -1 are self-canceling—happens to be true for 10 as well, but is not always true for composite numbers. (The integer 8, for example, has four self-canceling elements: 1, 3, 5, and 7.)

Let’s look at the multiplication table for 10 again, focusing on certain entries:

The rows that contain only “good” products (i.e., no zeros) are the ones whose first factor is shown in a rectangular box on the left—which also happen to be the rows where that factor has an inverse, shown on the right side of the table. Which rows have this property? Those that represent numbers that are coprime with 10. (Remember, being coprime means having no common factors greater than 1.)

So could we just use the good rows and leave out the rest? Not quite, because some of the results in good rows would themselves lead to bad rows if used in a successive product. (For example, 3 is a good row, but (3 × 5) × 2 = 0.) Euler’s idea was to use only the entries in good columns as well as good rows—the numbers in shaded cells. Notice that those numbers have all the nice properties we saw for primes: the shaded numbers in each row are permutations of each other, each set of shaded numbers contains a 1, and so on.

* * *

To extend Fermat’s Little Theorem for composite numbers, Euler uses only these bold values. He starts by defining the size of the set of coprimes:

Definition 5.2. The totient of a positive integer n is the number of positive integers less than n that are coprime with n. It is given by the formula:

φ(n) = |{0 < i < n ∧ coprime(i, n)}|

This is known as the Euler totient function or Euler φ function.

φ(n) gives us the number of rows containing shaded entries in the multiplication table modulo n. For example, φ(10) = 4, and φ(7) = 6, as we can see from the multiplication tables given earlier.

Since primes by definition don’t share any prime factors with smaller numbers, the totient of a prime number is

φ(p) = p – 1

In other words, all numbers less than a given prime are coprime with it.

What Euler realized was that the p - 1 in Fermat’s theorem is just a special case; it’s what φ happens to be for primes. Now we can state Euler’s generalization of Fermat’s Little Theorem.

Theorem 5.7 (Euler’s Theorem): coprime(a, n) a^φ(n) - 1 is divisible by n.

Exercise 5.2. Prove Euler’s Theorem by modifying the proof of Fermat’s Little Theorem. Steps:

• Replace Permutation of Remainders Lemma with Permutation of Coprime Remainders Lemma. (Essentially, use the same proof but look only at “good” elements.)

• Prove that every coprime remainder has a multiplicative inverse. (We just showed that the remainders form a permutation, so 1 has to be somewhere in the permutation.)

• Use the product of all coprime remainders where the proof of Little Fermat has the product of all nonzero remainders.

* * *

We would like to be able to compute the φ function for any integer. Since we can express any integer as the product of powers of primes, we’ll start by seeing how to compute the totient of a power of a prime p. We want to know the number of coprimes of p^m. We know there are at most p^m - 1 of them, because that’s all the possible numbers less than p^m. But we also know that those divisible by p (i.e., multiples of p) are not coprime, so we need to subtract however many of these there are from our total:

What happens if we have φ(p^uq^v), where p and q are both primes? Again, we start with the maximum possible and then subtract off all the multiples. So we’ll subtract the number of multiples of p and also the number of multiples of q, but then we have to add back multiples of both p andq, because otherwise they’d be subtracted twice. (This general technique, known as the inclusion-exclusion principle, is often used in combinatorics.) Let us assume n = p^uq^v:

As a special case when we have a simple product of two primes, p₁ and p₂, we now know that

For example, since 10 = 5 × 2,

φ(10) = φ(5)φ(2) = 4

Although the case we care most about is the one given here, we can generalize the formula to handle a product of any number of primes raised to powers, not just two. For example, if we had three factors p, q, and r, we’d subtract all the multiples of each, then add back the double-counted multiples of pq, pr, and qr, and then compensate for our over compensation by again subtracting multiples of pqr. Extending this to m primes gives this formula, where :

Euler’s interest in proving his theorem led to his need to count coprimes. His derivation of the φ function gave him a tool that allowed him to efficiently compute this count in the cases where the prime decomposition is known.

5.6 Applying Modular Arithmetic

In Section 5.3, we saw how modular multiplication was related to remainders. Let’s take a look at a couple of our important results from earlier in the chapter and see what some examples look like if we do them modulo 7. Wilson’s Theorem states that for a prime p, there exists some m such that

(p-1)! = ( p - 1) + mp

Another way to say this is

(p - 1)! = (p - 1) mod p

Let’s see if we can confirm that result if p is 7. p - 1 is 6, so we start by expanding 6! into its factors, rearranging them, and using our modular multiplication table to cancel inverses:

which is what Wilson’s Theorem predicts.

Similarly, let’s use modular multiplication to see what Fermat’s Little Theorem says. The original form is

If p is prime, a^p-1 – 1 is divisible by p for any 0 < a < p.

But with modular arithmetic, we could restate it as

If p is prime, a^p^–1 –1 = 0 mod p for any 0 < a < p.

If p is prime, a^p^–1 = 1 mod p for any 0 < a < p.

Again, let’s use p = 7, and try a = 2. This time we’ll expand our expression, multiply both sides by 6!, and then use modular multiplication to cancel terms:

which is what Fermat’s Little Theorem tells us.

5.7 Thoughts on the Chapter

Earlier, we saw how the ancient Greeks were interested in perfect numbers. There wasn’t any practical value to this work; they were simply interested in exploring properties of certain kinds of numbers for their own sake. Yet as we have seen in this chapter, over time the search for these “useless” perfect numbers led to the discovery of Fermat’s Little Theorem, one of the most practically useful theorems in all of mathematics. We’ll see why it’s so useful in Chapter 13.

This chapter also gave us a first look at the process of abstraction in mathematics. Euler looked at Fermat’s Little Theorem and realized that he could extend it from one specific situation (primes) to a more general one (integers). He saw that the exponent in Fermat’s theorem was a special case of a more general concept, the number of coprimes. That same process of abstraction lies at the heart of generic programming. Generalizing code is like generalizing theorems and their proofs. Just as Euler saw how to extend Fermat’s result from one type of mathematical object to another, so programmers can take a function that was designed for one type of computational object (say, vectors) and extend it to work equally well on another (perhaps linked lists).