6

This was a question from an exam:

Let $q \ge 5$ be a prime number and assume that $p=2q+1$ is also prime. Prove that $-3$ is a primitive root in $\mathbb{Z}_p$.

I guess the solution goes something like this:

Let $k$ be the order multiplicative order of $-3$ modulo p. Using Euler's theorem we see that: $(-3)^{2q} \equiv1\ (mod\ p)$. Hence $k\ |\ 2q$, which means (since $q$ is prime) that $k=1,\ 2,\ q,$ or $2q$. Obviously $k \neq 1$ and $k \neq 2$, since otherwise we'll have $[-3]_p=[1]_p$ and $[(-3)^2]_p = [9]_p = [1]_p$, respectively, which is wrong since $ p \ge 11$. What remains is to show that $k \neq q$. Unfortunately, I could not figure out how to show this.

Bart Michels
  • 26,355
SomeStrangeUser
  • 3,033

2 Answers2

5

Hint:

If $(-3)^q\equiv1\pmod p$, then $(-3)^{\frac{p-1}2}\equiv1\pmod p$, hence $-3$ would be a quadratic residue modulo $p$.

You could write this as

$$\left(\!\frac{-3}{p}\!\right)=1$$ and play around with the Law of Quadratic Reciprocity and other properties of the Legendre symbol.

This will allow you to conclude something very interesting.

Edit:

I'll show how I personally would handle with the Legendre symbols.

We have $$\begin{align}1=\left(\!\frac{-3}{p}\!\right)&=\left(\!\frac{-1}{p}\!\right)\cdot\left(\!\frac{3}{p}\!\right)\\&=(-1)^{\frac{p-1}2}\cdot\left(\!\frac{3}{p}\!\right)\\ &=(-1)^q\cdot(-1)^{\frac{(p-1)(3-1)}{4}}\cdot\left(\!\frac{p}{3}\!\right)\\ &=(-1)\cdot(-1)\cdot\left(\!\frac{p}{3}\!\right)\end{align},$$ hence $\left(\!\frac{p}{3}\!\right)=1$, which means $p\equiv1\pmod3$. This would imply $3\mid p-1=2q$, a contradiction.

Bart Michels
  • 26,355
  • Wait, there is no need of the reciprocity here, except the properties linked to in the second link, right? :) – awllower Jan 23 '14 at 11:18
  • 1
    I can use the properties to show that: $$\left(!\frac{3}{p}!\right)=-1$$ and then show that it is impossible for a prime $q \ge 5$ to have: $$2q+1\equiv5,7\ (mod\ 12)$$ But this property is very specific, and not something that can be thought up during an exam. – SomeStrangeUser Jan 23 '14 at 11:56
  • 1
    I edited my answer and added the rest of the solution. Please tell me if anything is unclear, I will explain. The only properties I use are the multiplicativity, Euler's criterion and the law of QR. – Bart Michels Jan 23 '14 at 12:17
  • @awllower (and SomeStrangeUser): Yes, in fact it can be solved if you know the values of $\left(!\frac 3p!\right)$ by heart. However I suggest not to learn these (I don't know them by heart either), and to use QR. There's less chance of making mistakes if you only use the general properties. (Besides, note that the multiplicative property follows from Euler's criterion.) – Bart Michels Jan 23 '14 at 12:23
  • Okay. Now I got it. Thanks Alot! – SomeStrangeUser Jan 23 '14 at 12:36
  • Thanks for the answer, then. I did not come up with your solution however. Maybe it is a personal choice. XD In any case, the property used in SomeStrangeUser's proof, the same as I would like to suggest, is a particular case of the reciprocity. :) – awllower Jan 23 '14 at 12:36
1

Hint: If $(-3)^q \equiv 1 (mod p)$ then $-3$ is a quadratic residue modulo $p$ (because if $\xi$ is a primitive root and $(\xi^k)^q \equiv 1$ then $k$ is even and $\xi^k$ is a quadratic resieue)

user68061
  • 3,827