# properties of the multiplicative order of an integer

###### Definition.

Let $m>1$ be an integer and let $a$ be another integer relatively prime to $m$. The order of $a$ modulo $m$ (or the multiplicative order of $a\mod m$) is the smallest positive integer $n$ such that $a^{n}\equiv 1\mod m$. The order is sometimes denoted by $\operatorname{ord}a$ or $\operatorname{ord}_{m}a$.

###### Proposition.

Let $m$ be a positive integer and suppose that $(a,m)=1$.

1. 1.

$a^{s}\equiv 1\mod m$ if and only if $\operatorname{ord}a$ divides $s$. In particular, $\operatorname{ord}a$ divides $\phi(m)$, where $\phi$ is the Euler phi function.

2. 2.

$a^{s}\equiv a^{t}\mod m$ if and only if $s\equiv t\mod\operatorname{ord}a$.

3. 3.

If $\operatorname{ord}a=d$ then $\displaystyle\operatorname{ord}a^{k}=\frac{d}{\gcd(k,d)}$ for any $k\geq 1$.

4. 4.

If $\operatorname{ord}a=d$ and $e$ is a positive divisor of $d$ then $a^{d/e}$ has exact order $e$.

5. 5.

Suppose $\operatorname{ord}a=h$ and $\operatorname{ord}b=k$ with $\gcd(h,k)=1$. Then $\operatorname{ord}(ab)=hk$.

Title properties of the multiplicative order of an integer PropertiesOfTheMultiplicativeOrderOfAnInteger 2013-03-22 16:20:44 2013-03-22 16:20:44 alozano (2414) alozano (2414) 4 alozano (2414) Theorem msc 11-00 msc 13M05 msc 13-00