Show that for every natural number $ a\ge 3, $ there are infinitely many natural numbers $ n $ such that $ a^n\equiv 1\pmod n . $ Does this hold for $ n=2? $
Problem
Source: Romanian TST 1978, Day 4, P1
Tags: number theory, modular arithmetic
30.09.2018 23:02
For $a = 2$ it is an open problem there are like $3$ or $4$ examples known(and i believe that situation is the same for any even $a$). For odd $a$ powers of $2$ fit ($\varphi(2^{k}) = 2^{k - 1}$).
22.10.2024 20:38
Here's a complete proof. First, for $a=2$, I show $n\mid 2^n-1$ iff $n=1$. Suppose $n>1$ and let $p$ be the smallest prime divisor of $n$. Then $p\mid 2^n-1$ and $p\mid 2^{p-1}-1$ (Fermat) collectively yield $p\mid 2^{(n,p-1)}-1=1$ as $(n,p-1)=1$ due to choice of $p$. A contradiction. Next, let $a\ge 3$. If $a$ is odd, any $n=2^k$ works due to Euler's theorem. Now, let $a\ge 3$ be even. I inductively construct an infinite sequence $(a_n)_{n\ge 1}$ along which $a_n\mid a^{a_n}-1$. For $n=1$, take $p$ as any odd prime $p\mid a-1$ and notice $p\mid a^p-1=(a-1)(a^{p-1}+\cdots+1)$. Now, $v_p(a^p-1)=v_p(a-1)+1$, so $p\mid\mid a^{p-1}+\cdots+1$ and that $a^{p-1}+\cdots+1>p$. Take $d={\rm gcd}(a-1,a^{p-1}+\cdots+1)$. Note that $a\equiv 1\pmod{d}$ so $a^{p-1}+\cdots+1\equiv p\pmod{d}$. Thus, there is a prime $q$, not dividing $a-1$, such that $q\mid a^p-1$. Set $a_2 = qa_1$ and notice $pq\mid a^{pq}-1$. Next for $u=a^p$, consider $u^q-1=(u-1)(u^{q-1}+\cdots+1)$. Check that $v_p(a^{pq}-1) = v_p(a^p-1)+v_p(q) = v_p(a^p-1)$ so $p\nmid u^{q-1}+\cdots+1$. Furthermore, $v_q(u^{q-1}+\cdots+1) = 1$ and that ${\rm gcd}(u-1,u^{q-1}+\cdots+1)\mid q$. Reasoning similarly, there is a prime $r\ne p,q$ such that $r\mid u^{q-1}+\cdots+1$, so it suffices to set $a_3=pqr$. Continuing in this manner, we obtain an infinite increasing sequence.