Problems & Puzzles: Puzzles

Puzzle 1140 Test for Sophie Germain primes Davide Rotondo sent the following puzzle: CONSIDER A PAIR OF NUMBERS (n,2n+1), n IS A PRIME OF SOPHIE GERMAIN IF (n-1)!^2 + 6n == 1 (mod n(2n+1)). Q. False or truth?

---

During the week 19-25 August, 2023 contribution came from Alessandro Casini, Ken Wilke, Adam Stinchcombe, Emmanuel Vantieghem

Alessandro wrote:

the statement is true but for n=2.  Here’s the proof. The modulo n*(2n+1) can be split in mod n and mod 2n+1. The former congruence is satisfied iff n is prime, as a consequence of Wilson’s theorem. About the latter, first of all it can be rearranged as (n-1)!^2 == 4 (mod 2n+1). It’s easy to see that n is the modular inverse of -2, hence n^2 is 4^(-1). Therefore, it’s equivalent to n!^2 == 1 (mod 2n+1). In this case one can exploit the variant of the Wilson’s theorem which states that n!^2 == (-1)^(n+1) (mod 2n+1) if 2n+1 is prime and == 0 otherwise. Therefore, together with the first one, the second congruence is satisfied iff n is an odd prime (here enters the exclusion of n=2) and 2n+1 is prime too, i.e. n is an odd Sophie Germain prime.

Needless to say, this test in practice is quite infeasible.

***

Ken wrote:

