PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (231)
Orphanage
Unclass'd
Unproven (514)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
[parent] 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:
  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^{\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).
  3. 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)

View style:

See Also: primitive root, prime residue class

Other names:  multiplicative order

This object's parent.

Attachments:
properties of the multiplicative order of an integer (Theorem) by alozano
Log in to rate this entry.
(view current ratings)

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 2235 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
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)