4
$\begingroup$

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)$?

$\endgroup$
2

3 Answers 3

9
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you! Then how can I prove it if $k$ is the smallest one? $\endgroup$
    – XYZ
    Jul 19, 2019 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, 2019 at 5:46
  • $\begingroup$ @XYZ See here for a conceptual proof. $\endgroup$ Jul 19, 2019 at 13:06
3
$\begingroup$

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)$ .

$\endgroup$
1
  • $\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$ Jul 19, 2019 at 13:25
2
$\begingroup$

No.

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.

$\endgroup$

You must log in to answer this question.

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