Difference between revisions of "User:Temperal/The Problem Solver's Resource9"
(errata) |
(Added basic Quadratic Recipricoty, will add more theorems later) |
||
| (14 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
| − | + | {{User:Temperal/testtemplate|page 9}} | |
| − | + | ==<span style="font-size:20px; color: blue;">Advanced Number Theory</span>== | |
| − | |||
| − | |||
| − | |||
| − | ==<span style="font-size:20px; color: blue;"> | ||
| − | |||
[[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 
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.
