User:Temperal/The Problem Solver's Resource9
|Introduction | Other Tips and Tricks | Methods of Proof | You are currently viewing page 9.|
Advanced Number Theory
A number m is a quadratic residue mod n if and only there exists a number a such that and . For example, since 4 is a quadratic residue mod 7.
Let p be an odd prime. There are some theorems regarding quadratic residues mod p. Usually, 0 is a "special case." So 0 is not a residue, but it is also not a non-residue.
Adopting these definitions, we prove some theorems.
Theorem 9.1. There are an equal number of non-residues and residues mod p.
Proof: First, we prove that are distinct modulo p. Assume where a and b are distinct integers from to Then, would have to be a multiple of . can be factored as However, since a and b are distinct integers from to can't be a multiple of p. Therefore, is a multiple of p. We know that so so also can't be a multiple of p, a contradiction.