Cyclic multiplicative group and quadratic residues

Question

The following observation: I have the group of integer multiplicative modulo $p$, where $p$ is prime and $p = 2q + 1$ where $q$ is also prime.

As an example $p = 23$ and $q = 11$

If I use the generator $2$, I get the following subgroup of order $q$:

$$ \{ 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12 \} $$

If I calculate the quadratic residues of the same group, I get the following:

$$ \{ 0, 1, 4, 9, 16, 2, 13, 3, 18, 12, 8, 6 \} $$

With the exception of the $0$, these are exactly the same numbers.

My questions are the following:

1. Is there a general rule that the quadratic residues equal the subgroup generated by $2$?
2. Can one show, by using Euler's criterion, if a certain number is part of the subgroup generated by $g$. Concretely, could I apply Euler's criterion to $7$ (which should output $-1$) and to $13$ (where it should output $1$)?

Answer 1

We know that the units modulo $p$ form a group of order $p-1$. In our case it's $2q$. Now as $\text{ord}(2) \mid 2q$ we have that $\text{ord}(2) = 1,2,q$ or $2q$. Obviously for big enough $p$ we have that $2^1, 2^2 \not \equiv 1 \pmod{p}$. On the other side by using the Euler's Crierion we have that:

$$2^q \equiv \left(\frac{2}{p}\right) \pmod{p}$$

Now we have that $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = (-1)^{\frac{(2q+1)^2-1}{8}} = (-1)^{\frac{4q^2 + 4q}{8}} = (-1)^{\frac{q(q+1)}{2}} = 1$ iff $q=4k+3$

Hence if $q=4s+3$ we have that $\text{ord}(2) = q$. Then if $g$ is a generator of the units modulo $p$ we ahve that $2 = g^{2k}$ for some $k \in \{1,2,\cdots q-1\}$. Now obviously any power from $2$ will be a quadratic residue and also $2$ generates a subgroup of order $q$ and they are exactly all quadratic residues, as there are exactly $\frac{p-1}{2} = q$ of them.

If $q=4s+1$ then $2$ is in fact generator of the units modulo $p$.

Answer 2

For question $1$, the answer is no, since the *Legendre's symbol for $2$ is $$\Bigl(\frac2p\Bigr)=(-1)^{\tfrac{p^2-1}8},$$ i.e. $2$ is a quadratic residue mod. $p$ if and only if $p\equiv \pm 1\mod 8$.

Now, $p\equiv 1\mod 8$ is impossible, as it implies $p\equiv 0\mod 4$, and $\;p\equiv -1\mod 8$ implies $q\equiv -2\mod 8$, i.e. $\;p\equiv -1\mod 4$.