Can you use 2^n - 2 / n to check if a number is prime with 100% accuracy?

Question

According to the AKS primality test:

$$(x-1)^p - (x^p-1)$$

If all coefficients (which can be found in Pascal's triangle) are divisible by p then p is prime.

If we sum these coefficients we get:

$2$ for $p = 2$;

$6$ for $p = 3$;

$14$ for $p = 4$;

$30$ for $p = 5$

$\ldots$

If all the coefficients are divisible by p, then the sum of all those coefficients must also be divisible by p

$sum = 2^p - 2$

So if $(2^p - 2) / p$ is a natural number, can we conclude that $p$ is definitely prime?

Please correct me if I made any obvious mistake

By Fermat's little theorem a prime number $p$ is always a divisor of $2^p-2$. — Jack D'Aurizio, Jun 28 '17 at 23:02
However, it is not true that if $a^n\equiv a\pmod{n}$ holds for every $a\in[1,n-1]$ then $n$ is a prime. See https://en.wikipedia.org/wiki/Carmichael_number — Jack D'Aurizio, Jun 28 '17 at 23:03

Reiner Martin · Accepted Answer · 2017-06-28T23:10:05.030

3

If a sum is divisble by $p,$ it does not mean the summands are.

The smallest counterexample to your claim is $p=341.$ We have $341=11\cdot 31,$ but $2^{341}=2\cdot(2^{10})^{34} = 2\cdot(1024)^{34} = 2\cdot(3\cdot 341+1)^{34} \equiv 2\cdot 1^{34} = 2 \pmod{341}.$

edited Jun 28 '17 at 23:10

answered Jun 28 '17 at 23:02

Reiner Martin

4,097

Can you use 2^n - 2 / n to check if a number is prime with 100% accuracy?

1 Answers1