$gcd(i,n)=1 \iff n\nmid ik$ for all $1 \leq k \leq n-1$

Question

I am working on my homework and have come into a problem. I am relying on this fact to prove the statement:

"Let $a$ have order $n$ modulo $m$ and let $i$ denote an integer. Prove that $a^i$ has order $n$ modulo $m$ if and only if $gcd(i, n)=1$.

My intuition keeps telling me to use the division algorithm, but I can't see it.

Hints appreciated!

Answer 1

The easy way is to show that if the order of $a^i$ is $n$, then $\gcd(i,n)=1$. We see this since $(a^i)^{n/\gcd(i,n)}=1$.

For the other direction, we want to show that $\gcd(i,n)=1$ implies that the order of $a^i$ is $n$. Consider the contrapositive: show instead that if $a^i$ has an order different from $n$, then $\gcd(i,n)\neq1$.

Assume $a^i$ has an order $k\neq n$. Then $k$ must be a divisor of $n$ (as $(a^i)^n$ is still $1$). Also, we know that $ik$ is some multiple of $n$, which is to say, there is an integer $a$ such that $ik=an$. This gives $$ i=a\frac nk $$ Thus $\frac nk>1$ is a common divisor of $n$ and $i$.

Answer 2

let $(i,n)=k$ where $k>1$

Then $n|i\cdot \frac{n}{k}$ because $\frac ik$ is an integer.

The other direction: assume $(n,i)=1$ and $n|ik$. Then there exists $m$ such that $ik-mn=1$ since $n,i$ coprime. $n|ik-mn=1$ which is clearly impossible.