Difference between revisions of "Order of An Integer"
(Created page with "The '''order''' of an integer modulo <math>m</math> is defined as <cmath>\text {ord} _n a = \min _{a^x \equiv 1 \pmod {n}} (x)</cmath> where <math>a</math> and <math>n</mat...") |
m (→See Also) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
<cmath>\text {ord} _n a = \min _{a^x \equiv 1 \pmod {n}} (x)</cmath> | <cmath>\text {ord} _n a = \min _{a^x \equiv 1 \pmod {n}} (x)</cmath> | ||
| − | where <math>a</math> and <math>n</math> are relatively prime positive integers with <math>a \ | + | where <math>a</math> and <math>n</math> are relatively prime positive integers with <math>a \neq 0</math>. |
The notation <math>\text {ord} _n a</math> is first introduced by Guass in his Disquisitiones Arithmeticae in 1801. It is still in common use. | The notation <math>\text {ord} _n a</math> is first introduced by Guass in his Disquisitiones Arithmeticae in 1801. It is still in common use. | ||
| Line 23: | Line 23: | ||
* [[Primitive Root]] | * [[Primitive Root]] | ||
| + | {{stub}} | ||
[[Category:Definition]] | [[Category:Definition]] | ||
Latest revision as of 20:56, 18 January 2025
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.
