• April 24th 2010, 05:03 AM
Tand
Let p be a prime such that p is congruent to 3 modulo 4 and let a be a quadratic residue modulo p. Prove that if ab is congruent to p-1 modulo p, then b is a quadratic non-residue modulo p.
• April 24th 2010, 09:32 AM
chiph588@
Quote:

Originally Posted by Tand
Let p be a prime such that p is congruent to 3 modulo 4 and let a be a quadratic residue modulo p. Prove that if ab is congruent to p-1 modulo p, then b is a quadratic non-residue modulo p.

$ab\equiv p-1\equiv -1\bmod{p}\implies b\equiv-a^{-1}\bmod{p}$

$\left(\frac bp\right) = \left(\frac{-a^{-1}}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a^{-1}}{p}\right) = (-1)\cdot(1) = -1$ since $p\equiv3\bmod{4}$.

You may be wondering why $\left(\frac{a^{-1}}{p}\right) = 1$.

Well, $1=\left(\frac1p\right) = \left(\frac{a\cdot a^{-1}}{p}\right) = \left(\frac ap\right)\left(\frac{a^{-1}}{p}\right) = \left(\frac{a^{-1}}{p}\right)$.