Three proofs that 2017 is prime

Aaron Meurer asked on Twitter whether there’s a proof that 2017 is prime that would fit into 140 characters.

My first reply was this:

sqrt(2017) < 45.
2017 not divisible by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, or 43.
Ergo prime.

I’m not sure that’s what he had in mind. There’s some implied calculation (which I didn’t actually do), so it’s kinda cheating. It would be interesting if there were something special about 2017 that would allow a more transparent proof.

(Implicit in the proof above is the theorem that if a number has a prime factor, it has a prime factor less than it’s square root. If you multiply together numbers bigger than the square root of n, you get a product bigger than n.)

Then for fun I gave two more proofs that are more sophisticated but would require far too much work to actually carry out by hand.

The first uses Fermat’s little theorem:

For 0 < a < 2017, a2016 − 1 is divisible by 2017.
2017 is not one of the three Carmichael numbers < 2465.
Ergo prime.

Fermat’s little theorem says that if p is prime, then for any 0 < ap, ap − 1 − 1 is divisible by p. This is actually an efficient way to prove that a number is not prime. Find a number a such that the result doesn’t hold, and you’ve proved that p isn’t prime. For small numbers, the easiest way to show a number is not prime is to show its factors. But for very large numbers, such as those used in cryptography, it’s efficient to have a way to prove that a number has factors without having to actually produce those factors.

Unfortunately, Fermat’s little theorem gives a necessary condition for a number to be prime, but not a sufficient condition. It can appear to be prime for every witness (the bases a are called witnesses) and still not be a prime. The Carmichael numbers pass the Fermat primailty test without being prime. The first four are 561, 1105, 1729, and 2465.

For more on using Fermat’s little theorem to test for primality, see Probability that a number is prime.

The final proof was this:

2016! + 1 is divisible by 2017, and so by Wilson’s theorem 2017 is prime.

Unlike Fermat’s little theorem, Wilson’s theorem gives necessary and sufficient conditions for a number to be prime. A number n is prime if and only if (n − 1)! + 1 is divisible by n. In theory you could use Wilson’s theorem to test whether a number is prime, but this would be horrendously inefficient. 2016! has 5,789 digits. (You can find out how many digits n! has without computing it using a trick described here.)

Despite its inefficiency, you can actually use Wilson’s theorem and SymPy to prove that 2017 is prime.

      >>> from sympy import factorial
      >>> x = factorial(2016) + 1
      >>> x % 2017


9 thoughts on “Three proofs that 2017 is prime

  1. I actually like the first reply best. It’s the only one you can verify with just mental calculations. It’s easy to forget that you only have to test primes p < sqrt(n) to check if n is prime.

  2. The following is a bit elliptic, but it provides easy to check certificates that show that 2017 is not divisible by any of the primes to be tested.

    test primes < sqrt(2017): 2 3 5 7 11 13 17 19 23 29 31 37 41 43

  3. In R you could use the Rmpfr package:

    (factorial(as.bigz(2016)) + 1) %% 2017
    ## Big Integer (‘bigz’) :
    ## [1] 0

  4. Benoît R. Kloeckner

    You do not need to actually compute 2016! to apply Wilson’s theorem: you can do the computation modulo 2017, saving time and memory space. This is actually doable by hand, though still tedious.

  5. How about this?

    2, 3 and 5 are not factors; 7*11*13*17*19*23*29*31*37*41*43=436092044389001; hcf(2017,436092044389001) = 1.

    Again there is some implied computation, but the Euclidean algorithm part would be fairly quick.

  6. A variation on 1:
    for 1 < a < 2016, a^1008-1 or a^1008+1 is divisible by 2017
    ergo prime

    If n is a Carmichael number, then x^2 = 1 (mod n) has at least 8 solutions.

  7. I goofed. I should be

    for 1 <= a <= 2016, a^1008-1 or a^1008+1 is divisible by 2017
    and for 1 < a < 2016, a^2-1 is not divisible by 2017,
    ergo prime.

Comments are closed.