|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
properties of primitive roots
|
(Theorem)
|
|
Definition 1 Let $m>1$ be an integer. An integer $g$ is said to be a primitive root of $m$ if $\gcd(g,m)=1$ and the multiplicative order of $g$ is exactly $\phi(m)$ , where $\phi$ is the Euler phi function. In other words, $g^{\phi(m)}\equiv 1 \mod m$ and $g^n\neq 1 \mod m$ for any $n<\phi(m)$ .
Proposition 1 Let $m>1$ be an integer.
- If $g$ is a primitive root of $m$ then the set $\{1,g,g^2,\ldots,g^{\phi(m)}\}$ is a complete set of representatives for $(\Ints/m\Ints)^\times$ .
- If $\gcd(g,m)=1$ then $g$ is a primitive root of $m$ if and only if $g^{\phi(m)/q}\neq 1 \mod m$ for every prime divisor $q$ of $\phi(m)$ .
- If $g$ is a primitive root of $m$ , then $g^s\equiv g^t \mod m$ if and only if $s\equiv t \mod \phi(m)$ . Thus $g^s\equiv 1 \mod m$ if and only if $\phi(m)$ divides $s$ .
- If $g$ is a primitive root of $m$ , then $g^k$ is a primitive root of $m$ if and only if $\gcd(k,\phi(m))=1$ .
- If $m$ has a primitive root then $m$ has exactly $\phi(\phi(m))$ incongruent primitive roots.
|
"properties of primitive roots" is owned by alozano.
|
|
(view preamble | get metadata)
Cross-references: divides, prime divisor, complete, every prime has a primitive root, Euler phi function, multiplicative order, primitive root, integer
This is version 1 of properties of primitive roots, born on 2006-10-26.
Object id is 8479, canonical name is PropertiesOfPrimitiveRoots.
Accessed 1206 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
