|
|
| (26 intermediate revisions by 4 users not shown) |
| 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 equation|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]]
| |
| − | | |
| − | == Miscellany ==
| |
| − | | |
| − | === The binary operation "mod" ===
| |
| − | | |
| − | Related to the concept of congruence mod <math>n</math> is the binary operation '''<math>a</math> mod <math>n</math>''', which is used often in computer programming.
| |
| − | | |
| − | Recall that, by the [[Division Algorithm]], given any two integers <math>a</math> and <math>n</math>, with <math>n > 0</math>, we can find integers <math>q</math> and <math>r</math>, with <math>0 \leq r < n </math>, such that <math>a = nq + r</math>. The number <math>q</math> is called the ''quotient'', and the number <math>r</math> is called the ''remainder''. The operation ''<math>a</math> mod <math>n</math>'' returns the value of the remainder <math>r</math>. For example:
| |
| − | | |
| − | <math>15</math> mod <math>6 = 3</math>, since <math>15 = 6 \cdot 2 + 3</math>.
| |
| − | | |
| − | <math>35</math> mod <math>7 = 0</math>, since <math>35 = 7 \cdot 5 + 0</math>.
| |
| − | | |
| − | <math>-10</math> mod <math>8 = 6</math>, since <math>-10 = 8 \cdot -2 + 6</math>.
| |
| − | | |
| − | Observe that if <math>a</math> mod <math>n = r</math>, then we also have <math>a \equiv r</math> (mod <math>n</math>).
| |
