Let $n$ be a positive integer. Show that there are infinitely many primes $p$ such that the smallest positive primitive root of $p$ is greater than $n$.

Click for solution It's enough to show that there exists infinitely many primes $ p$ such that all the numbers from $ 1$ to $ n$ are quadratic residues modulo $ p$ because order of quadratic residue is $ \frac {p - 1}{2}$. If we denote $ p_1,...,p_k$ all odd primes less or equal to $ n$, then by Chinese remainder theorem and Dirichlet's Theorem there are infinitely many primes $ q$ such that $ q \equiv a^2 \pmod{p_1 p_2...p_k}$ and $ q\equiv 1 \pmod 8$. For all such primes $ q$, by Quadratic reciprocity law we have $ \left(\frac {p_i}{q}\right) = \left(\frac {q}{p_i}\right) = 1$ and $ \left(\frac {2}{q}\right) = 1$ so also $ \left(\frac {m}{q}\right) = 1$ for $ m\le n$ because of multiplicativity of Legendre symbol.

Show that for each odd prime $p$, there is an integer $g$ such that $1<g<p$ and $g$ is a primitive root modulo $p^n$ for every positive integer $n$.

Let $g$ be a Fibonacci primitive root $\pmod{p}$. i.e. $g$ is a primitive root $\pmod{p}$ satisfying $g^2 \equiv g+1\; \pmod{p}$. Prove that $g-1$ is also a primitive root $\pmod{p}$. if $p=4k+3$ then $(g-1)^{2k+3} \equiv g-2 \pmod{p}$, and deduce that $g-2$ is also a primitive root $\pmod{p}$.

Click for solution a.: We have $(g-1)g=g^2-g \equiv 1 \mod p$, thus $g-1$ is the inverse of $g \mod p$, thus primitive root, too. b.: $g-1$ is a nonsquare $\mod p$ since it's a primitive root. Thus $(g-1)^\frac{p-1}{2} \equiv -1 \mod p$. This gives $(g-1)^{2k+3} = (g-1)^2 \cdot (g-1)^\frac{p-1}{2} \equiv -(g^2-2g+1) \equiv g-2 \mod p$. All we are left to show is $\gcd(2k+3,p-1)=1$, which follows via $\gcd(2k+3, 4k+3) = \gcd(2k+3, -3)=1$, the latter because otherwise $3|p$, impossible.

Let $p$ be an odd prime. If $g_{1}, \cdots, g_{\phi(p-1)}$ are the primitive roots $\pmod{p}$ in the range $1<g \le p-1$, prove that \[\sum_{i=1}^{\phi(p-1)}g_{i}\equiv \mu(p-1) \pmod{p}.\]

Suppose that $m$ does not have a primitive root. Show that \[a^{ \frac{\phi(m)}{2}}\equiv 1 \; \pmod{m}\] for every $a$ relatively prime $m$.

Click for solution If $m=xy$ with coprime $x,y>2$, then $2| \varphi(x), \varphi(y)$, giving: \[a^\frac{\varphi(m)}{2}= a^{\varphi(x) \cdot \frac{\varphi(y)}{2}}\equiv 1^\frac{\varphi(y)}{2}=1 \mod x\] and \[a^\frac{\varphi(m)}{2}= a^{\varphi(y) \cdot \frac{\varphi(x)}{2}}\equiv 1^\frac{\varphi(x)}{2}=1 \mod y.\] After handling the easy case $m=2^{k}\geq 8$, this now gives our result because for all other $m$, there are primitive roots.

Suppose that $p>3$ is prime. Prove that the products of the primitive roots of $p$ between $1$ and $p-1$ is congruent to $1$ modulo $p$.

Click for solution Just note that if $g$ is primitive root then $\frac{1}{g}$ is a primitive root as well. Because $-1$ can't be a primitive root (since the order of $-1$ is 2) the conclusion follows.