# help with proof

• Dec 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
• Dec 15th 2007, 01:58 PM
ThePerfectHacker
Quote:

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

We know $\displaystyle r^{(p-1)} \equiv 1 (\bmod p)$ that means $\displaystyle r^{(p-1)} - 1 \equiv 0 (\bmod p)$ since $\displaystyle p$ is odd we can write $\displaystyle [r^{(p-1)/2} - 1][r^{(p-1)/2} + 1]\equiv 0(\bmod p)$. Now it cannot be $\displaystyle r^{(p-1)/2} \equiv 1(\bmod p)$ because $\displaystyle (p-1)/2 < p$. Thus, the only possibility is that $\displaystyle 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 $\displaystyle r' \equiv r^k (\bmod p)$ where $\displaystyle 1\leq k \leq p-1$. For $\displaystyle r'$ be a primitive root it is necessary and sufficient that $\displaystyle \gcd (k, p-1) = 1$. Now $\displaystyle rr' \equiv rr^k \equiv r^{k+1} (\bmod p)$, now for $\displaystyle rr'$ to be a primitive root it is necessary and sufficient that $\displaystyle \gcd(k+1, p-1) = 1$. But that is impossible because $\displaystyle p-1$ is an even number and among $\displaystyle k,k+1$ one is even by pigeonholing. Thus it impossible for $\displaystyle 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, $\displaystyle r' \not \equiv 0 (\bmod p)$ because $\displaystyle rr'\equiv 1$, thus, $\displaystyle \gcd(r',p)=1$ that means we can write $\displaystyle r' \equiv r^k$ for $\displaystyle 1\leq k \leq p-1$. We have that $\displaystyle rr' \equiv rr^k = r^{k+1} \equiv 1 (\bmod p)$ by hypothesis. That means $\displaystyle k+1 = p-1$ because the order of $\displaystyle r$ is $\displaystyle p-1$ and $\displaystyle k+1\leq p-1$. Thus $\displaystyle k = p-2$, so $\displaystyle \gcd( k , p-1) = 1$ and it means it is a primitive root.