$n^n\equiv 1\pmod M\implies n\equiv 1\pmod M$ Determine all $M$, such that for $n\ge 2$, $n^n\equiv 1\pmod M\implies n\equiv 1\pmod M$.
I’ll use the term $M$ is good if the above statement holds $\forall n\ge 2$, and bad otherwise.
I don’t know how to solve this in general but I’ve proved that if $M$ is a prime then the statement is false,
Let $M$ be a prime, set $n=\phi(M)=M-1$ then we know $$n^n\equiv 1\pmod M$$
but clearly $n\not \equiv 1\pmod M$ because $M$ is bigger than $n$. I guess that this is also applicable to odd $M$ but I don’t know how to prove it.
 A: The result is that $M$ is good if and only if every prime divisor of $\phi(M)$ is also a divisor of $M$. This is the sequence A151999 on OEIS.
"If" part:
Suppose that every prime divisor of $\phi(M)$ is also a divisor of $M$. Let $n$ be a positive integer such that $n^n \equiv 1\pmod M$ and let $d$ be the order of $n$ mod $M$. It follows that $d \mid n$ and also $d \mid \phi(M)$. But clearly $n$ is prime to $M$, and hence is prime to $\phi(M)$ because of the assumption on $M$. This implies $d = 1$ and therefore $n \equiv 1\pmod M$.
"Only if" part:
Suppose that there exists a prime divisor $p$ of $M$ and a prime number $q$ such that $q \mid p - 1$ but $q$ is prime to $M$. We want to show that $M$ is bad.
Write $M = p^r N$ with $N$ prime to $p$. We know that the multiplicative group $\Bbb Z/p^r\Bbb Z$ is cyclic and has order disivible by $q$, therefore there exists $x$ such that $x^q \equiv 1 \pmod{p^r}$ and $x \not\equiv 1 \pmod {p^r}$.
By Chinese remainder theorem, we can find $n$ such that $n \equiv 0 \pmod q$, $n \equiv x \pmod {p^r}$ and $n \equiv 1 \pmod N$.
Clearly $n \not\equiv 1 \pmod M$. On the other hand, we have $n^n \equiv (x^q)^{n/q} \equiv 1\pmod{p^r}$ and also $n^n \equiv 1 \pmod N$, thus $n^n \equiv 1 \pmod M$.
A: Certainly all odd $M$ are "bad", because
$$
(M-1)^{M-1} \equiv (-1)^{M-1} = 1
$$
(mod $M$), while $(M-1)\neq 1$ (mod $M$).
