Problem
Prove that the product of the quadratic residue modulo $p$ is congruent to $1$ modulo p if $p \equiv -1 \pmod{4}$ and is congruent to $-1$ modulo $p$ if $p \equiv 1 \pmod{4}$.
First of all, my question is what do they mean by product? Is it $a \cdot a$ or it could be $a^{k}$, where $k$ is an integer?
On the other hand, when attempting to solve it, I realized it could lead to a contradiction.
Proof
By Euler's criteria, we have $$\bigg( \dfrac{a}{p} \bigg) \equiv a^{\frac{p-1}{2}} \pmod{p}$$
Since $a$ is quadratic residue modulo $p$ as suppose, hence,
$$\bigg( \dfrac{a}{p} \bigg) \equiv a^{\frac{p-1}{2}} \pmod{p} = 1$$
which implies $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$, then
If $p \equiv -1 \pmod{4} \Leftrightarrow p \equiv 3 \pmod{4} \Leftrightarrow p = 4k + 3$, for some integers $k$. And If $p \equiv 1 \pmod{4} \Leftrightarrow p = 4q + 1$, for some integers $q$. So,
If $p = 4k + 3, \Rightarrow \dfrac{p-1}{2} = \dfrac{4k + 3 – 1}{2} = 2k + 1$, then $a^{2k + 1} \equiv 1 \pmod{p}$.
If $p = 4q + 1, \Rightarrow \dfrac{p-1}{2} = \dfrac{4q + 1 – 1}{2} = 2q$, then $a^{2q} \equiv 1 \pmod{p}$.
From here, I saw that the product of $a$, $a$ raises to either an odd power or an even power is $1$. So how the product could be $-1$ as the in the proof requirement? And what can we deduce from here? Any idea?
Thanks,
Best Answer
They mean product as in multiplication, e.g. the product of the numbers $a$, $b$, and $c$ is $abc$.
Hint: If $x$ is a quadratic residue modulo $p$, then so is $x^{-1}$ (recall that $x^{-1}$ is the $a$ such that $ax=1\bmod p$). Pair up each quadratic residue with its inverse in the product, and cancel each pair; what's different about the case when $\frac{p-1}{2}$ (the number of quadratic residues mod $p$) is even, vs. when it is odd? In particular, think about $-1$.