PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 1002
ID: 55391
Credit: 879,355,065
RAC: 316,764
Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2022 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (6,055,323)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,443,837)PPS LLR Sapphire: Earned 20,000,000 credits (33,758,824)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (44,987,733)SR5 LLR Turquoise: Earned 5,000,000 credits (6,205,694)SGS LLR Ruby: Earned 2,000,000 credits (3,627,819)TRP LLR Turquoise: Earned 5,000,000 credits (7,078,152)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (457,897,035)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,165,888)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,071,454)AP 26/27 Turquoise: Earned 5,000,000 credits (6,798,063)GFN Emerald: Earned 50,000,000 credits (57,113,430)WW Ruby: Earned 2,000,000 credits (2,072,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
Message 153187 - Posted: 11 Jan 2022 | 5:18:22 UTC
Last modified: 11 Jan 2022 | 6:09:57 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)!

Post to thread

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.54, 2.83, 2.85
Generated 4 Jul 2022 | 2:05:39 UTC