## Other

drummers-lowrise

Message boards : General discussion : An Impractical Test for Twin Primes

Author Message
composite
Volunteer tester

Joined: 16 Feb 10
Posts: 1002
ID: 55391
Credit: 879,355,065
RAC: 316,764

Message 153187 - Posted: 11 Jan 2022 | 5:18:22 UTC

Here's a conjecture and proof.
p! == 1 (mod p+2) if and only if (p+2) is prime. (I use '==' for congruent)
Equivalently
(p-2)! == 1 (mod p) if and only if p is prime. (yes, 0! = 1 is true, look it up)

Proof:
Wilson's Theorem states (p-1)! == -1 (mod p) if and only if p is prime.

Starting with a prime p, make a change of variables u=p-2 so Wilson's Theorem becomes
(u+1)! == -1 (mod u+2) if and only if (u+2) is prime.

In the multiplicative group of integers modulo p, each nonzero element has an inverse.
So multiplying by the inverse of (u+1):
(u+1)-1(u+1)! == (u+1)-1(-1) (mod u+2) if and only if (u+2) is prime.

For the LHS, the first 2 factors reduce to 1 because (u+1)-1(u+1) = 1
and 1 is the identity element of the group so the LHS becomes u!

For the RHS, we use the fact that u+1 == -1 (mod u+2) so that the RHS becomes
(u+1)-1(u+1) which we saw above equals 1. So

u! == 1 (mod u+2) if and only if (u+2) is prime.

QED (the name of the variable doesn't matter)

Equivalently we can put back the substitution u=p-2 and we have the other relation

(p-2)! == 1 (mod p) if and only if p is prime.

For an application of this theorem, we can use it to test for twin primes.

In pseudocode

for the first 50 odd primes: print p, mod(p!, p+2)

In WxMaxima
p:2\$for c:1 thru 50 do block(p:next_prime(p),print(p,mod(p!,p+2)));

This code produces a residue of 1 when p is the first member of a twin prime, and 0 otherwise.
As a derivative of Wilson's Theorem, it is just as impractical.
Basically it just avoids the 2 multiplications that would take (p-1)! to (p+1)!

Message boards : General discussion : An Impractical Test for Twin Primes