I have seen an exercise on the Apostol, but I haven't understood some passages. I would be very grateful if you could solve my doubts.
The problem is
Find all primes $p$ for which 3 is a Quadratic Residue
The problem is modelled by $\left(3\mid p\right)=1$; apply Law of quadratic reciprocity and obtain
$$\left(3\mid p\right)=\left(p\mid 3\right)=(-1)^{\left(p-1 \right)\left(3-1 \right)/4}$$
Observes that the value of $\left(3\mid p\right)$ depends from $p\mod 3$ and from the sign of the exponent, or $p\mod4$. Hence, $p\mod12$ is considered. Finally, the author observes that since $\phi\left(12\right)=4$, there are only four cases to consider.
And, up to this point, everything is crystal clear.
The exercise then proceeds saying that the cases to analyse are:
- $p\equiv1\left(\mod12\right)$
- $p\equiv5\left(\mod12\right)$
- $p\equiv7\left(\mod12\right)$
- $p\equiv11\left(\mod12\right)$
I don't understand the logic behind selecting the numbers 1, 5, 7, and 11. Can anybody help me?
Thanks
If $p = 2, 3$, then $p$ is a multiple of $2$ or $3$. Otherwise, it is not a multiple of $2$ or $3$, which implies $p \equiv 1,5, 7, 11$ modulo $12$.
This is because if a number is even, then it is even modulo an even number, and vice versa. Same for multiples of $3$.