User:Temperal/The Problem Solver's Resource9

From AoPSWiki

Introduction \| Other Tips and Tricks \| Methods of Proof \| You are currently viewing page 9.

Advanced Number Theory

Back to page 8 | Continue to page 10

Quadratic Reciprocity

A number m is a quadratic residue mod n if and only there exists a number a such that $a^2 \equiv m \pmod{n}$ and $0 \le m < n.$ . For example, since $5^2 \equiv 4 \pmod{7},$ 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 $1^2, 2^2, ... (\frac{p-1}{2})^2$ are distinct modulo p. Assume $a^2 \equiv b^2 \pmod{p},$ where a and b are distinct integers from $1$ to $\frac{p-1}{2}.$ Then, $a^2-b^2$ would have to be a multiple of $p$ . $a^2-b^2$ can be factored as $(a-b)(a+b).$ However, since a and b are distinct integers from $1$ to $\frac{p-1}{2},$ $a-b$ can't be a multiple of p. Therefore, $a+b$ is a multiple of p. We know that $\frac{p-1}{2} \ge a,b \ge 1,$ so $p-1 \ge a+b \ge 2,$ so $a+b$ also can't be a multiple of p, a contradiction.

Personal tools

Navigation

Search

Toolbox

User:Temperal/The Problem Solver's Resource9

From AoPSWiki

Advanced Number Theory

Quadratic Reciprocity