Let $a$ and $n$ be integers with $n>0$. Show that the additive order of $a$ modulo $n$ is $\frac{n}{\gcd(a,n)}$.

Question

Let $a$ and $n$ be integers with $n>0$. Show that the additive order of $a$ modulo $n$ is $\frac{n}{\gcd(a,n)}$.

attempt: Let $a$ and $n$ be integers with $n>0$. Let $m=\frac{n}{\gcd(a,n)}$. Then, \begin{equation*} ma = \left(\frac{n}{\gcd(a,n)}\right)a = n\left(\frac{a}{\gcd(a,n)}\right) \equiv 0 \pmod{n}. \end{equation*} Since $d=\gcd(a,n)$ is the greatest positive integer such that $d\mid a$ and $d \mid n$, then $m$ is the smallest positive integer such that $n \mid ma$.

Hence, $m$ is the additive order of $a$ modulo $n$.

Am I true?

Answer 1

A bit more constructively. The order of $\bar a \in \Bbb Z/n\Bbb Z$ is by definition the least positive integer, say $o(\bar a)$, such that $o(\bar a)\bar a=\bar 0$. But, $o(\bar a)\bar a=\overline{o(\bar a)a}$, and hence:

\begin{alignat}{1} o(\bar a)\bar a=\bar 0 &\iff \overline{o(\bar a)a}=\bar 0 \\ &\iff o(\bar a)a \equiv 0 \pmod n \\ &\iff o(\bar a)a=mn \end{alignat}

for some $m\in \Bbb Z$. Therefore, the order of $\bar a$ is the least positive integer of the form $n/(a/m)$, and it is then gotten when the denominator is the greatest divisor of $a$ which is also divisor of $n$, namely:

$$o(\bar a)=\frac{n}{\operatorname{gcd}(a,n)}$$

Answer 2

The additive order of $a$ modulo $n$ is the smallest positive integer $m$ such that $ma \equiv 0 \pmod{n}$.

Now, $ma = kn$ for some integer $k$. Then, $m = \frac{kn}{a}$.

Let $\gcd(a,n) = d$. Then, $m = k\frac{\frac{n}{d}}{\frac{a}{d}}$.

Since $\frac{a}{d}$ and $\frac{n}{d}$ are relative prime, then $\frac{a}{d} \mid k$. Hence, the order of $a$ is a multiple of $\frac{n}{d}$. Since the order must be minimum, then the order of $a$ is $\frac{n}{d}$.

Is the approach above true?