Problems & Puzzles: Conjectures

Conjecture 102.  Conjecture related to A359387

Alain Rochelli sent the following conjecture, on Feb 19, 2023


In Puzzle 1122 OEIS A005385, we have proven that, for any Safe prime p>7, A(p) = (2^(p-1) - 1) / 3 has as smallest prime factor p.

OEIS A359387 is relative to primes p such that the smallest prime factor of A(p) is p. Of course, all Safe primes (> 7) are included in A359387.

Let q be the A359387 primes which are not Safe primes. The first suitable primes q are as follows :

443, 647, 1847, 2243, 2687, 2699, 6263, 6563, 7487, 7583, 8627, 8663, 9419

For any value of q, it is conjectured that q = 2*u*v + 1 where u and v are distinct primes not in A005384 = non-Sophie Germain primes (cf. A053176).

For example :

443 = 2*13*17 + 1 (13 and 17 in A053176)

647 = 2*17*19 + 1 (17 and 19 in A053176)

1847 = 2*13*71 + 1 (13 and 71 in A053176)

2243 = 2*19*59 + 1 (19 and 59 in A053176)

2687 = 2*17*79 + 1 (17 and 79 in A053176)

- - -

9419 = 2*17*277 + 1 (17 and 277 in A053176)

Q : Can you get an explanation of this or find a counterexample ?


During the week from 7-13 Oct 2023, Contributions came from Oscar Volpatti, Alessandro Casini, Emmanuel Vantieghem

***

Oscar wrote:

Conjecture 102 is false.
These primes are the first ten counterexamples:

41039 = 2*17^2*71+1
72923 = 2*19^2*101+1
1516583 = 2*31*61*401+1
1902347 = 2*31*61*503+1
2039243 = 2*31^2*1061+1
2235287 = 2*31^2*1163+1
2638907 = 2*31^2*1373+1
2984867 = 2*31^2*1553+1
3817259 = 2*61*67*467+1
4398467 = 2*31*61*1163+1

***

Alessandro wrote:

The conjecture, such as it is stated, is incorrect. In fact, q = 41039 = 2 * 17^2 * 71 + 1 is in A359387 but has the 17 squared. Moreover, it isn’t even mandatory to have only two distinct odd prime factors u and v, although quite rare. Indeed, there are only four q < 5M with 3 distinct odd primes, with 1516583 the smallest. However, the fact remains that the prime factors cannot be Sophie Germain primes. Therefore, the conjecture can be restated as follows:

If q is a no-safe prime in A359387, then q = 2*C + 1, where C is a product of non-Sophie Germain primes.

This statement is actually always true, here’s the proof.

Since q = 11 (mod 12), q-1 cannot be divisible by 4, so C = (q - 1) / 2 is an odd composite cofactor. Let’s assume C is divisible by a Sophie Germain prime p. By Fermat’s theorem, 2 ^ (2p) = 1 (mod 2p + 1) and raising to the appropriate power we get that 2p + 1 divides 2 ^ (q-1) - 1. But 3 < 2p + 1 < 2C + 1 = q, hence q isn’t in A359387, absurd.

In addition, It isn’t important that p is a prime number, just that 2p+1 is. Therefore, 2*d+1 must be composite for every proper divisor d of C.

Lastly, C cannot be a square, else q = 2C+1 will be a multiple of 3.

I wonder if it is possible to show further limitations on their shape.

 

***

Emmanuel wrote:

I think this conjecture has been settled as "False" in your Conjecture 96.

There I gave many counterexamples of type  2*p*r*s +1 and  2*(p^2)*r + 1 (p,r s, primes with  p < r < s).

(I conjectured that there would be no others

but Oscar Volpatti also gave an example of type  2*p*q^2 + 1  and  2*q^3 + 1.


 

Recently, I found a counterexample  q = 5165748299123 = 2*(613^3)*11213 + 1.

But, a double check is wanted here.

 

***

Records   |  Conjectures  |  Problems  |  Puzzles