Here is my attempt.

Suppose we have $a^m \equiv 1 \pmod n$ and assume that $ord(a,n) = k$ (order of $a)$ and so since $k = ord(a,n)$ it follows that $k \leq m$ .
Now if $k = m$ then we are done but now assume that $k < m$ and it also follows that $a^k \equiv 1 \pmod n$. Hence we do have that $a^m \equiv a^k \pmod n$ which means that $n \mid a^m - a^k$ and so $n | a(a^{m-1} - a^{k-1})$, however since $gcd(a,n) = 1$ then we know that $n \mid a^{m-1} - a^{k-1}$ and eventually since we have $k < m$ we can keep doing that until we have $n \mid a^{m-k} - 1$.

but how do I conclude form here that $k \mid m$ or is there another simpler method ?

For the converse statement (other implication , it's trivial)

Suppose that $ ord(a,n) \mid m$

so again let $k = ord(a,n)$ then there exists an integer $t$ such that $kt = m$

then since $a^k\equiv 1 \pmod n$ then $a^{kt} \equiv 1 ^{t} \pmod n$ and so $a^m \equiv 1 \pmod n$ . So I am just stuck in the first implication


If $k<m$ apply Euclidean division to write $m=qk+r$. Then $a^m\equiv a^r\equiv1$, but $r<k$, and this implies $r=0$.


The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:a^n \equiv 1\:$ is closed under positive subtraction, i.e.

$$\rm \color{#0A0}n>\color{#C00}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#0A0}{a^n} \equiv a^{n-m}\, \color{#C00}{a^m} \equiv a^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$

Thus, by theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \! $ := order of $\rm\,a.$

Theorem $\ \ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\ n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$

Proof $\ $ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \, $

See here for elaboration on the Theorem, and for more on the key innate structure see this post on order ideals and denominator ideals.


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.