# help with proof

• December 15th 2007, 12:39 PM
midosoft
help with proof
hi every one

can any one help me to prove the following problem

Assuming thatr is a primitive root of the odd prime p, establish the following fact

a) the congruence r^((p-1)/2) =-1(mod p) holds.
b) if r' is any other primitive root of p , then rr' is not primitive root of p.
c) if the integer r' is such that rr'=1(mod p) then r' is primitive root of p.

and thnx alot
• December 15th 2007, 01:58 PM
ThePerfectHacker
Quote:

Originally Posted by midosoft
a) the congruence r^((p-1)/2) =-1(mod p) holds.

We know $r^{(p-1)} \equiv 1 (\bmod p)$ that means $r^{(p-1)} - 1 \equiv 0 (\bmod p)$ since $p$ is odd we can write $[r^{(p-1)/2} - 1][r^{(p-1)/2} + 1]\equiv 0(\bmod p)$. Now it cannot be $r^{(p-1)/2} \equiv 1(\bmod p)$ because $(p-1)/2 < p$. Thus, the only possibility is that $r^{(p-1)/2} \equiv - 1(\bmod p)$.
Quote:

b) if r' is any other primitive root of p , then rr' is not primitive root of p.
We can write $r' \equiv r^k (\bmod p)$ where $1\leq k \leq p-1$. For $r'$ be a primitive root it is necessary and sufficient that $\gcd (k, p-1) = 1$. Now $rr' \equiv rr^k \equiv r^{k+1} (\bmod p)$, now for $rr'$ to be a primitive root it is necessary and sufficient that $\gcd(k+1, p-1) = 1$. But that is impossible because $p-1$ is an even number and among $k,k+1$ one is even by pigeonholing. Thus it impossible for $rr'$ to be a primitive root canal.

Quote:

c) if the integer r' is such that rr'=1(mod p) then r' is primitive root of p.
Now, $r' \not \equiv 0 (\bmod p)$ because $rr'\equiv 1$, thus, $\gcd(r',p)=1$ that means we can write $r' \equiv r^k$ for $1\leq k \leq p-1$. We have that $rr' \equiv rr^k = r^{k+1} \equiv 1 (\bmod p)$ by hypothesis. That means $k+1 = p-1$ because the order of $r$ is $p-1$ and $k+1\leq p-1$. Thus $k = p-2$, so $\gcd( k , p-1) = 1$ and it means it is a primitive root.