[seqfan] A new look at the Lehmer's totient problem

[Tomasz Ordowski]

Dear SeqFans!

Let a(n) = phi(n) / gcd(phi(n), n-1).

(*) Conjecture: a(n) > 2 for every composite n > 6.
  Note: Checked only for Carmichael numbers n.
Are there no other counterexamples, for sure?

(**) Conjecture:
For each natural number k,
there are at most finitely many
Carmichael numbers n such that a(n) <= k.

(**) Question: Could this be true?

The probable number of such Carmichaels
is 0, 0, 1, 5, ? for k = 1, 2, 3, 4, 5.
For now, we have a database of
Carmichael numbers n < 10^18.
It's worth search all n < 10^21.

I am asking for comments.

Best regards,

Thomas Ordowski & Amiram Eldar
______________________
(*) By Lehmer's Conjecture, a(n) > 1 for every composite n.
https://en.wikipedia.org/wiki/Lehmer%27s_totient_problem
http://mathworld.wolfram.com/LehmersTotientProblem.html

P.S. Further. Let's define:
Carmichael numbers n such that a(n) is prime.
(**) Conjecture:
There are only finitely many such numbers?
Data:
n = 1729,
3069196417,
23915494401,
1334063001601,
6767608320001,
33812972024833,
1584348087168001,
1602991137369601,
6166793784729601,
?
a(n) = 3, 11, 421, 23, 43, 41, 11, 5, 43, ?
No more found for n < 10^18. Search all n < 10^21.

Thomas Ordowski (idea) &
Amiram Eldar (implementation)