# multiplicative order of an integer modulo m

###### Definition.

Let $m>1$ be an integer and let $a$ be another integer relatively prime to $m$. The order (http://planetmath.org/OrderGroup) 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$.

###### Remarks.

Several remarks are in order:

1. 1.

Notice that if $\gcd(a,m)=1$ then $a$ belong to the units $(\mathbb{Z}/m\mathbb{Z})^{\times}$ of $\mathbb{Z}/m\mathbb{Z}$. The units $(\mathbb{Z}/m\mathbb{Z})^{\times}$ form a group with respect to multiplication, and the number of elements in the subgroup generated by $a$ (and its powers) is the order of the integer $a$ modulo $m$.

2. 2.

By Euler’s theorem, $a^{\phi(m)}\equiv 1\mod m$, therefore the order of $a$ is less or equal to $\phi(m)$ (here $\phi$ is the Euler phi function).

3. 3.

The order of $a$ modulo $m$ is precisely $\phi(m)$ if and only if $a$ is a primitive root for the integer $m$.

Title multiplicative order of an integer modulo m MultiplicativeOrderOfAnIntegerModuloM 2013-03-22 16:20:38 2013-03-22 16:20:38 alozano (2414) alozano (2414) 5 alozano (2414) Definition msc 13-00 msc 13M05 msc 11-00 multiplicative order PrimitiveRoot PrimeResidueClass