$10$ is a primitive root modulo $p=4q+1$

642 Views Asked by At

Let $q$ be a prime number such that $p=4q+1$ is also a prime number and $q\equiv 2\ (\text{mod}\ 5)$.

Prove that $10$ is a primitive root modulo $p$.

I know that it is sufficient to prove that $\forall\ \text{prime number }t|\varphi(p)$ $$10^{\frac{\varphi(p)}{t}}\not\equiv 1\ (\text{mod}\ p)$$

Now, since $\varphi(p)=4q$ we only need to check with $t=2,q$.

For $t=q$ we have $10^{\frac{\varphi(p)}{t}}\equiv 10^4\ (\text{mod}\ p)$.

Therefore, if $10^4\equiv 1\ (\text{mod}\ p)$ we have $10^2\equiv \pm1\ (\text{mod}\ p)$.

It is easy to check that it is false for $p$'s that are smaller than $10^2$ (in fact $q=7$ and $p=29$ is the only pair with $p\leq 10^2$ that fall into our case) and for the others it is clearly false.

For $t=2$ I have problems. $10^{\frac{\varphi(p)}{t}}\equiv 10^{2q}\ (\text{mod}\ p)$.

1

There are 1 best solutions below

0
On BEST ANSWER

You can use Euler's Criterion. We would have:

$$10^{2q} = 10^{\frac{p-1}{2}} \equiv \left(\frac{10}{p}\right) \pmod p$$

where $\left(\frac{10}{p}\right)$ is the Legendre Symbol. Now we have:

$$\left(\frac{10}{p}\right) = \left(\frac{2}{p}\right)\left(\frac{5}{p}\right) = (-1) \cdot 1 = -1$$

Hence $$10^{2q} \equiv -1 \pmod p$$


[UPDATE]: Here's why $\left(\frac{2}{p}\right) = -1$ and $\left(\frac{5}{p}\right) = 1$.

First note that $q$ is odd, so we have that $q=2k+1$ and so $p = 8k + 5$. This implies that $\left(\frac{2}{p}\right) = -1$, as $p \equiv 5 \pmod 8$.

For the other one we have that $q\equiv 2 \pmod 5$ from the condition and so $p \equiv 4\cdot2 + 1 \equiv 4 \pmod 5$ and so $\left(\frac{p}{5}\right) = 1$. By the law of quadratic reciprocity $\left(\frac{5}{p}\right) = 1$.