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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Nov 14 at 6:16
  • 2
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Nov 14 at 6:24
  • 2
    $\begingroup$ 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}$. $\endgroup$ – xmq Nov 14 at 6:27
  • 1
    $\begingroup$ Sequence is on OEIS: oeis.org/A239063 with no useful information (unless you consider the first 10000 terms useful) $\endgroup$ – player3236 Nov 14 at 8:50
  • 1
    $\begingroup$ 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. $\endgroup$ – player3236 Nov 14 at 12:45

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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 ?) $\endgroup$ – Sunaina Pati Nov 15 at 6:17
  • $\begingroup$ Yes, that’s correct. $\endgroup$ – Jack LeGrüß Nov 15 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.