During the week 12-18 Feb. 2023, contributions came from Alain Rochelli,
Emmanuel Vantieghem, Oscar Volpatti
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
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.
The conjecture by Alain
Rochelli is true.
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
As 4 == 1 mod 3, prime 3 actually divides 4^q-1 for every
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.