Primitive Roots Proofs

Question

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

Answer 1

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.

Answer 2

(1) $r$ being a primitive root means that the multiplicative order of $r$ modulo $p$ is $p-1$ (maximal), so that it generates all nonzero elements.
In particular, we also have $r^k\equiv -1$ for some $k< p-1\}$. As then $r^{2k}\equiv 1$, it follows that $k=\frac{p-1}2$.
Then we have $$-r\equiv r^{k+1}=r^{\frac{p+1}2}\,.$$ Now, by hypothesis, $4\,|\,p-1$ so $k=\frac{p-1}2$ is still even, $k+1=\frac{p+1}2$ is odd. In order that $-r$ be a primitive root, we only need that $k+1$ is coprime to $2k$ in case $k$ is even.

(2) Let $G$ denote a representative set of coprimes to $n$ and let $r$ be a primitive root. That means that its powers give all the coprimes to $n$ (modulo $n$, of course), in other words, the order of $r$ is $\varphi(n)$. Now if $a^2\equiv 1 \pmod n$ for a coprime $a$, then, as before, $a=r^k$ for some $k<\varphi(n)$, so $r^{2k}\equiv 1$ which implies $\varphi(n)\,|\, 2k$ that has only possibility $2k=\varphi(n)$. So, in this case $a^2\equiv 1$ can have at most two solutions in $G$, $\,a\equiv -1$ and $a\equiv 1$.

All other elements of $G$ come in pairs: for each $a$, its inverse $b$ in $G$ is unique (if $a=r^k$, then $b=r^{\varphi(n)-k}$). So, when multiplying all these together, the inverse pairs will cancel out, and only $-1$ and $1$ are whose pairs are themselves.