Tweaking Fermat's primality test - Why does it work and should I expect different results?

67 Views Asked by At

Fermat's primality test states that for any $p$ as a positive odd integer, IF:

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

or in a different way: $$a^{{p}}-a\equiv 0{\pmod {p}}$$

THEN $p$ is probably prime.

Out of curiosity I was trying to see if I can get the same or any different outcomes, applying some basic tweaking (without the complexities of other primality tests).

I came up with the following:

For it to work: $x$ can be any positive even integer and $p > 5$:

$$\frac{2^{(p-2)}-2}{6}-\frac{p^x-1}{4} \equiv 0 \pmod p$$

To make it even more easy, I just set $x=2$:

$$\frac{2^{(p-2)}-2}{6}-\frac{p^2-1}{4} \equiv 0 \pmod p$$

I am not sure if the results are the same as the traditional test, but so far it seems to be working as well as the traditional test.

My question is: Why does it work in general and should I expect different results?
Examples:

  1. $$\frac{2^{(7-2)}-2}{6}-\frac{7^2-1}{4} = -7$$ $$ -7 \equiv 0 \pmod 7$$

  2. $$\frac{2^{(9-2)}-2}{6}-\frac{9^2-1}{4} = 1$$ $$ 1 \not\equiv 0 \pmod 9$$

  3. $$\frac{2^{(11-2)}-2}{6}-\frac{11^2-1}{4} = 55$$ $$ 55 \equiv 0 \pmod {11}$$

  4. $$\frac{2^{(13-2)}-2}{6}-\frac{13^2-1}{4} = 299$$ $$ 299 \equiv 0 \pmod {13}$$

1

There are 1 best solutions below

0
On BEST ANSWER

Call your test term $f_p.\,$ Wlog $\,2,3\nmid p\,$ so $\, (p,12)=1\,$ so $\,p\mid f_p\iff p\mid 12f_p.\,$ But

$$\bmod p\!:\,\ 12f_p = 12\left[\dfrac{2^{p-2}-2}6 - \dfrac{p^{2k}-1}4\right]\equiv 2^{p-1}-1\qquad $$

Therefore $\,p\mid f_p \iff p\mid 2^{p-1}-1$ so your test is equivalent to the classical test.