# Conjecturing when $M$ is good

We say an integer $$M>1$$ is good if whenever $$n^n \equiv 1 \mod M$$ then we also have $$n \equiv 1 \mod M$$ and bad otherwise, for any integer $$n\ge 2$$ . Prove that all odd $$M$$ are bad. Find all good $$M$$ .

My progress: First taking example, we get Among $$M \in \{2,3,4,5\}$$ $$, 2,4$$ are good.

Now for all odd $$M$$ , consider $$(M-1)^{M-1}$$ , note that $$(M-1)^{M-1}\equiv -1^{M-1}\equiv 1 \mod M-1$$ , since $$M-1$$ is even .But $$M-1 \equiv -1 \mod M$$. This proves the first part.

For second part I thought that it would be true for all even M, but then $$9^9\equiv 1 \mod 14$$ . However I got $$2,4,6,8,10,12$$ good.

Also $$M=42$$ is good too . Here's the proof showing $$M=42$$ is good:

If $$n^n\equiv 1\mod 42 \implies n^n\equiv 1\mod 2 \implies n$$ is odd . Also we have $$n^n\equiv 1\mod 6 \implies n\equiv 1\mod 6$$. Now for $$n^n \equiv 1 \mod 7 \implies n \equiv \text{1 or 6} \mod 7$$. If $$n=6 \mod 7$$ , then by CRT $$n\equiv 13 \mod 42$$ which is not possible as $$13^{13} \equiv 13 \mod 42$$ ( Thanks! @Ross Millikan for correction )

I couldn't formulate a conjecture about when $$M$$ is $$good$$. Any hints? Thanks in advance!

• The problem statement is fine now, but if $n \equiv 1 \bmod 6$ and $n \equiv 6 \bmod 7$, then $n \equiv 13 \bmod 42$. As $13^{13} \equiv 13 \bmod 42$ you are fine. – Ross Millikan Nov 14 at 6:16
• MathJax hint: for multicharacter exponents, enclose them in braces, so 13^{13} gives $13^{13}$ compared to 13^13 which gives $13^13$ It works for fractions, subscripts, etc. – Ross Millikan Nov 14 at 6:24
• Note (from your example for 14) that $9^9 \equiv 1 \pmod{7}$, so I think $n \equiv 1, 6 \pmod{7}$ does not follow from $n^n \equiv 1 \pmod{42}$. 42 still seems good though. More generally, I think the solution to $n^n \equiv 1 \pmod{p}$ may be something $\pmod{p(p-1)}$ rather than something $\pmod{p}$. – xmq Nov 14 at 6:27
• Sequence is on OEIS: oeis.org/A239063 with no useful information (unless you consider the first 10000 terms useful) – player3236 Nov 14 at 8:50
• Upon further inspection, the above sequence is NOT the sequence you seek, since for $2 \le n \le 46$, $n^n \not \equiv 1 \pmod {46}$, but $55^{55} \equiv 1 \pmod {46}$. Therefore it appears that this sequence is not on the OEIS. – player3236 Nov 14 at 12:45

Theorem: Let $$\phi(M)$$ be the Euler totient value of $$M$$. Then $$M$$ is good if and only if $$\operatorname{sqrf}(\phi(M))\mid M$$, where $$\operatorname{sqrf}(\cdot)$$ denotes the squarefree part.
For the “if” part, this follows because given $$n\not\equiv 1\pmod M$$ but coprime to $$M$$, then $$\operatorname{ord}_M(n)>1$$; however, $$n^n\not\equiv 1\pmod M\,,$$ because otherwise, we would have that $$\operatorname{ord}_M(n)\mid n$$ whereas $$\gcd(n,\phi(M))=1$$.
For the “only if” part, suppose $$p\mid\phi(M)$$ but $$p\nmid M$$. Thanks to Cauchy’s Theorem (see https://en.wikipedia.org/wiki/Cauchy%27s_theorem_(group_theory)) we can find a natural number $$m$$ such that $$\operatorname{ord}_M(m)=p$$. Now let $$v:= \operatorname{ord}_M(p)$$ and define $$n:=p^vm$$. Clearly $$n\not\equiv 1\pmod M$$; however, $$n^n=(p^vm)^{p^vm}= p^{v(p^vm)}m^{p^vm}\equiv 1\pmod M\,,$$ which completes the proof.