Maximum exponent in the prime factorization of n

The question

conjecture1. Are there composite numbers $n>4$ such that $n\equiv a(n)(\mathrm{mod}\varphi (n))$?

• Thomas Ordowski, Dec 02 2019

This question is equivalent to Lehmer's totient problem LehmerTotient.lehmer_totient; a positive answer here falsifies the universal statement asked about in Erdos828.erdos_828.variants.lehmer_conjecture. Any composite $n$ with $\varphi (n)\mid n-1$ is squarefree, so $a(n)=1$ and the condition here holds. Conversely, let $n>4$ be composite with $\varphi (n)\mid n-a(n)$ and $e=a(n)\ge 2$, and pick $p$ with $p^e\mid n$. Then $p^{e-1}\mid \varphi (n)\mid n-e$ and $p^{e-1}\mid n$, so $p^{e-1}\mid e$, which forces $p=2$ and $e=2$. Now $n=4m$ with $m$ odd and squarefree, and $2\varphi (m)\mid 4m-2$ makes $\varphi (m)$ odd, so $m=1$ and $n=4$. Hence $e=1$ and the condition is $\varphi (n)\mid n-1$.

conjecture2. Are there odd numbers $n$ such that $a(n)>1$ and $n\equiv a(n)(\mathrm{mod}\lambda (n))$? (Equivalently, odd numbers $n$ such that $a(n)>1$ and $b^n\equiv b^{a(n)}(\mathrm{mod}n)$ for all $b$.)

• Thomas Ordowski, Dec 02 2019

conjecture3. Are there odd numbers $n$ such that $a(n)>1$ and $n\equiv a(n)(\mathrm{mod}{\mathrm{ord}}_n(2))$? (Equivalently, odd numbers $n$ such that $a(n)>1$ and $2^n\equiv 2^{a(n)}(\mathrm{mod}n)$.)

• Thomas Ordowski, Dec 02 2019

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.OEIS.«51903» (3 statements). answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem conjecture1 :
    answer(sorry) ↔ ∃ n : ℕ, 4 < n ∧ ¬ n.Prime ∧ n.totient ∣ (n - a n)

theorem conjecture2 :
    answer(sorry) ↔ ∃ n : ℕ, Odd n ∧ 1 < a n ∧ ∀ b : ℕ, b ^ n ≡ b ^ (a n) [MOD n]

theorem conjecture3 :
    answer(sorry) ↔ ∃ n : ℕ, Odd n ∧ 1 < a n ∧ 2 ^ n ≡ 2 ^ (a n) [MOD n]

What counts as progress

• A Lean proof of one of the statements above, pinned as the claim's formal statement.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

• A051903

Source and licence

Imported from Formal Conjectures (OEIS), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.