Primitive Root Mod P

Question

I have been able to answer all of the parts to the question apart from part (v). Any tips on how? I assume I have to show that $ m=2^n $, but I am unsure as to how. I can't imagine it is very difficult/long. Thanks :)

Answer 1

Since we have $\phi(p-1)=\phi(2^{2^n})=2^{2^{n-1}}=\frac{p-1}{2}$, we see that every quadratic non-residue modulo $p$ is a primitive root modulo $p$. Indeed, we know that there are $\phi(\phi(p))=\phi(p − 1)$ primitive roots, and that every primitive root is a quadratic non-residue. But there are exactly $(p−1)/2$ non-residues, hence every non-residue automatically is a primitive root.

From part $(ii)$ we know that for $5$, hence $5$ is a primitive root modulo $p$.

Answer 2

Theorem: If $a\in\mathbb Z$, $p$ is prime, $\gcd(a,p)=1$, and for all prime divisors $q$ of $p-1$ we have $a^{(p-1)/q}\not\equiv 1\pmod{p}$, then $a$ is a primitive root mod $p$.

First, if $p=2^{2^n}+1$ with $n\ge 2$, then $\gcd(5,p)=1$, because by Fermat's Little Theorem $$2^{2^n}\equiv \left(2^{2^{n-2}}\right)^4\equiv 1\not\equiv -1\pmod{5}$$

The only prime divisor of $p-1=2^{2^n}$ is $2$, therefore we're left with proving $5^{\frac{p-1}{2}}\not\equiv 1\pmod{p}$, which is true, because by Euler's Criterion and Quadratic Reciprocity: $$5^{\frac{p-1}{2}}\equiv \left(\frac{5}{p}\right)\equiv \left(\frac{p}{5}\right)\equiv \left(\frac{2}{5}\right)\equiv -1\pmod{p}$$