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$ Commented Nov 14, 2020 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$ Commented Nov 14, 2020 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
    Commented Nov 14, 2020 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
    Commented Nov 14, 2020 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$ Commented Nov 14, 2020 at 20:11

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .