New Mersenne prime

With impeccable timing, just in the middle of my series about primality testing, a new Mersenne prime has been announced, a little under two years after the previous one. In particular, it has been shown that 2^{77,232,917}-1 is prime; this is now the largest known prime number.

If you want to understand what computers are actually doing when they check a Mersenne number for primality, I wrote a whole series about it two years ago: visit this list of my post series and search for “Lucas-Lehmer”.

Posted in number theory, primes | Tagged , , , , | Leave a comment

A tale of three machines

The Fundamental Theorem of Arithmetic tells us that any positive integer can be factored into a product of prime factors.1 Given a positive integer n, this leads naturally to several questions:

  1. What is the prime factorization of n?

This is the most obvious question we could ask. The Fundamental Theorem tells us such a prime factorization must exist (and must be unique up to the order of the factors), so we can simply ask what it is. For example, if n = 101500, then the answer would be n = 2^2 \cdot 5^3 \cdot 7 \cdot 29. What we really want is some sort of machine (let’s call it a factorization machine) where we can put a positive integer in one end, the machine makes whirring, griding, and beeping sounds for a while, and then a factorization pops out the other end:

Another question we could ask about n would be:

  1. What is one prime factor of n?

An answer to this question is a similar sort of machine, except instead of getting the entire prime factorization out, we just get one prime factor; let’s call this a factor machine. For example, it might work like this:

These first two machines are very closely related. If we have a factorization machine we can easily use it to build a factor machine: just run n through the factorization machine, pick one of the factors to return, and throw the rest away.

Slightly less obviously, we can also use a factor machine to build a factorization machine: run n through the factor machine to get a prime factor p_0. Now we can compute n_1 = n/p_0 (by definition, p_0 must evenly divide n); to get the rest of the factorization of n we just need to factor n_1. So we run n_1 through the factor machine to get a prime factor p_1; we compute n_2 = n_1/p_1; and so on. We are done when putting n_i into the factor machine returns n_i itself; that means n_i = p_i is prime. Finally, we return the factorization p_0 \cdot p_1 \cdot \dots \cdot p_i.

For example, if we run 101500 through the factor machine and get 7, then we compute 101500/7 = 14500. Next we run 14500 through the factor machine again and get, say, 5, and then compute the remaining part that needs to be factored, 14500/5 = 2900; and so on.

Finally, here’s a third question we could ask:

  1. Is n prime?

In answer to this we could imagine another similar machine which outputs a simple yes/no answer. Let’s call this a primality machine:

Given a factor machine, we can easily use it to build a primality machine: take the input n and run it through the factor machine. If the answer is n, then n is prime so output “YES”; otherwise, n is not prime (since it is divisible by the output factor), so output “NO”.

But what about the converse? If we have a working primality machine, can we use it to build a factor machine? Given some n, if the primality machine says YES then n is prime, so the factor machine should output n. But what if the primality machine says NO? On the face of it, the mere fact of knowing that n is composite does not help us find a factor. But what is the primality machine doing on the inside? If it knows that n is not prime, it must have figured out a way to factor n, right? That is, somewhere in the internals of the machine, there must have been a factor that it simply isn’t telling us about:

If this is true, it means we could rip open the guts of the primality machine and use it to build a factor machine. Or, put more simply, this would be saying that the only way to make a primality machine is to build it out of a factor machine. This seems intuitively reasonable: how could you know that n is composite without factoring it?

The punchline is that this is not true!! That is,

It is possible to make working primality machines that truly do not know anything about any factors of n.

Not only that, but we know how to make primality machines that run much faster than the fastest known factor machines!

Let that sink in for a minute. It is really quite surprising that we can find out whether n has any prime divisors without actually finding out what they are, and that moreover it is much faster if you don’t care what the prime factors are. Think of it as a sort of “computational loophole” in our universe.

This is no mere curiosity; it turns out that this “loophole” is actually the basis of almost all of modern cryptography. When your browser makes an encrypted connection to a website in order to securely transmit your credit card information, it is relying on this loophole: your browser needs to pick some numbers and make sure that they are prime, which it can do quickly; but for anyone intercepting the messages to steal your credit card, they would have to factor another number, which (as far as we know) cannot be done quickly. (This is really cool and a topic for another post.)

It gets stranger, though: you may have noticed that I keep using phrases such as “fastest known”, “seems”, and “as far as we know”. It turns out that no one has been able to prove that making faster factor machines can’t be done! So it’s possible that the “loophole” isn’t a loophole at all; perhaps with a clever enough idea it will turn out to be possible to factor numbers just as fast as we can test whether they are prime. But most people don’t believe that.

