# Showing $\operatorname{ord}_ma^s=k$ if $\gcd(s,k) = 1$ and $\operatorname{ord}_ma=k$

If $\operatorname{ord}_ma=k$ and if $\gcd(s,k)=1$ for some $s\ge1$, prove that $\operatorname{ord}_ma^s=k$.

I know that $a^n\equiv 1 \pmod m$ for $n \ge 1$ if and only if $k\mid n$.

However, I don't know how to use this.

-

## 2 Answers

If the order of $a^s$ is $r$, then $k$ divides $rs$, but $\gcd(k,s)=1$, so $k$ divides $r$. On the other hand, it's clear that $r$ is at most $k$.

-

Let $\DeclareMathOperator\ord{ord}x=\ord_m(a^s)$. We'll prove that $$x\mid k\quad\text{and}\quad k\mid x$$ which implies $k=x$.

Part 1: $x\mid k$
We have $$(a^s)^k=(a^k)^s\equiv1^s\equiv1\pmod m$$ hence $x\mid k$ because $(a^s)^k\equiv1\pmod m$ (if and) only if $x\mid k$.

Part 2: $k\mid x$
We have $$1\equiv(a^s)^x=a^{sx}\pmod m$$ hence $k\mid sx$ because $a^y\equiv1\pmod m$ (if and) only if $k\mid y$.
Because $\gcd(k,s)=1$, $k\mid sx$ implies $k\mid x$.

Note: Similarly, but with a little more work one can show that

$$\ord_m(a^s)=\frac k{\gcd(k,s)}\qquad\text{for any }s.$$

If $\gcd(k,s)=1$ we get $\ord_m(a^s)=k$ as above.

-