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 (194)
Orphanage
Unclass'd
Unproven (498)
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: Very high Entry average rating: Very high
primitive root (Definition)

Given any positive integer $ n$, the group of units $ U(\mathbb{Z}/n\mathbb{Z})$ of the ring $ \mathbb{Z}/n\mathbb{Z}$ is a cyclic group iff $ n$ is 4, $ p^m$ or $ 2p^m$ for any odd positive prime $ p$ and any non-negative integer $ m$. A primitive root is a generator of this group of units when it is cyclic.

Equivalently, one can define the integer $ r$ to be a primitive root modulo $ n$, if the numbers $ r^0,\,r^1,\,\ldots,\,r^{n-2}$ form a reduced residue system modulo $ n$.

For example, 2 is a primitive root modulo 5, since $ 1,\; 2,\; 2^2 = 4,\; 2^3 = 8 \equiv 3 \pmod{5}$ are all with 5 coprime positive integers less than 5.

The generalized Riemann hypothesis implies that every prime number $ p$ has a primitive root below $ 70(\ln p)^2$.

Bibliography

Wikipedia, ``Primitive root modulo n''



Anyone with an account can edit this entry. Please help improve it!

"primitive root" is owned by CWoo. [ full author list (3) | owner history (1) ]
(view preamble)

View style:

See Also: multiplicative order of an integer modulo m, prime residue class, using primitive roots and index to solve congruences

Other names:  primitive root modulo n, primitive element

Attachments:
every prime has a primitive root (Theorem) by alozano
properties of primitive roots (Theorem) by alozano
index of an integer with respect to a primitive root (Definition) by alozano
existence of primitive roots for powers of an odd prime (Theorem) by alozano
Artin's conjecture on primitive roots (Conjecture) by alozano
Log in to rate this entry.
(view current ratings)

Cross-references: implies, generalized Riemann hypothesis, coprime, reduced residue system, numbers, cyclic, generator, prime, odd, iff, cyclic group, ring, group of units, integer, positive
There are 20 references to this entry.

This is version 9 of primitive root, born on 2006-07-11, modified 2008-01-25.
Object id is 8133, canonical name is PrimitiveRoot.
Accessed 3707 times total.

Classification:
AMS MSC: 11-00 (Number theory :: General reference works )
Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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