Quadratic Residues

By Brad Rodgers on Thursday, February 14, 2002 - 03:59 am:

How do I prove that "there are (p-1)/2 quadratic residues and (p-1)/2 non-residues of an odd prime p." This is theorem 84 in Hardy and Wright, and a 'proof' is given in the book, but I don't understand how any of the statements they give support this theorem. I'm interested in just a proof, not solely their proof, so there is no need to elaborate on the book (although I'd like to see ho it works, if anyone has the book).

Anyone have a proof?

Brad

By David Loeffler on Thursday, February 14, 2002 - 09:09 am:

Their proof looks fine to me - they exhibit (p-1)/2 quadratic residues, show that these are all incongruent, and that all others are congruent to one of these; hence there are precisely (p-1)/2 distinct (nonzero) quadratic residues. Where do you think there's a catch?

David

By William Astle on Thursday, February 14, 2002 - 09:11 am:

x

is a residue mod

p

if and only if there exists a

y

such that

y^{2} = x

(mod

p

). The residues mod

p

are the image of the mapping:

$f : Z / pZ \to Z / pZ$

with

$f ([y]) = [y]^{2}$

(where $[x]$ denotes the equivalence class of $x$ in $Z / pZ$ )

Suppose $f ([z]) = f ([y])$ then $[z]^{2} = [y]^{2}$ equivalently $(z - y) (z + y) = 0$ mod( $p$ ) equivalently $z = y$ (mod $p$ ) or $z = - y$ (mod $p$ ). Excluding $[p]$ (which is not considered a residue) therefore, each square in $Z / pZ$ is the square of two members of $Z / pZ$ (as for the integers). So there are $(p - 1) / 2$ residues and $(p - 1) / 2$ non residues.

Will

By David Loeffler on Thursday, February 14, 2002 - 09:22 am:

Third proof: for any p it is known that there exists an a(p) such that the powers of a(p) are 1,2,3..(p-1) (in some order). So the elements of Z/pZ are {1, a, a² , a³ , ... a^p-2 }
and it follows immediately that the squares mod p are {1, a² , a⁴ , ..., a^p-3 } - so there are (p-1)/2 of them.

(This proof is a little more high-powered, but once you know about generators it's trivial, as are a lot of other nice results concerning powers.)

David

By Brad Rodgers on Thursday, February 14, 2002 - 08:54 pm:

Ok, thanks. I see the Hardy and Wright proof now. Something about the phrasing in the book wasn't suggestive enough for me...

Thanks again,

Brad