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
    @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
    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