Primitive Root
Let be an positive integer. Then integer
is said to be a Primitive Root of
(if it exist), if
Existence
Primitive roots only exist for certain integers. In fact, it only exist for or
, where
is a ODD prime and
is a positive integer.
The proof of that statement is extremely long and tedious. Euler tried to prove it but his proof was wrong. This is a link to the proof: Proof of the Existence of Primitive Roots
How to Find a Primitive Root
Once you find a primitive root for a prime number (which you probably just have to find by trial and error),
, determine if
If , then
is not a primitive root of
, but
is. Now,
is extremely rare, so for the vast majority of the time, if
is a primitive root for
, it is also a primitive root of
. However, if
is a primitive root of
, then obviously
is also a primitive root of
. Now, if
is a primitive root of both
and
, then
is a primitive root of
for all positive integers
.
A proof of all the statements above can be found here.
Uses
Primitive roots have some important properties.
For example, if is a primitive root of a integer
and
and
is relatively prime, then
form a reduced residue system modulo .
Proof:
Obviously, every elements of is relatively prime to
.
Now, suppose that there exist two integers and
such that
satisfies
Then
so , since
.
This result allows us to define the index of an integer with respect to a prime and a primitive root of
,
.
Indices can be used to solve Polynomial Congruences.
See Also
This article is a stub. Help us out by expanding it.