In some upcoming posts I plan to talk a bit more about what we actually mean when we are talking about these machines being “fast” or “slow”, and then finally get around to explaining some different ways of building fast primality machines.

  1. Possibly a product of no prime factors, which accounts for 1.

Posted in computation, number theory, primes | Tagged , , , , | 10 Comments

Fermat’s Little Theorem: proof by group theory

It’s time for our third and final proof of Fermat’s Little Theorem, this time using some group theory. This proof is probably the shortest—explaining this proof to a professional mathematician would probably take only a single sentence—but requires you to know some group theory as background. Fortunately I’ve written about the relevant group theory before, so I will link to the relevant posts if you want to read up on the background.

This time we’re going to prove statement 1:

If p is prime and a is an integer where 0 < a < p, then a^{p-1} \equiv 1 \pmod p.

Consider the set P = \{1, 2, \dots, p-1\}. I claim that this set forms a group under the operation of multiplication \pmod p. To verify this we need to check several things:

  • First, we need to check that the set is closed under the given operation, that is, if we start with two elements from P and multiply them \pmod p, we will end up with an element in P again. If we reduce the product \pmod p, we will definitely get something less than p; so the real question is why we will never get 0. This is because if 0 < a,b < p and p is prime, then neither a nor b is divisible by p, and hence neither is ab.
  • We need to check that this operation is associative—and indeed, multiplication \pmod p is associative.
  • There needs to be an identity element, and there is: 1 \cdot a  \equiv a \cdot 1 \equiv a \pmod p.
  • Finally, every element must have a multiplicative inverse, that is, for any a \in P, there must be some b \in P such that ab \equiv  1 \pmod p. But we already know this is true (this also came up when proving two of the statements of Fermat’s Little Theorem equivalent).

So P is a group under the operation of multiplication \pmod p, and it has p-1 elements, that is, its order is p-1. But by Lagrange’s Theorem, the order of each element evenly divides the order of the group. So let a \in P and suppose a has order k, that is, a^k \equiv 1 \pmod p. Then k divides p-1, that is, there is some j such that jk = p-1. Then a^{p-1} \equiv a^{jk} \equiv (a^k)^j \equiv 1^j \equiv 1 \pmod p.

It is also easy to generalize this proof to a proof of Euler’s Theorem; I will leave it to interested readers to fill in the details. Recall that Euler’s Theorem says that if n is any integer and a is relatively prime to n, then a^{\varphi(n)} \equiv 1 \pmod p. Consider the set \Phi(n) of all positive integers 0 < a < n which are relatively prime to n. This also forms a group under the multiplication \pmod n, and hence any element a raised to the order of the group (\varphi(n)) results in the identity element (1).

There are many more proofs of Fermat’s Little Theorem, but this has been a representative sampling! In future posts, I’m going to explore the mathematics behind several computational tests for primality, most of which end up relying on Fermat’s Little Theorem in one way or another.

Posted in group theory, number theory, primes, proof | Tagged , , , , | Leave a comment

Post without words #21

Posted in combinatorics, geometry, posts without words | Tagged , , | 15 Comments

Fermat’s Little Theorem: proof by necklaces

It’s time for our second proof of Fermat’s Little Theorem, this time using a proof by necklaces. As you know, proof by necklaces is a very standard technique for… wait, what do you mean, you’ve never heard of proof by necklaces?! Honestly, what do they teach in schools these days…?

…just kidding! I’ll explain what necklaces are in a minute. But first, let me state that we will be proving statement (3) of FlT, namely,

If p is prime and a is any integer, then a^p \equiv a \pmod p.

Subtracting a from both sides, this is the same as saying that a^p - a \equiv 0 \pmod p, which is in turn the same as saying that a^p - a is evenly divisible by p. As we have already seen, this statement is equivalent to the other statements (1) and (2) of Fermat’s Little Theorem.

Now, this is a necklace:

That is, a necklace is a circular arrangement of colored beads. (I’ve also labelled each bead with a number corresponding to its color, to make it easier to distinguish them.) Two necklaces are the same if they are rotations of each other. For example, these three necklaces, although they are drawn differently, are all the same:

Unlike in real life, though, we’re not allowed to flip necklaces over,1 so these two necklaces are different:

