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