Difference between revisions of "Modular arithmetic"

(reorganized and started intermediate section)
 
(37 intermediate revisions by 8 users not shown)
Line 1: Line 1:
'''Modular arithmetic''' a special type of arithmetic that involves only [[integers]]. If two integers <math>{a},{b}</math> leave the same remainder when they are divided by some positive integer <math>{m}</math>, we say that <math>{a}</math> and <math>b</math> are congruent [[modulo]] <math>{m}</math> or <math>a\equiv b \pmod {m}</math>.
+
'''Modular arithmetic''' is a special type of arithmetic that involves only [[integers]]. Since modular arithmetic is such a broadly useful tool in [[number theory]], we divide its explanations into several levels:
 +
* [[Modular arithmetic/Introduction|Introduction to modular arithmetic]]
 +
* [[Intermediate modular arithmetic]]
 +
* [[Olympiad modular arithmetic]]
  
  
== Introductory ==
+
== Resources ==
=== Operations ===
+
=== Introductory Resources ===
 +
==== Books ====
 +
* The AoPS [http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?page_id=10 Introduction to Number Theory] by [[Mathew Crawford]].
 +
==== Classes ====
 +
* [http://www.artofproblemsolving.com/Classes/AoPS_C_ClassesS.php#begnum AoPS Introduction to Number Theory Course]
  
Consider four integers <math>{a},{b},{c},{d}</math> and a positive integer <math>{m}</math> such that <math>a\equiv b\pmod {m}</math> and <math>c\equiv d\pmod {m}</math>. In modular arithmetic, the following operations are allowed:
+
=== Intermediate Resources ===
 +
* [http://www.artofproblemsolving.com/Resources/Papers/SatoNT.pdf Number Theory Problems and Notes] by [[Naoki Sato]].
  
* Addition: <math>a+c\equiv b+d\pmod {m}</math>.
+
=== Olympiad Resources ===
* Substraction: <math>a-c\equiv b-d\pmod {m}</math>.
+
* [http://www.artofproblemsolving.com/Resources/Papers/SatoNT.pdf Number Theory Problems and Notes] by [[Naoki Sato]].
* Multiplication: <math>ac\equiv bd\pmod {m}</math>.
 
* Division: <math>\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}</math>, where <math>e</math> is a positive integer that divides <math>{a}</math> and <math>b</math>.
 
* Exponentiation: <math>a^e\equiv b^e\pmod {m}</math> where <math>e</math> is a positive integer.
 
 
 
=== Examples ===
 
 
 
* <math>{7}\equiv {1} \pmod {2}</math>
 
 
 
* <math>49^2\equiv 7^4\equiv (1)^4\equiv 1 \pmod {6}</math>
 
 
 
* <math>7a\equiv 14\pmod {49}\implies a\equiv 2\pmod {7}</math>
 
 
 
=== Applications ===
 
 
 
Modular arithmetic is an extremely useful tool in mathematics competitions. It enables us to easily solve [[Linear diophantine equations]], and it often helps with other [[Diophantine equations]] as well.
 
 
 
 
 
 
 
== Intermediate ==
 
=== Topics ===
 
* [[Fermat's Little Theorem]]
 
* [[Euler's Theorem]]
 
* [[Phi function]]
 
 
 
 
 
=== See also ===
 
 
 
* [[Number theory]]
 
* [[Quadratic residues]]
 

Latest revision as of 20:38, 19 July 2006

Modular arithmetic is a special type of arithmetic that involves only integers. Since modular arithmetic is such a broadly useful tool in number theory, we divide its explanations into several levels:


Resources

Introductory Resources

Books

Classes

Intermediate Resources

Olympiad Resources