Now, suppose we have a different bead colors to choose from. Assume that we have a plentiful supply of each bead color, so we can use as many beads of each color as we want. Here is the central question we will consider:

How many necklaces are there with exactly p beads and at least two different colors?

We will show that there are in fact \displaystyle\frac{a^p - a}{p} such necklaces—and since the number of necklaces is obviously an integer, this means that p must evenly divide a^p - a. So, on with the proof!

If you cut a necklace in between two beads and open it up, you get a strand (also commonly called a string or a word). Like this:

Let’s start by counting strands. First, the number of different strands with p beads chosen from a possible colors is a^p: for each one of the p beads we can independently choose any one of the a available colors, for a total of \underbrace{a \cdot a \cdot \dots \cdot a}_p = a^p choices. For example, if a = 2 and p = 5, here are the 2^5 = 32 different possible strands with 5 beads and (up to) two colors:

Notice that we don’t have to use all the colors in each strand. a is the number of available colors, but just because a color is available doesn’t mean we have to use it. As another example, here are the 3^3 = 27 strands with three beads chosen from among three available colors:

Now, some of these strands use only a single color, that is, all their beads are the same color. In fact, there are exactly a such strands, one for each color. So the number of strands with at least two different colors is a^p - a: the total number of strands minus the strands with only one color.

So, how many necklaces are there? Let’s work backwards: think about starting with a necklace and cutting it at various points to create different strands. For example, if we start with the necklace shown below and cut it in all five possible locations, we get five distinct strands:

You can check that these five strands are all different. However, this is not always the case. For example, cutting the necklace shown below yields only three different strands:

I’ve drawn six strands above, representing all six possible cuts, but as you can see, they are not all unique—in fact, there are two copies of each strand.

What’s the difference? Well, the difference is that 5 is prime whereas 6 is not! Remember that we assumed p, the length of our necklaces, is prime. And I claim that every necklace of prime size p, that uses two or more colors, yields exactly p distinct strands when cut.

Why is that? Think about what it means if a necklace yields the same strand when cut in two different places which are spaced k beads apart. (In the example shown above, k = 3.) Since the strands are the same, the beads right after each cut must be the same; the beads two places after each cut must be the same, the beads three places after each cut must be the same, and so on—in general, if you look at any two beads spaced k apart, they must be the same. But this means that the whole necklace has a period of k—that is, the necklace consists of a group of k beads which is repeated some number of times. But if the whole necklace is made up of some number of repetitions of a group of k beads, that means k must evenly divide the size of the necklace p. But if p is prime, the only way for this to happen is if k = 1, in which case the necklace consists of a single repeated bead, that is, the necklace only has one color.

So, when p is prime, each necklace with at least two bead colors corresponds to exactly p different strands—and each strand corresponds to exactly one necklace (the one you get when you glue the ends of the strand together). For example, here is the correspondence between the 6 different necklaces of size p = 5 with at least two colors chosen out of a = 2, and the a^p - a = 2^5 - 2 = 30 different strands containing both colors. Each necklace corresponds to exactly 5 different strands.

We already know there are a^p - a strands with at least two colors; since we can put them in groups of p, one for each necklace of at least two colors, a^p - a must be evenly divisible by p. QED!

  1. Circular arrangements of beads which are considered the same up to rotations and flips are usually called bracelets.

Posted in combinatorics, number theory, primes, proof | Tagged , , , , , , | 3 Comments

Euler’s Theorem: proof by modular arithmetic

In my last post I explained the first proof of Fermat’s Little Theorem: in short, a \cdot 2a \cdot 3a \cdot \dots \cdot (p-1)a \equiv (p-1)! \pmod p and hence a^{p-1} \equiv 1 \pmod p. Today I want to show how to generalize this to prove Euler’s Totient Theorem, which is itself a generalization of Fermat’s Little Theorem:

If n \geq 1 and a is any integer relatively prime to n, then a^{\varphi(n)} \equiv 1 \pmod n.

Remember that \varphi(n) is the function that tells us how many positive integers less than n are relatively prime to (share no common factors with) n. So, for example, suppose n = 12 and a = 7. There are four positive integers among \{1, \dots, 11\} which are relatively prime to 12 (namely, 1, 5, 7, and 11), so the theorem says we should have 7^4 \equiv 1 \pmod{12}, which we can verify: 7^4 = 2401 = 200 \cdot 12 + 1.

Once again, we start by considering the set of multiples of a up to (n-1)a:

