I am stuck on how to prove these two questions:
(1) Let r be a primitive root of the prime $p$ with $p$ congruent to $1$ modulo $4$. Show that $-r$ is also a primitive root.
(2) Let n be a positive integers possessing a primitive root. Using this primitive root, prove that the product of all positive integers less than $n$ and relatively prime to $n$ is congruent to $-1$ modulo $n$.
Best Answer
1) Let $p=4k+1$. Since $r$ is a primitive root of $p$, it follows that $r$ is a quadratic non-residue of $p$. Thus by Euler's Criterion, we have $r^{2k}\equiv -1\pmod{p}$.
It follows that $(-r)^{2k}\equiv -1\pmod{p}$. Multiply by $-r$. We get that $(-r)^{2k+1}\equiv r\pmod{p}$.
Since $r$ is a power 0f $-r$, and every $a$ relatively prime to $p$ is congruent to a power of $r$, it follows that every $a$ relatively prime to $p$ is congruent to a power of $-r$. This implies that $-r$ is a primitive root of $p$.
2) The result is easy to prove for $n=1$ and $n=2$, so we may assume that $n\ge 3$. Let $g$ be a primitive root of $n$. Then the $\varphi(n)$ numbers in the interval from $1$ to $n$ that are relatively prime to $n$ are congruent (modulo $n$) in some order to $g^1,g^2,g^3,\dots, g^{\varphi(n)}$.
Thus their product is congruent to $g^N$, where by the usual formula for the sum of the first $\varphi(n)$ positive integers we have $2N=\varphi(n)(\varphi(n)+1)$. Since $n\ge 3$, the number $\varphi(n)$ is even, so $\varphi(n)+1$ is odd.
We have $g^N=(g^{\varphi(n)/2})^{\varphi(n)+1}$. Since $g$ is a primitive root of $n$, we have $g^{\varphi(n)/2}\equiv -1\pmod{n}$. Raising this to the odd power $\varphi(n)+1$, we see that $g^N\equiv -1\pmod{N}$, which is what needed to be shown.