$n$ such that $ n^2 \mid \varphi(n)^{\varphi(n)} - 1 $. Can $n$ be a prime number $n>2$ or a Carmichael number?

Question

For all $n$ such that $\large n^2 \mid \varphi(n)^{\varphi(n)} - 1 $ with $\varphi()$ denotes Euler's totient function.

It can be shown that $n$ must be a cyclic number. That means $n$ is coprime to $\varphi(n)$.
Implying further that $n > 2$ is odd and squarefree.

Besides the two trivial solutions $n=1$ and $n=2$ OEIS states five nontrivial solutions below $10^{12}$:

$19043= 137 \cdot 139$,
$289627=13 \cdot 22279$,
$6674419= 571 \cdot 11689$,
$49865347= 7 \cdot 173 \cdot 41177$,
and
$185014655= 5 \cdot 7 \cdot 17 \cdot 310949 $.

As Carmichael numbers are also cyclic numbers, I tested the first $1,401,644$ of them below $10^{18}$ from a database. None of them gives a solution.

If $n$ is a prime number then $n^2 \mid (n-1)^{n-1} - 1$.
Hence $n$ must be a Wieferich prime to base $n-1$.

Can $n$ be a prime number $n>2$ or a Carmichael number?

Answer 1

Partial answer :

$n$ cannot be an odd prime.

Proof :

Let $p$ be an odd prime and denote $m:=p-1$. Then we have

$$m^m-1=\prod_{d\mid m} \Phi_d(m)$$

• We have $\Phi_1(m)=m-1=p-2$ , which is not divisible by $p$
• We have $\Phi_2(m)=m+1=p$

It remains to show that for $d>2$, $\Phi_d(m)$ cannot be divisible by $p$. First note $$\Phi_d(m)\equiv \Phi_{d}(-1)\mod p$$

Let $r$ be the radical of $d$ (product of the distinct prime factors of $d$). Using the well-known formula $\Phi_d(b)=\Phi_r(b^{d/r})$ , applied for $-1$ , we get $$\Phi_d(-1)=\Phi_r(\pm 1)$$ depending on the parity of $\frac{d}{r}$.

In the case $\Phi_d(-1)=\Phi_r(1)$ we have $\Phi_d(-1)=1$ or a prime factor of $r$ and hence of $d$.

So, let us assume $\Phi_d(-1)=\Phi_r(-1)$. We have $3$ cases :

• $r=2$ , then $\frac{d}{r}$ is even, hence $\Phi_d(-1)=\Phi_r(1)=2$
• $r$ even and greater than $2$. Then, $\Phi_r(-1)=\Phi_{r/2}(1)$ and $\frac{r}{2}>1$, so $\Phi_r(1)$ is either $1$ or a prime factor of $r$ and hence of $d$
• $r$ odd. Then $\Phi_r(-1)=\Phi_{2r}(1)=1$

In none of the cases $p$ divides $\Phi_d(-1)$, which completes the proof.

Answer 2

$n$ can't be a prime number $> 2$ because in the binomial expansion of
$(p-1)^{(p-1)} ~-~ 1$,

$p^2$ must divide all but the last term, and can not divide the last term, which is $\pm \binom{p-1}{p-2}p^1.$