|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
multiplicative order of an integer modulo m
|
(Definition)
|
|
Definition 1 Let $m>1$ be an integer and let $a$ be another integer relatively prime to $m$ . The order 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 1 Several remarks are in order:
- Notice that if $\gcd(a,m)=1$ then $a$ belong to the units $(\Ints/m\Ints)^\times$ of $\Ints/m\Ints$ . The units $(\Ints/m\Ints)^\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$ .
- 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).
- The order of $a$ modulo $m$ is precisely $\phi(m)$ if and only if $a$ is a primitive root for the integer $m$ .
|
"multiplicative order of an integer modulo m" is owned by alozano.
|
|
(view preamble | get metadata)
Cross-references: primitive root, Euler phi function, Euler's theorem, subgroup generated by, number, multiplication, group, units, positive, relatively prime, integer
There are 6 references to this entry.
This is version 2 of multiplicative order of an integer modulo m, born on 2006-10-26, modified 2007-05-30.
Object id is 8476, canonical name is MultiplicativeOrderOfAnIntegerModuloM.
Accessed 3412 times total.
Classification:
| AMS MSC: | 11-00 (Number theory :: General reference works ) | | | 13M05 (Commutative rings and algebras :: Finite commutative rings :: Structure) | | | 13-00 (Commutative rings and algebras :: General reference works ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
