Is this a new deterministic primality test???

Question

$|(x-1)^p -(x^p-1)-(x^{p-1} -2)| \equiv -1 \mod p$

It seems to work. Can anyone refute it or improve it?

Answer 1

$(x-1)^p -(x^p-1)-(x^{p-1} -2)$ is negative for positive $x$. Thus (I will assume $p $ is prime and will use Fermat's little theorem):

$$\begin{align}& |(x-1)^p -(x^p-1)-(x^{p-1} -2)| \\ =&-(x-1)^p +(x^p-1)+(x^{p-1} -2) \\ \equiv & -(x-1)+(x-1)+x^{p-1}-2 \\ = & x^{p-1}-2 \\ \equiv & -2+\begin {cases}0 & p|x \\ 1 & \text{otherwise}\end {cases} \\ =& \begin {cases}-2 & p|x \\ -1 & \text{otherwise}\end {cases}\end {align}$$

so your formula holds for $x\gt 0, x\not\equiv 0\pmod p $.

Notes:

• The formula doesn't hold for negative $x $, fix it by removing the modulus and just putting the minus sign in front.
• There is a lot of overhead: no need to calculate $(x-1)^p $ and $x^p-1$ when they will cancel each other.
• Why take away 2 to get -1 when you can not take away 2 and get... well... 1?

In other words, your test boils down to: $x^{p-1}\equiv 1\pmod p $ if $p\not|x $. This is a well-known result (Fermat's little theorem proves one side, and for a composite number the test fails for any proper divisor $x\ne 1$ of $p $). Caveat: I didn't look at how your test behaves for composite $p $ - it may well succeed...

As a practical primality test, this requires testing every number $x$ in the range $[2,p-2] $, so is grossly inefficient. If you are already iterating in that range - why not check directly if $x|p $ or not?