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 ax2=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 !

2. ## Re: quadratic residue proof

lazy proof of (1):

suppose a = x2 (mod p), and b = y2 (mod p).

then ab = x2y2 = (xy)2 (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, ap-1 = 1 (mod p), thus:

(a(p-1)/2)2 = ap-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) (Zp)* is cyclic, so there is a unique element of order 2).

this creates a homomorphism (the legendre symbol homomorphism) from (Zp)* 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) = x2Q = Q (since x2 is clearly a quadratic residue).

this is what we set out to prove.

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

12 = 1
22 = 4
32 = 2
42 = 2 (not surprising: 4 = -3, and (-3)(-3) = (-1)(3)(-1)(3) = (-1)(-1)(3)(3) = (3)(3))
52 = 4
62 = 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(ax2) = a-1b <---the RHS is in Q, by (1).

(a-1a)x2 = a-1b,

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

3. ## Re: quadratic residue proof

wow, thanks so much!