Quadratic Residue Proof

**Tand** · April 24th 2010, 05:03 AM

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.

**chiph588@** · April 24th 2010, 09:32 AM

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

Thread: Quadratic Residue Proof

LinkBack

Thread Tools

Display

Quadratic Residue Proof

Similar Math Help Forum Discussions

proof with quadratic residue

[SOLVED] Quadratic Residue proof

When is 2 a quadratic residue?

Quadratic residue -5

quadratic non residue

Search Tags