Solution: The numbers n and 2n+1 are Sophie Germaine primes if both n and 2n+1 are
prime. The numbers 2 and 5 form the first pair of Sophie Germaine primes. Then the
condition (n-1)!^2 + 6n == 1 (mod n(2n+1)) is equivalent to the condition that both of the
congruences (n-1)!^2 + 6n == 1 (mod n)and (n-1)!^2 + 6n == 1 (mod (2n+1)) being true
simultaneously. For n =n 2, the first congruence implies (1!)^2 +6*2 ==13==1 (mod 2)
which is correct. However, the second congruence implies (1!)^2 + 6*2 ==13==3 (mod 5)
which is false. Hence the criterion as posed is false.
An improved statement of the criterion would be:
CONSIDER A PAIR OF NUMBERS (p, 2p+1), p IS A PRIME OF SOPHIE GERMAIN IF
(p-1)!^2 + 6p == 1 (mod p(2p+1)) where p is an odd prime.
Proof: The stated condition (p-1)!^2 + 6p == 1 (mod p(2p+1)) is equivalent to the
condition that both of the following congruences
(p-1)!^2 + 6p == 1 (mod p) (1) and
(p-1)!^2 + 6p == 1 (mod (2p+1)) (2)
are true simultaneously.
Consider congruence (1) where p is an odd prime (or even 2).Then by Wilson’s Theorem,
(p-1)! ==-1 (mod p), so congruence (1 becomes (-1)^2 + 6*0 ==1 (mod p) which proves
the validity of congruence (1).
Next consider the quantity (p-1)!^2 (mod (2p+1)) where p is an odd prime. Then for j = 1
to p-1, we have 2p+1-j==(-1) (mod 2p+1). Then (p-1)!^2 (mod (2p+1)) becomes
(p-1)!^2 (mod(2p+1))== 1*2* …*(p-1)*(p+2)*(p+3)…*(2p)*{(-1)^(p-1)} (mod (2p+1)
Then by using Wilson’s Theorem, we obtain:
p*(p-1)*(p-1)!^2 == -1==2p(mod (2p+1) (3)
Now let y be a nonzero residue (mod (2p+1)) such that y=={(p-1)!^2 + 6p}
(mod(2p+1)).Then by congruence (3),

p*(p+1)*y == p*(p+1*){(p-1)!^2 + 6p}== {2p + 6*p^2*(p+1)} =={2p
+(2p)*(3p)*(p+1)} ==p*{2-3*(p+1)} ==p*(-3p-1)==p*(p+1) (mod (2p+1)
Hence y==1 (mod (2p+1)) which establishes congruence (2).
Finally since both congruences (1) and (2) are true when p is an odd prime, we have
(p-1)!^2 + 6p == 1 (mod p(2p+1)) where p is an odd prime and p and 2p+1 form a pair of
Sophie Germain primes.

***

Adam wrote:

You can check n=1 does not solve the equation.

 

I prove:  If n is composite then (n-1)!^2+6n is not congruent to 1 mod n.  Suppose n=s*t then s appears in one factor of (n-1)! and t appears in the other factor of (n-1)! (in case s=t) so (n-1)!^2=0 mod n  and 6n=0 mod n.    (n-1)!^2+6n is 0 mod n, and not 1.  
 

Next I prove:  If 2n+1 is composite then (n-1)!^2+6n is not congruent to 1 mod 2n+1. Write 2n+1=s*t.  Since 2n+1 is odd, the least factor of 2n+1 is greater than or equal to three and the largest factor is less than or equal to (2n+1)/3<n.  Once again s appears in one factor of (n-1)! and t appears in the other factor of (n-1)! so (n-1)!^2=0 mod(2n+1).  Mod 2n+1, 6n is congruent to 6n-3(2n+1) = -3. So (n-1)!^2+6n is 0+(-3) = -3 mod (2n+1).  This is only 1 if 2n+1 divides 4 which it doesn't.

 

If (n-1)!^2+6n is 1 mod n(2n+1) then (n-1)!^2+6n is 1 mod n so n is prime.  Also, if (n-1)!^2+6n is 1 mod n(2n+1) then (n-1)!^2+6n is 1 mod 2n+1 so 2n+1 is prime.
 

Consequently, n is a prime of Sophie Germain type

***

Emmanuel wrote:

If I understood well, you want us to examine the truth/falseness of the statement :
   If  the congruence
     (n-1)!^2 + 6n == 1 mod n(2n+1)   (*)
   holds  then  n  is a Sophie Germain prime.

My answer is : True !
Proof :
When (*) holds then we have :
     (n-1)!^2 + 6n == 1 mod n).
  If  q  would be a prime divisor of   n  such that  1 < q < n  then we would have :
   0 == 1 mod q,
  impossible.  Thus, n  is prime.
From (*)  follows also :
     (n-1)!^2 + 6n == 1 mod (2n+1)   (**)
  If  q  would be a prime divisor of   2n+1  such that  1 < q < 2n+1  then  we would have :
     1 < q <= n-1  and thus : (n-1)!^2 == 0 mod q.
  We then have also : 6n = 3(2n+1) - 3 == -3 mod q, which finally would lead to :
     -3 == 1 mod q.
  This is also impossible for  q  must at least be odd.
Thus, (*)  implies the primality of  n  and  2n+1, QED.

I also could not resist to examine the truth of the converse. I. e. :
   If  n  is a Sophie Germain prime, then the congruence (*)  holds.
Here, we see immediately that this assertion is false since we have :
   n = 2  is a Sophie Germain prime, but  1!^2 + 12 !== 1 mod 10.
A numeric search for other counterexamples revealed no more such primes !
Finally, I could prove prove the following statement :

  "n  is an odd Sophie Germain prime" implies  "(n-1)!^2 + 6n == 1 mod n(2n+1)".

Proof.
Assume  n  is an odd Sophie Germain prime.
From the primality of  n  we deduce :
   (n-1)!^2 == 1 mod n (Wilson's theorem)  and thus also :
   (n-1)!^2 + 6n == 1 mod n.    (***)
From the primality of  p = 2n + 1 we deduce :
   (2n)!^2 == -1 == 2n mod p (Wilson's theorem).
But :
   (2n)!^2 = 1*...*(n-1)*n *(n+1)*...*(n+n)
                = (n-1)!*n*(n+1)*(p-(n-1))*...*(p-1)
                == (n-1)!*n*(n+1)*((n-1)!)*(-1)^(n-1)*
                == ((n-1)!^2)*n*(n+1)   (we use the oddness of  n)
Thus : ((n-1)!^2)*n*(n+1) == 2n mod p
Since  n  and  p  are coprime, we may cancel  n  in both sides, which gives :
   ((n-1)!^2)*(n+1) == 2 mod p
But, we have : 2(n+1) == 1 mod p.  Multiplying both sides of the preceding leads to :
   (n-1)!^2 == 4 mod p.
Together with  6n === -3 mod p  this leads to  
    (n-1)!^2 + 6n == 1 mod 2n + 1   (****).
 From the two congruences (***)  and (****) we deduce easily (*),QED.

***