Problems & Puzzles: Conjectures

Conjecture 100.  Rn = An / Gn

Alain Rochelli sent the following conjecture.

Any odd integer except 1 can be written q=2*n+1 with n>0.

Let An be the value of Euler totient function applied to 2*n+1. E.g.: An = phi(2*n+1).

Cf. OEIS A000010, A037225 and A363700.

Let Gn be the greatest common divisor of An and 2*n. E.g.: Gn = gcd(An,2*n).

Noting Rn = An / Gn (Rn is an integer), we conjecture:

I) If Rn = 1 then 2*n+1 is prime.

II) If Rn > 2 then 2*n+1 is composite.

III) Rn is never equal to 2 (i.e., An # 2*Gn).

Q) Can you get an explanation (or proof) of this?

During the week 1-7 July, 2023 contributions came from Alessandro Casini.


Alessandro wrote:

Here some comments about the conjecture.

  1. This is essentially the Lehmerís totient problem, a 90 years oldís open problem. So far itís known that a hypothetical counterexample must be an odd Carmichael number, hence squarefree, with at least 14 prime factors, and enormously much more if 3 is one of the divisors.
  2. This is surely true, since a prime integer must have Rn=1.
  3. This is equivalent to finding a k such that phi(k)/2 is a divisor of k-1 but phi(k) isnít, thus if M*phi(N)=2(N-1) has an odd solution with odd M. Since M=1 is impossible, it must be at least 3. I canít prove or disprove the existence of a solution. By a reasoning similar to Lehmerís original with however much more computations (that 2 is very annoying), it can be shown that N must be a squarefree number with at least 8 prime factors, and then 2^7 divides N-1. Moreover if 3 is a factor, than it must have 9 prime factors; instead a solution with M=7 has at least 158 prime factors and itís coprime to 21.



Records   |  Conjectures  |  Problems  |  Puzzles