1
$\begingroup$

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,

  • 0
    Are you needing (p-1)! = -1 (mod p)?2011-04-16
  • 0
    @quanta: Oh, interesting, let me think. Thank you ;)2011-04-16

1 Answers 1

4

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$.

  • 0
    Thanks. So is it $aa$ or $a^k$, or they could be different quadratic residues?2011-04-16
  • 0
    @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$.2011-04-16
  • 0
    @Chan: Recall your [previous problem](http://math.stackexchange.com/questions/30785/find-the-sum-of-all-quadratic-residues-modulo-p-where-p-equiv-1-pmod4) 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).2011-04-16
  • 0
    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.2011-04-16