Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
    
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
add comment

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.