Euler's totient theorem states that if $a$ and $n$ are coprime positive integers, then: $$a^{\varphi(n)} \equiv 1\;(\mathrm{mod}\;n)$$ So if $k$ is a given positive integer, which satisfies: $$\begin{cases} a^k \equiv 1\;(\mathrm{mod}\;n)\\ k\leqslant \varphi(n) \end{cases}$$

Does it necessarily hold that $k\,|\,\varphi(n)$?


No. For example $n=16$, $\phi(n)=8$, $a=9$, $k=6$. You can confirm that $$9^6\equiv1\pmod{16}\quad\hbox{but}\quad 6\not\mid8\ .$$

However if $a$ is given and $k$ is the smallest positive integer such that $a^k\equiv1\pmod n$, then it is true that $k\mid\phi(n)$. In the above example the smallest possible value of $k$ would have been $2$, not $6$.

  • 1
    $\begingroup$ Thank you! Then how can I prove it if $k$ is the smallest one? $\endgroup$ – XYZ Jul 19 at 4:47
  • 4
    $\begingroup$ Hint: divide $\phi(n)$ by $k$ to give quotient $q$ and remainder $r$. Prove that $r$ is zero. $\endgroup$ – David Jul 19 at 5:46
  • $\begingroup$ @XYZ See here for a conceptual proof. $\endgroup$ – Bill Dubuque Jul 19 at 13:06

No... This doesn't hold true if you take $n=16$ and $a=9$. You may easily check that $$9^6\equiv1\pmod{16}\quad\hbox{but}\quad 6\not\mid8\ .$$

Indeed, your assertion holds good if you are taking $k$ to be the order of $a$ in mod $n$. To find the minimum value of $k$, you should use an even stronger result which is Carmichael's Theorem; it states that the minimum value of $k$ is $\lambda(n)$ if $\gcd(a,n)=1$.

enter image description here Note: Value of Carmichael Function does not depends on $a$ and obviously $\lambda(n)\mid \phi(n)$ .

  • $\begingroup$ Why do you think Carmichael lambda is relevant here? Rather, it seems what the OP seeks is the order of $a,\ $ which generally is not the same as $\lambda(n).\ $ $\endgroup$ – Bill Dubuque Jul 19 at 13:25


Say $n=15$. Then $\varphi (15)=8$. And $(4,15)=1$. But $4^{6}=(4^2)^3\cong1\pmod{15}$. And $6\not\mid8$.

Write $\varphi (n)=kq+r\,,r\lt k$. Then $1\cong a^{\varphi (n)}\cong a^r$. So if $k$ is the least such, then yes.


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.