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.

$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.

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

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

If $\operatorname{ord}a=d$ and $e$ is a positive divisor of $d$ then $a^{d/e}$ has exact order $e$ .
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
Canonical name	PropertiesOfTheMultiplicativeOrderOfAnInteger
Date of creation	2013-03-22 16:20:44
Last modified on	2013-03-22 16:20:44
Owner	alozano (2414)
Last modified by	alozano (2414)
Numerical id	4
Author	alozano (2414)
Entry type	Theorem
Classification	msc 11-00
Classification	msc 13M05
Classification	msc 13-00