Problems & Puzzles: Puzzles

Puzzle 1122 OEIS A005385   Alain Rochelli sent the following nice puzzle: Related to OEIS A005385, Safe primes are those such that (p-1) / 2 is also prime. It is conjectured that, for p>7, A(p) = (2^(p-1) - 1) / 3 never has a prime factor < p. It's quite easy to check up to 10^6 and I think I got a proof of that. This conjecture is original to me. It is not mentioned in A005385. Q1 : Can you verify by computation, as big as is reasonable, that this is true? Q2 : Can you get an explanation (proof) of this?

---

During the week 12-18 Feb. 2023, contributions came from Alain Rochelli, Emmanuel Vantieghem, Oscar Volpatti

***

Alain wrote:

At the moment, I couldn't get a self-supporting proof so I will use the information available on the Net.

Contrary to the text of the Puzzle, let q be a Safe Prime (> 7) and then p = (q-1) / 2 is also prime and called corresponding Sophie Germain prime (cf. A005384).

The conjecture notation is then as follows:

A(q) = (2^(q-1) - 1) / 3 never has a prime factor < q.

3*A(q) = (2^((q-1)/2) – 1) * (2^((q-1)/2) + 1) = (2^p – 1) * (2^p + 1)

It follows that:

A(p) = M(p) * G(p) where M(p) = 2^p – 1 and G(p) = (2^p + 1) / 3

We have then to prove that for any Sophie Germain prime p (p>=5) there is no prime factor < 2*p+1 in the factorization neither of M(p) nor in that of G(p).

M(p) is the Mersenne number (cf. A001348) corresponding to the prime p and it is well known that any prime factor of M(p) is of the form 2*k*p+1 with k>1. Also, the smallest possible prime factor of M(p) is 2*p+1.

Sophie Germain primes (A005384) are made up of the union of Lucasian primes (A002515) and Sophie Germain primes that are not Lucasian primes (A103579).

In OEIS A103579, it is mentioned : “For n > 1, the prime 2*a(n) + 1 is the smallest prime divisor of (2^a(n) + 1)/3. - Emmanuel Vantieghem, Aug 12 2018”. Also, in this case, there is no prime factor < 2*p+1 in the factorization of G(p).

We then have to prove that for all Lucasian primes (A002515, p > 5) there is no prime factor < 2*p+1 in the factorization of G(p).

Lucasian primes: p == 3 (mod 4) with 2*p+1 prime.

In OEIS A002515, it is mentioned : “2*p+1 divides A000225(p), the p-th Mersenne number. – Lekraj Beedassy, Jun 23 2003”.

In this case, I easily checked up to 10^6 that 2*p+1 divides M(p) well but also that there is no prime factor < 2*p+1 in the factorization of G(p).

We can then draw the conclusion that for all Sophie Germain Primes p, A(p)=G(p)*G(p) has as smallest prime factor q = 2*p+1.

***

Emmanuel wrote:

***

Oscar wrote:

The conjecture by Alain Rochelli is true.

Proof.
Choose a safe prime p>7, such that integer q = (p-1)/2 is prime too, with q>3.
Consider Mersenne number M(p-1) = 2^(p-1)-1 = 2^(2*q)-1 = 4^q-1, clearly odd and coprime with 4.
Let f be an odd prime factor of M(p-1), and let x be the multiplicative order of 4 mod f;
by Lagrange's theorem, x divides phi(f) = f-1.
Congruence 4^q == 1 mod f holds, so x also divides prime q, hence x = 1 or x = q.
Case x = q.
Odd prime q divides f-1; 2 divides f-1 too, as f is odd; hence f = 2*q*k+1, for some positive integer k.
For k = 1 we obtain the smallest candidate f = 2*q+1 = p, which actually divides M(p-1) by Fermat's little theorem.
Case x = 1.
Odd prime f divides 4^1-1 = 3; the only candidate prime is f = 3 itself.
As 4 == 1 mod 3, prime 3 actually divides 4^q-1 for every integer q.
The multiplicative order of 4 mod 9 is 3, so 9 also divides 4^q-1 iff 3 divides q;
the only safe-prime case is q = 3, p = 7, M(6) = 63 = 3^2*7.

Therefore, for a safe prime p>7, number A(p) = (2^(p-1)-1)/3 is an integer coprime with 3;
its prime factors are of the form f = 2*q*k+1 and they are never smaller than p itself.
QED.

***