Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "User:Temperal/The Problem Solver's Resource9"

(hm)
(Added basic Quadratic Recipricoty, will add more theorems later)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
 
{{User:Temperal/testtemplate|page 9}}
 
{{User:Temperal/testtemplate|page 9}}
−
==<span style="font-size:20px; color: blue;">Complex Numbers</span>==
+
==<span style="font-size:20px; color: blue;">Advanced Number Theory</span>==
  
 
[[User:Temperal/The Problem Solver's Resource8|Back to page 8]] | [[User:Temperal/The Problem Solver's Resource10|Continue to page 10]]
 
[[User:Temperal/The Problem Solver's Resource8|Back to page 8]] | [[User:Temperal/The Problem Solver's Resource10|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 <math>a^2 \equiv m \pmod{n}</math> and <math>0 \le m < n.</math>. For example, since <math>5^2 \equiv 4 \pmod{7},</math> 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 <math>1^2, 2^2, ... (\frac{p-1}{2})^2</math> are distinct modulo p. Assume <math>a^2 \equiv b^2 \pmod{p},</math> where a and b are distinct integers from <math>1</math> to <math>\frac{p-1}{2}.</math> Then, <math>a^2-b^2</math> would have to be a multiple of <math>p</math>. <math>a^2-b^2</math> can be factored as <math>(a-b)(a+b).</math> However, since a and b are distinct integers from <math>1</math> to <math>\frac{p-1}{2},</math> <math>a-b</math> can't be a multiple of p. Therefore, <math>a+b</math> is a multiple of p. We know that <math>\frac{p-1}{2} \ge a,b \ge 1,</math> so <math>p-1 \ge a+b \ge 2,</math> so <math>a+b</math> also can't be a multiple of p, a contradiction.

Latest revision as of 15:08, 11 January 2009

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=User:Temperal/The_Problem_Solver%27s_Resource9&oldid=29472"