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

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.

@@ Line 1: / Line 1: @@
 __NOTOC__
-<br /><br />
+{{User:Temperal/testtemplate|page 9}}
-{| style='background:lime;border-width: 5px;border-color: limegreen;border-style: outset;opacity: 0.8;width:840px;height:300px;position:relative;top:10px;'
+==<span style="font-size:20px; color: blue;">Advanced Number Theory</span>==
-|+ <span style="background:aqua; border:1px solid black; opacity: 0.6;font-size:30px;position:relative;bottom:8px;border-width: 5px;border-color:blue;border-style: groove;position:absolute;top:50px;right:155px;width:820px;height:40px;padding:5px;">The Problem Solver's Resource</span>
-|-
-| style="background:lime; border:1px solid black;height:200px;padding:10px;" | {{User:Temperal/testtemplate|page 9}}
-==<span style="font-size:20px; color: blue;">Derivatives</span>==
-This page will cover derivatives and their applications, as well as some advanced limits. The Fundamental Theorem of Calculus is covered on the [[User:Temperal/The Problem Solver's Resource10|integral page]].
-===Definition===
+[[User:Temperal/The Problem Solver's Resource8|Back to page 8]] | [[User:Temperal/The Problem Solver's Resource10|Continue to page 10]]
-*<math>\displaystyle\frac{df(x)}{dx}=\lim_{x->x_0}\frac{f(x_0)-f(x)}{x_0-x}</math>, where <math>f(x)</math> is a function continuous in <math>L</math>, and <math>x_0</math> is an arbitrary constant such that <math>x_0\subset L</math>.
+===Quadratic Reciprocity===
-*Multiple derivatives are taken by evaluating the innermost first, and can be notated as follows: <math>\frac{d^2f(x)}{dx^2}</math>.
+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.
-*The derivative of <math>f(x)</math> can also be expressed as <math>f'(x)</math>, or the <math>n</math>th derivative of <math>f(x)</math> can be expressed as <math>f^{(n)}(x)</math>.
+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.
-===Rolle's Theorem===
-If <math>f(x)</math> is differentiable in the open interval <math>(a,b)</math>, continuous in the closed interval <math>[a,b]</math>, and if <math>f(a)=f(b)</math>, then there is a point <math>c</math> between <math>a</math> and <math>b</math> such that <math>f'(c)=0</math>
-====Extension: Mean Value Theorem====
-If <math>f(x)</math> is differentiable in the open interval <math>(a,b)</math> and continuous in the closed interval <math>[a,b]</math>, then there is a point <math>c</math> between <math>a</math> and <math>b</math> such that <math>f(b)-f(a)=f'(c)\cdot(b-a)</math>.
-===L'Hopital's Rule===
-<math>\lim \frac{f(x)}{g(x)}=\lim \frac{f'(x)}{g'(x)}</math>
-Note that this inplies that <math>\lim \frac{f(x)}{g(x)}=\lim \frac{f^{(n)}(x)}{g^{(n)}(x)}</math> for any <math>n</math>.
+Adopting these definitions, we prove some theorems.
-===Taylor's Formula===
-Let <math>a</math> be a point in the domain of the function <math>f(x)</math>, and suppose that <math>f^{(n+1)}(x)</math> (that is, the <math>n+1</math>th derivative of <math>f(x)</math>) exists in the neighborhood of <math>a</math> (where <math>n</math> is a nonnegative integer). For each <math>x</math> in the neighborhood,
-<cmath>f(x)=f(a)+f'(a)(x-a)+\frac{f''(a)}{2!}(x-a)^2+...+\frac{f^{(n)}(a)}{n!}(x-a)^n+\frac{f^{(n+1)}(a)}{n!}(x-a)^{n+1}</cmath>
+Theorem 9.1. There are an equal number of non-residues and residues mod p.
-where <math>c</math> is in between <math>x</math> and <math>a</math>.
+'''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.
-[[User:Temperal/The Problem Solver's Resource8|Back to page 8]] | [[User:Temperal/The Problem Solver's Resource10|Continue to page 10]]
-|}<br /><br />

Page

Toolbox

Search

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

Latest revision as of 15:08, 11 January 2009

Advanced Number Theory

Quadratic Reciprocity