i need help in primitive roots

Printable View

December 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 ?
December 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 $\{ r,r^2,...,r^{\phi(n)} \}$ , this set is the complete set of numbers relatively prime to $n$ . Now $s=r^k$ is a primitive root means $\{ s,s^2,...,s^{\phi(n)} \}$ must also be a complete set of numbers relatively prime to $n$ . If $\gcd (k, \phi(n)) = d$ then $s^{\phi(n)/d} = \left( r^{\phi (n)} \right)^{k/d} \equiv 1 (\bmod n)$ thus the order of $s$ is at least $\phi(n)/d$ but since we require that $\phi(n)/d \geq \phi(n)$ it means the only possible value for $d$ is $1$ . Now (for the converse) say $\gcd (k,\phi(n)) = 1$ . We will argue that $\{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 $n$ . Note, if $s^i \equiv s^j (\bmod n)$ then $r^{ki} \equiv r^{kj} (\bmod n)$ but that means $ki \equiv kj (\bmod \phi(n))$ since $\gcd(k,\phi(n))=1$ it means $i\equiv j (\bmod \phi(n))$ so $i=j$ since $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.
December 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 $r$ is a primitive root then $r^k$ is a primitive root iff $\gcd(k, p - 1) = 1$ so there are $\phi(p-1)$ such exponents which can be paired because $\phi (p-1)$ is even since $p>3$ . Let $r_1,...,r_m$ be these primitive roots. Then the equation $r_i x \equiv 1(\bmod p)$ has a solution since $\gcd (r_i,p)=1$ it means for $r_1$ be can pick a $r_2$ so that $r_1r_2\equiv 1$ ; for $r_3$ we can pick a $r_4$ so that $r_3r_4\equiv 1$ , and so on.
December 13th 2007, 04:51 PM
midosoft

i don't know what i say man

very thnx