1. ## 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

2. 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)$.
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.

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.