\{a, 2a, 3a, \dots, (n-1)a \}.

However, in this more general context we don’t want to use all of them! Our proof of Fermat’s Little Theorem relied on the fact that if p (here, n) is prime, then none of 1, 2, \dots, (p-1) have any factors in common with it. But if n is not prime that may no longer be true. So, instead of the set above, we will look at the set of multiples of a which are relatively prime to n. Since we already assumed a is relatively prime to n, this is equivalent to saying we want multiples ka where k is relatively prime to n:

M = \{ ka \mid 1 \leq k < n, \gcd(k,n) = 1 \}

(\gcd(k,n) = 1 is another way to say that k and n are relatively prime: they share no factors in common if and only if they have no nontrivial common divisor, that is, their greatest common divisor is 1.) Note that |M| = \varphi(n): the number of things relatively prime to n between 1 and n-1 is exactly what \varphi(n) counts.

As an example, suppose n = 12 and a = 5. The only multiples of a which are relatively prime to n are

\{1 \cdot 5, 5 \cdot 5, 7 \cdot 5, 11 \cdot 5\} = \{5, 25, 35, 55\}.

If we take these \pmod {12}, we get

\{5, 1, 11, 7\}

and hey, look at that—it’s the numbers relatively prime to 12 again, just in a different order! As another example, suppose n = 20 and a = 3. The numbers relatively prime to 20 are \{1,3,7,9,11,13,17,19\}, and we can check that

\{3,9,21,27,33,39,51,57\} \equiv \{3,9,1,7,13,19,11,17\} \pmod {20}.

So the claim is that if we start with all the numbers relatively prime to n, multiply them all by a, and then take their remainders \pmod n, we get back the same set we started with (though quite possibly in a different order). More formally, let \Phi(n) = \{ k \mid 1 \leq k < n, \gcd(k,n) = 1 \} be the set of numbers relatively prime to n. Then the claim is that

a \cdot \Phi(n) \equiv \Phi(n) \pmod{n}

where multiplying a number by a set, like a \cdot \Phi(n), means to multiply each element of the set by the given number.

The proof of this claim starts out quite similar to the proof from last time. First, suppose there are two multiples of a, say, ja and ka, which have the same remainder when divided by n. We can write this as ja \equiv ka \pmod n. Subtracting ka from both sides and factoring out a, we find that a(j-k) \equiv 0 \pmod n, that is, a(j-k) is divisible by n. By assumption, a is relatively prime to n, so the only way for this to be true is if j - k is divisible by n, but since j and k are less than n, the only way for this to happen is if j - k = 0, that is, j = k. So this means that if we start with different multiples of a, we get different remainders out.

However, this isn’t enough—this time we actually care about which remainders we get. We have to prove that if we start with only those multiples which are relatively prime to n, we get exactly the same remainders out. So far, we haven’t used the fact that j and k are relatively prime to n at all. Indeed, if we take all multiples of a, we still end up with each remainder only once:

\{5,10,15,20,25,30,35,40,45,50,55\} \pmod {12} = \{5,10,3,8,1,6,11,4,9,2,7\}

However, you’ll see later why we specifically want only the remainders which are relatively prime to n.

So, assuming j is relatively prime to n, consider the remainder r we get after dividing ja by n. So, ja is r more than some multiple of n, that is, ja = qn + r. We want to show that r is relatively prime to n. If r had a factor d in common with n, then the whole right-hand side qn + r would be divisible by d (because a sum of multiples of d is also a multiple of d). But then the left-hand side, ja, would be divisible by d also, but neither j nor a can be divisible by d, since both are relatively prime to n. Hence r in fact has no factors in common with n.

We’re almost done now. We start with the equation

a \cdot \Phi(n) \equiv \Phi(n) \pmod n

and, just like last time, we now multiply together everything on the left and everything on the right. On the left we can factor out \varphi(n) copies of a, and this leaves us with

\displaystyle a^{\varphi(n)} \prod \Phi(n) \equiv \prod \Phi(n) \pmod n

where \prod means to take the product of all the elements in a set. Finally, we can see why it was important that we only took multiples of a which are relatively prime to n: this means the product \prod \Phi(n) shares no common factors with n, which means we can divide by it on both sides, concluding that

a^{\varphi(n)} \equiv 1 \pmod n.

If we had instead used the multiples of a as before, we would end up with

a^{n-1} (n-1)! \equiv (n-1)! \pmod n,

