Question regarding the product of quadratic residue modulo $p$, $p$ is prime

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,

• Are you needing (p-1)! = -1 (mod p)? – quanta Apr 16 '11 at 18:18
• @quanta: Oh, interesting, let me think. Thank you ;) – Chan Apr 16 '11 at 18:21

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$.
• Thanks. So is it $aa$ or $a^k$, or they could be different quadratic residues? – Chan Apr 16 '11 at 22:36
• @Chan: your question doesn't make any sense. We have a collection of integers, the integers between $1$ and $p-1$ that are quadratic residues modulo $p$. We are multiplying all of them together. If I have a collection of integers $x$, $y$, and $z$, the product of the collection is $xyz$. I really have no idea what you mean by $a^k$. – Zev Chonoles Apr 16 '11 at 23:09
• @Chan: Recall your previous problem regarding the sum of all the quadratic residues when $p\equiv 1\bmod 4$, and my proof that the sum was equal to 0 modulo $p$ because we could pair off each quadratic residue $a$ with its negative, $p-a$, which would also be a quadratic residue when $p\equiv 1\bmod 4$. Well here, we are instead multiplying, so we want to pair off by $a$ and it's inverse mod $p$, namely $a^{-1}$, which is also a quadratic residue (no matter what $p$ is). – Zev Chonoles Apr 16 '11 at 23:36
• Sorry for the confusion. The reason that I misunderstood because of the expression that I derived above. Now I understand what it meant by the product of quadratic residues. On the other hand, reading your statement in the previous problem thread, I already proved that if $p \equiv 1 \pmod{4}$ then $-a$ is also a quadratic residue modulo $p$. Should I go from here as well since I was stuck with your given hint above. – Chan Apr 16 '11 at 23:49