4
$\begingroup$

Suppose that p is a prime of the form $8t +3$ and that $q=(p-1)/2$ is also a prime. Show that 2 is a primitive root modulo p.

We must show that $ 2^{(p-1)} \equiv1 \ (mod \ p) $ for this we use the fact that $x^{(p-1)} -1\equiv (x-1)(x-2) \dots(x-(p-1)) \ (mod \ p) $ as the right side is zero then $x^{(p-1)} \equiv 1 \ (mod \ p)$ then $ 2^{(p-1)} \equiv1 \ (mod \ p) $.

Now we see that what $ 2^{(n)} \not\equiv1 \ (mod \ p) $ for $n < p-1$, how could I check this?

$\endgroup$
1
$\begingroup$

You want to calculate the multiplicative order of $2$ modulo $p$. Note that $p-1 = 2q$, so the only possible orders are $q$, and $2q$ (technically $1$ and $2$ are possibilities, but they are easily eliminated).

So this problem is really about showing that $2^q \not\equiv 1 (\rm{mod}\ p)$, rather than $2^p \equiv 1 (\rm{mod}\ p)$.

$2^{\frac{p-1}{2}} (\rm{mod}\ p)$ is just the Legendre symbol $\left(\frac{2}{p}\right)$, which is a standard quantity that comes up as a supplement to the law of quadratic reciprocity.

$\endgroup$
1
$\begingroup$

You know that the prime factorization of $p-1$ is $p-1 = 2 \cdot q$. So the possible orders of the element $2 \in (\mathbb{Z}/p\mathbb{Z})^*$ are the divisors of $p-1$, and these are $1,2,q$ and $p-1$. Try to look at all these possibilities and find that in each possible case $2$ is a primitive root. The case of order $2$ does actually occur (for $p = 3$), but in that case $2 = p - 1$, so things are good anyway.

$\endgroup$
0
$\begingroup$

Hint: If $2^n = 1\mod p$, then $n \in \{2,q,p-1\}$. If it is $2$, then $3 = 2^2 - 1 = pk$ for some $k$, which is a contradiction. If it is $q$, what can you say?

$\endgroup$
0
$\begingroup$

Hint: Euler's Criterion and Wilson's Theorem may be enlightening to anyone trying to show that $2^q \not\equiv 1 (\rm{mod}\ p)$.

An informative proof of Euler's Criterion

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.