# Math Help - Help

1. ## Help

We will show that $3$ is a primitive root modulo $p$. If $3$ is not a primitive root then $3$ must be a quadradic residue. This is because $3^{(p-1)/2}\equiv \pm 1(\bmod p)$. It cannot be $-1$ for that would force $p-1$ to be the order of $3$ since $p-1$ is a power of $2$. Therefore, there is $a$ such that $a^2 \equiv - 3(\bmod p)$. Let $x$ be the solution to $2x\equiv a - 1(\bmod p)$. Then, $(2x)^3 \equiv (a-1)^3 (\bmod p)$ and so $8x^3 \equiv (a^3+3a) - (1+3a^2)\equiv 8(\bmod p)$. Thus, we see that $x$ has order $3$. That gives us a contradiction because then $3$ divides $(p-1)$ which is impossible. Since $3$ is a primitive root it means $(3/p)=-1$ and so $3^{(p-1)/2}\equiv -1(\bmod p)$. We see that $p$ divides $3^{(p-1)/2}+1$.