9
$\begingroup$

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!

$\endgroup$
6
  • 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$ Nov 14 '20 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$ Nov 14 '20 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 '20 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 '20 at 8:50
  • 2
    $\begingroup$ @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$. $\endgroup$ Nov 14 '20 at 20:11
9
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\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$ Nov 15 '20 at 6:17
  • $\begingroup$ Yes, that’s correct. $\endgroup$ Nov 15 '20 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.