# 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. Nov 14 '20 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. Nov 14 '20 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 '20 at 6:27
• Sequence is on OEIS: oeis.org/A239063 with no useful information (unless you consider the first 10000 terms useful) Nov 14 '20 at 8:50
• @SunainaPati Thanks for the updates. FYI, a somewhat more direct way to state your question is that an integer $M \gt 1$ is good if there exists a positive integer $n \not\equiv 1 \pmod{M}$ where $n^n \equiv 1 \pmod{M}$, else $M$ is bad. Also, for any prime $p$ and $1 \le k \le p - 1$, with $n = (p - 1)(p - k) = (p - k - 1)p + k$, then Fermat's little theorem gives $n^n \equiv \left(k^{p-1}\right)^{p - k} \equiv 1 \pmod{p}$. Thus, $n^n \equiv 1 \pmod{7}$ means $n$ can be congruent to $1$ through $6$, inclusive, $\mod 7$. Nov 14 '20 at 20:11

This is the complete solution.

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.

• nice one!!!! well.. we could have also defined M such for every prime p|M , we have q|M for each prime factor q of p-1 ( skipping the term square free ?) Nov 15 '20 at 6:17
• Yes, that’s correct. Nov 15 '20 at 6:45