multiplicative order of an integer modulo m
Definition.
Let $m\mathrm{>}\mathrm{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\mathrm{mod}m$) is the smallest positive integer $n$ such that ${a}^{n}\mathrm{\equiv}\mathrm{1}\mathrm{mod}m$. The order is sometimes denoted by $\mathrm{ord}\mathit{}a$ or ${\mathrm{ord}}_{m}\mathit{}a$.
Remarks.
Several remarks are in order:

1.
Notice that if $\mathrm{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.
By Euler’s theorem, ${a}^{\varphi (m)}\equiv 1modm$, therefore the order of $a$ is less or equal to $\varphi (m)$ (here $\varphi $ is the Euler phi function).

3.
The order of $a$ modulo $m$ is precisely $\varphi (m)$ if and only if $a$ is a primitive root^{} for the integer $m$.
Title  multiplicative order of an integer modulo m 

Canonical name  MultiplicativeOrderOfAnIntegerModuloM 
Date of creation  20130322 16:20:38 
Last modified on  20130322 16:20:38 
Owner  alozano (2414) 
Last modified by  alozano (2414) 
Numerical id  5 
Author  alozano (2414) 
Entry type  Definition 
Classification  msc 1300 
Classification  msc 13M05 
Classification  msc 1100 
Synonym  multiplicative order 
Related topic  PrimitiveRoot 
Related topic  PrimeResidueClass 