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 Resource6"

(link)
(topic)
Line 5: Line 5:
 
|-  
 
|-  
 
| style="background:lime; border:1px solid black;height:200px;padding:10px;" | {{User:Temperal/testtemplate|page 6}}
 
| style="background:lime; border:1px solid black;height:200px;padding:10px;" | {{User:Temperal/testtemplate|page 6}}
−
==<span style="font-size:20px; color: blue;">Modulos</span>==
+
==<span style="font-size:20px; color: blue;">Number Theory</span>==
−
This section covers [[modulo|modulos]].
+
This section covers [[number theory]], especially [[modulo]]s (moduli?).
−
==Definition==
+
==Definitions==
 
*<math>n\equiv a\pmod{b}</math> if <math>n</math> is the remainder when <math>a</math> is divided by <math>b</math> to give an integral amount.
 
*<math>n\equiv a\pmod{b}</math> if <math>n</math> is the remainder when <math>a</math> is divided by <math>b</math> to give an integral amount.
 +
*<math>a|b</math> (or <math>a</math> divides <math>b</math>) if <math>b=ka</math> for some [[integer]] <math>k</math>.
 
==Special Notation==
 
==Special Notation==
 
Occasionally, if two equivalent expressions are both modulated by the same number, the entire equation will be followed by the modulo.
 
Occasionally, if two equivalent expressions are both modulated by the same number, the entire equation will be followed by the modulo.
Line 16: Line 17:
 
If <math>a\equiv b \pmod{m}</math> and <math>c \equiv d \pmod{m}</math>, then <math>(a+c) \equiv (b+d) \pmod {m}</math>.  
 
If <math>a\equiv b \pmod{m}</math> and <math>c \equiv d \pmod{m}</math>, then <math>(a+c) \equiv (b+d) \pmod {m}</math>.  
  
 +
*<math>a \pmod{m} + b \pmod{m} \equiv (a + b) \pmod{m}</math>
  
−
<math>a \pmod{m} + b \pmod{m} \equiv (a + b) \pmod{m}</math>
+
*<math>a \pmod{m} - b \pmod{m} \equiv (a - b) \pmod{m}</math>
  
−
<math>a \pmod{m} - b \pmod{m} \equiv (a - b) \pmod{m}</math>
+
*<math>a \pmod{m} \cdot b \pmod{m} \equiv (a \cdot b) \pmod{m} </math>
  
−
<math>a \pmod{m} \cdot b \pmod{m} \equiv (a \cdot b) \pmod{m} </math>
+
===Fermat's Little Theorem===
 +
For a prime <math>p</math> and a number <math>a</math> such that <math>a\ne{p}</math>, <math>a^{p-1}\equiv 1 \pmod{p}</math>.
 +
===Wilson's Theorem===
 +
For a prime <math>p</math>, <math> (p-1)! \equiv -1 \pmod p</math>.
  
−
==Useful Theorems==
+
===Fermat-Euler Identitity===
−
Fermat's Little Theorem:For a prime <math>p</math> and a number <math>a</math> such that <math>a\ne{p}</math>, <math>a^{p-1}\equiv 1 \pmod{p}</math>.
+
If <math>gcd(a,m)=1</math>, then <math>a^{\phi{m}}\equiv1\pmod{m}</math>, where <math>\phi{m}</math> is the number of relatively prime  numbers lower than <math>m</math>.
  
−
Wilson's Theorem: For a prime <math>p</math>, <math> (p-1)! \equiv -1 \pmod p</math>.
+
===Gauss's Theorem===
 +
If <math>a|bc</math> and <math>(a,b) = 1</math>, then <math>a|c</math>.
  
 +
===Diverging-Converging Theorem===
 +
A series <math>\sum_{i=0}^{\infty}S_i</math> converges iff <math>\lim S_i=0</math>.
 +
 +
===Errata===
 +
All quadratic residues are <math>0</math> or <math>1\pmod{4}</math>and  <math>0</math>, <math>1</math>, or <math>4</math> <math>\pmod{8}</math>.
  
−
<!-- to be continued -->
 
 
[[User:Temperal/The Problem Solver's Resource5|Back to page 5]] | [[User:Temperal/The Problem Solver's Resource7|Continue to page 7]]
 
[[User:Temperal/The Problem Solver's Resource5|Back to page 5]] | [[User:Temperal/The Problem Solver's Resource7|Continue to page 7]]
 
|}<br /><br />
 
|}<br /><br />

Revision as of 12:12, 23 November 2007



The Problem Solver's Resource
Introduction | Other Tips and Tricks | Methods of Proof | You are currently viewing page 6.

Number Theory

This section covers number theory, especially modulos (moduli?).

Definitions

  • $n\equiv a\pmod{b}$ if $n$ is the remainder when $a$ is divided by $b$ to give an integral amount.
  • $a|b$ (or $a$ divides $b$) if $b=ka$ for some integer $k$.

Special Notation

Occasionally, if two equivalent expressions are both modulated by the same number, the entire equation will be followed by the modulo.

Properties

For any number there will be only one congruent number modulo $m$ between $0$ and $m-1$.

If $a\equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $(a+c) \equiv (b+d) \pmod {m}$.

  • $a \pmod{m} + b \pmod{m} \equiv (a + b) \pmod{m}$
  • $a \pmod{m} - b \pmod{m} \equiv (a - b) \pmod{m}$
  • $a \pmod{m} \cdot b \pmod{m} \equiv (a \cdot b) \pmod{m}$

Fermat's Little Theorem

For a prime $p$ and a number $a$ such that $a\ne{p}$, $a^{p-1}\equiv 1 \pmod{p}$.

Wilson's Theorem

For a prime $p$, $(p-1)! \equiv -1 \pmod p$.

Fermat-Euler Identitity

If $gcd(a,m)=1$, then $a^{\phi{m}}\equiv1\pmod{m}$, where $\phi{m}$ is the number of relatively prime numbers lower than $m$.

Gauss's Theorem

If $a|bc$ and $(a,b) = 1$, then $a|c$.

Diverging-Converging Theorem

A series $\sum_{i=0}^{\infty}S_i$ converges iff $\lim S_i=0$.

Errata

All quadratic residues are $0$ or $1\pmod{4}$and $0$, $1$, or $4$ $\pmod{8}$.

Back to page 5 | Continue to page 7



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