# $n^n\equiv 1\pmod M\implies n\equiv 1\pmod M$

elementary-number-theory

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.

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$$.