Difference between revisions of "Modular arithmetic"

Latest revision as of 19: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

@@ Line 1: / Line 1: @@
-'''Modular arithmetic''' is a special type of arithmetic that involves only [[integers]].  Given integers <math>a</math>, <math>b</math>, and <math>n</math>, with <math>n > 0</math>, we say that <math>a</math> is ''congruent to'' <math>b</math> ''modulo'' <math>n</math>, or <math>a \equiv b</math> (mod <math>n</math>), if the difference <math>{a - b}</math> is divisible by <math>n</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]]
-For a given positive integer <math>n</math>, the relation <math>a \equiv b</math> (mod <math>n</math>) is an [[equivalence relation]] on the set of integers.  This relation gives rise to an algebraic structure called '''the integers modulo <math>n</math>''' (usually known as "the integers mod <math>n</math>," or <math>\mathbb{Z}_n</math> for short).  This structure gives us a useful tool for solving a wide range of number-theoretic problems, including finding solutions to [[Diophantine equations]], testing whether certain large numbers are prime, and even some problems in cryptology.
+== Resources ==
+=== 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]
-== Introductory ==
+=== Intermediate Resources ===
-=== Useful Facts ===
+* [http://www.artofproblemsolving.com/Resources/Papers/SatoNT.pdf Number Theory Problems and Notes] by [[Naoki Sato]].
-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 [[identity | identities]] hold:
+=== Olympiad 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>.
-* Substraction: <math>a-c\equiv b-d\pmod {m}</math>.
-* 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 equation]]s, and it often helps with other [[Diophantine equation | Diophantine equations]] as well.
-== Intermediate ==
-=== Topics ===
-* [[Fermat's Little Theorem]]
-* [[Euler's Totient Theorem]]
-* [[Phi function]]
-=== See also ===
-* [[Number theory]]
-* [[Quadratic residues]]

Page

Toolbox

Search

Difference between revisions of "Modular arithmetic"

Latest revision as of 19:38, 19 July 2006

Contents

Resources

Introductory Resources

Books

Classes

Intermediate Resources

Olympiad Resources