Thread: quadratic residue proof

1) If ab=r mod p, where r is a quadratic residue of the odd prime p, prove that a & b are both quadratic residues of p or both non-residues of p.

2) If a and b are both quadratic residues of the odd prime p, or both non-residues of p, show that the congruence ax²=b mod p has a solution [hint: multiply the given congruence by a', where aa'=1 mod p]

Need all the help i can get... pretty stuck. Thanks !

lazy proof of (1):

suppose a = x² (mod p), and b = y² (mod p).

then ab = x²y² = (xy)² (mod p).

the quadratic residues form a subgroup of the non-zero residues (mod p), this is a finite set, and we have closure.

now since p is an odd prime, (p-1)/2 is an integer.

by fermat's little theorem, a^p-1 = 1 (mod p), thus:

(a^(p-1)/2)² = a^p-1 = 1 (mod p).

hence a^(p-1)/2 is either of order 1 (that is = 1), or order 2 (that is = -1 = p - 1 (mod p) (Z_p)* is cyclic, so there is a unique element of order 2).

this creates a homomorphism (the legendre symbol homomorphism) from (Z_p)* to {-1,1}.

the kernel of this homomorphism is the quadratic residues, which is therefore a (normal) subgroup of index 2.

if we call this subgroup Q, we see the non-quadratic residues are "the other coset" xQ, for some non-residue x.

thus:
1. QQ = Q
2.Q(xQ) = (1x)Q = xQ
3.(xQ)Q = (x1)Q = xQ
4.(xQ)(xQ) = x²Q = Q (since x² is clearly a quadratic residue).

this is what we set out to prove.

for example, with p = 7 (working mod 7):

1² = 1
2² = 4
3² = 2
4² = 2 (not surprising: 4 = -3, and (-3)(-3) = (-1)(3)(-1)(3) = (-1)(-1)(3)(3) = (3)(3))
5² = 4
6² = 1

so Q = {1,2,4} ((7-1)/2 = 6/2 = 3 elements) and we may take x = 3, so 3Q = {3,6,5} (this is the same set as 5Q, or 6Q).

now (2) is straightforward:

a^-1(ax²) = a^-1b <---the RHS is in Q, by (1).

(a^-1a)x² = a^-1b,

x² = a^-1b (and we have a solution since a^-1b is in Q, that is aQ and bQ are the same coset).

wow, thanks so much!