Re: quadratic residue proof

lazy proof of (1):

suppose a = x^{2} (mod p), and b = y^{2} (mod p).

then ab = x^{2}y^{2} = (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, a^{p-1} = 1 (mod p), thus:

(a^{(p-1)/2})^{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^{2}Q = Q (since x^{2} is clearly a quadratic residue).

this is what we set out to prove.

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

1^{2} = 1

2^{2} = 4

3^{2} = 2

4^{2} = 2 (not surprising: 4 = -3, and (-3)(-3) = (-1)(3)(-1)(3) = (-1)(-1)(3)(3) = (3)(3))

5^{2} = 4

6^{2} = 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^{2}) = a^{-1}b <---the RHS is in Q, by (1).

(a^{-1}a)x^{2} = a^{-1}b,

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

Re: quadratic residue proof