A Hypothesis about Euler's Totient Theorem

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

• Thank you! Then how can I prove it if $k$ is the smallest one? – XYZ Jul 19 at 4:47
• Hint: divide $\phi(n)$ by $k$ to give quotient $q$ and remainder $r$. Prove that $r$ is zero. – David Jul 19 at 5:46
• @XYZ See here for a conceptual proof. – 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$$.

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

• 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).\$ – Bill Dubuque Jul 19 at 13:25

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.