Order of An Integer
The order of an integer modulo 
is defined as
![\[\text {ord} _n a = \min _{a^x \equiv 1 \pmod {n}} (x)\]](http://latex.artofproblemsolving.com/4/3/d/43d0b23ae919c7d996b59ab92b355b617c0cb934.png)
where 
and 
are relatively prime positive integers with 
.
The notation 
is first introduced by Guass in his Disquisitiones Arithmeticae in 1801. It is still in common use.
Existence
The proof of its existence is quite easy.
By the Euler's Totient Theorem, the set
![\[S= \{ x: | a^x \equiv 1 \pmod {n} \}\]](http://latex.artofproblemsolving.com/4/7/5/4754626e011a36d9c7c4815fe6fcfd21bb5e28d7.png)
contain at least one element, namely 
. Thus, the Well Ordering Principle implies the existence of the smallest element of 
Uses
The order of an integer is not really useful for anything. However, it is essential for the definition of the concept of a Primitive Root, which is quite useful.
See Also
This article is a stub. Help us out by expanding it.