which is a valid equation, but the problem is we are stuck here: dividing both sides by (n-1)! would not result in a valid modular equation, since (n-1)! shares one or more common factors with n when n is not prime.

Posted in number theory, primes, proof | Tagged , , , | Leave a comment

Fermat’s Little Theorem: proof by modular arithmetic

In a previous post I explained four (mostly) equivalent statements of Fermat’s Little Theorem (which I will abbreviate “FlT”—not “FLT” since that usually refers to Fermat’s Last Theorem, whose proof I am definitely not qualified to write about!).

Today I want to present the first proof of FlT. We’re going to prove statement (2), that is,

If p is a prime and a is any integer not divisible by p, then a^{p-1} \equiv 1 \pmod p.

We already saw that statements (1), (2), and (3) are logically equivalent, so proving (2) is sufficient to prove all of them. (As I’ll show in a future post, we can also generalize this proof to prove the corrected version of statement (4).)

So, suppose p is a prime, and a is any integer not divisible by p. Now consider the set of multiples of a up to (p-1)a:

\{a, 2a, 3a, \dots, (p-1)a \}.

However, we will consider not the multiples of a themselves but their remainders when divided by p. As an example, suppose p = 7 and a = 3. Then we want to look at multiples of a: 3, 6, 9, 12, 15, 18—and then take their remainders \pmod 7. As you can check, this yields the set

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

As another example, suppose p = 13 and a = 20. Then the multiples of a, considered \pmod {13}, are 20 \equiv 7, 40 \equiv 1, 60 \equiv 8, and so on, ultimately yielding the set of remainders (which you can again check):


Have you noticed anything about the previous examples? It looks like every possible remainder (other than 0) shows up exactly once, (though obviously not in order). Will this always be true?

The fact that 0 doesn’t show up is no mystery: we specified that a is not divisible by p, and in that case none of a, 2a, \dots, (p-1)a will be divisible by p either, so none of them have a remainder of 0. But why would their remainders all be different?

Suppose there are two multiples of a, say, ja and ka, which have the same remainder when divided by p. We can write this as ja \equiv ka \pmod p. Subtracting ka from both sides and factoring out a, we find that a(j-k) \equiv 0 \pmod p, that is, a(j-k) is divisible by p. Well, when a prime divides a product of two things, it must divide one or the other (or both). But we already assumed a is not divisible by p. Hence p must evenly divide j-k. But j and k are both less than p, so their difference must lie strictly between -p and p. The only multiple of p strictly between -p and p is zero, so j - k = 0, that is, j = k. So the only way to have ja \equiv ka \pmod p is if j = k. Put the other way around, we’ve shown that if j \neq k then ja and ka don’t have the same remainder \pmod p. So this proves that all the multiples of a from a up to (p-1)a have different remainders when divided by p.

Finally, since there are exactly p-1 multiples of a in our set, and p-1 possible nonzero remainders \pmod p, and all the remainders have to be different, we conclude that each remainder shows up exactly once.

So what? Here comes the clever trick: what happens if we take all those multiples of a and multiply them all together, and then take the remainder \pmod p? Since taking remainders commutes with multiplication (that is, ab \bmod p \equiv (a \bmod p)(b \bmod p)), this is the same as if we first take their remainders and then multiply those. But we already know that the remainders will contain each number from 1 to (p-1) exactly once—and if we’re multiplying them then the order doesn’t matter. So,

a \cdot 2a \cdot 3a \cdot \dots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \pmod p,

that is, the product of all the multiples of a has the same remainder as the factorial of (p-1) when divided by p. For example, looking at the example of p = 7 and a = 3 again, the product of the multiples of a is 3 \cdot 6 \cdot 9 \cdot 12 \cdot 15 \cdot 18 = 524880, whereas 6! = 720; but both have a remainder of 6 when divided by p = 7.

Now, we can factor the (p-1) copies of a out of the left side, and we are left with

a^{p-1} (p-1)! \equiv (p-1)! \pmod p

Now we just want to cancel (p-1)! from both sides—though we have to be a little careful when dividing both sides of a modular equation. In general it’s only valid when the thing you want to divide by is relatively prime to the modulus (this same issue came up in my previous post). But that is indeed the case here: (p-1)! is not divisible by p (since p is prime and (p-1)! is the product of a bunch of things that are all smaller than p). So we are justified in dividing both sides by it, and this completes the proof:

a^{p-1} \equiv 1 \pmod p.

Posted in number theory, primes, proof | Tagged , , | 8 Comments