|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
properties of the multiplicative order of an integer
|
(Theorem)
|
|
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$ .
Proposition 1 Let $m$ be a positive integer and suppose that $(a,m)=1$ .
- $a^s\equiv 1 \mod m$ if and only if $\ord a$ divides $s$ . In particular, $\ord a$ divides $\phi(m)$ , where $\phi$ is the Euler phi function.
- $a^s\equiv a^t \mod m$ if and only if $s\equiv t \mod \ord a$ .
- If $\ord a =d$ then $\displaystyle \ord a^k =\frac{d}{\gcd(k,d)}$ for any $k\geq 1$ .
- If $\ord a =d$ and $e$ is a positive divisor of $d$ then $a^{d/e}$ has exact order $e$ .
- Suppose $\ord a=h$ and $\ord b = k$ with $\gcd(h,k)=1$ . Then $\ord (ab)=hk$ .
|
"properties of the multiplicative order of an integer" is owned by alozano.
|
|
(view preamble | get metadata)
Cross-references: divisor, Euler phi function, divides, positive, multiplicative order, order, relatively prime, integer
There is 1 reference to this entry.
This is version 1 of properties of the multiplicative order of an integer, born on 2006-10-26.
Object id is 8478, canonical name is PropertiesOfTheMultiplicativeOrderOfAnInteger.
Accessed 988 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
|
|
|
|
|
|
|
|
|
|
|
