# i need help in primitive roots

• Dec 11th 2007, 05:33 PM
midosoft
i need help in primitive roots
i have 2 problem and need ur help

let r be a primitive root of the integer n . prove that r^k is a primitive root of n if and only if gcd(k,phi(n))=1

***********

for prime p>3 prove that the primitive root of p occur in pairs r,r' where rr' equivelent to 1(modp)

hint (take r' as r^(p-2) )

******

plz any one can help me with them ?
• Dec 11th 2007, 06:58 PM
ThePerfectHacker
Quote:

Originally Posted by midosoft
i have 2 problem and need ur help

let r be a primitive root of the integer n . prove that r^k is a primitive root of n if and only if gcd(k,phi(n))=1

Let n>2 be a positive integer. Say that n has a primitive root, call it r. Consider the set $\displaystyle \{ r,r^2,...,r^{\phi(n)} \}$, this set is the complete set of numbers relatively prime to $\displaystyle n$. Now $\displaystyle s=r^k$ is a primitive root means $\displaystyle \{ s,s^2,...,s^{\phi(n)} \}$ must also be a complete set of numbers relatively prime to $\displaystyle n$. If $\displaystyle \gcd (k, \phi(n)) = d$ then $\displaystyle s^{\phi(n)/d} = \left( r^{\phi (n)} \right)^{k/d} \equiv 1 (\bmod n)$ thus the order of $\displaystyle s$ is at least $\displaystyle \phi(n)/d$ but since we require that $\displaystyle \phi(n)/d \geq \phi(n)$ it means the only possible value for $\displaystyle d$ is $\displaystyle 1$. Now (for the converse) say $\displaystyle \gcd (k,\phi(n)) = 1$. We will argue that $\displaystyle \{s,s^2,...,s^{\phi(n)}\}$ cannot be congruent to eachother and hence by pigeonhole principle they must contain all the relatively prime numbers to $\displaystyle n$. Note, if $\displaystyle s^i \equiv s^j (\bmod n)$ then $\displaystyle r^{ki} \equiv r^{kj} (\bmod n)$ but that means $\displaystyle ki \equiv kj (\bmod \phi(n))$ since $\displaystyle \gcd(k,\phi(n))=1$ it means $\displaystyle i\equiv j (\bmod \phi(n))$ so $\displaystyle i=j$ since $\displaystyle 1\leq i,j\leq \phi(n)$. Thus, this shows that the only numbers congruent are those to themselves, i.e. distinct numbers leave distinct remainders mod n.
• Dec 11th 2007, 07:36 PM
ThePerfectHacker
Quote:

Originally Posted by midosoft
for prime p>3 prove that the primitive root of p occur in pairs r,r' where rr' equivelent to 1(modp)

hint (take r' as r^(p-2) )

By the first excerise if $\displaystyle r$ is a primitive root then $\displaystyle r^k$ is a primitive root iff $\displaystyle \gcd(k, p - 1) = 1$ so there are $\displaystyle \phi(p-1)$ such exponents which can be paired because $\displaystyle \phi (p-1)$ is even since $\displaystyle p>3$. Let $\displaystyle r_1,...,r_m$ be these primitive roots. Then the equation $\displaystyle r_i x \equiv 1(\bmod p)$ has a solution since $\displaystyle \gcd (r_i,p)=1$ it means for $\displaystyle r_1$ be can pick a $\displaystyle r_2$ so that $\displaystyle r_1r_2\equiv 1$; for $\displaystyle r_3$ we can pick a $\displaystyle r_4$ so that $\displaystyle r_3r_4\equiv 1$, and so on.
• Dec 13th 2007, 04:51 PM
midosoft
i don't know what i say man

very thnx