Difference between revisions of "Modular arithmetic"

Revision as of 20:53, 23 June 2006

Modular arithmetic is a special type of arithmetic that involves only integers. Given integers $a$ , $b$ , and $n$ , with $n > 0$ , we say that $a$ is congruent to $b$ modulo $n$ , or $a \equiv b$ (mod $n$ ), if the difference ${a - b}$ is divisible by $n$ .

For a given positive integer $n$ , the relation $a \equiv b$ (mod $n$ ) is an equivalence relation on the set of integers. This relation gives rise to an algebraic structure called the integers modulo $n$ (usually known as "the integers mod $n$ ," or $\mathbb{Z}_n$ 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.

Introductory

Useful Facts

Consider four integers ${a},{b},{c},{d}$ and a positive integer ${m}$ such that $a\equiv b\pmod {m}$ and $c\equiv d\pmod {m}$ . In modular arithmetic, the following identities hold:

Addition: $a+c\equiv b+d\pmod {m}$ .
Substraction: $a-c\equiv b-d\pmod {m}$ .
Multiplication: $ac\equiv bd\pmod {m}$ .
Division: $\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}$ , where $e$ is a positive integer that divides ${a}$ and $b$ .
Exponentiation: $a^e\equiv b^e\pmod {m}$ where $e$ is a positive integer.

Examples

${7}\equiv {1} \pmod {2}$

$49^2\equiv 7^4\equiv (1)^4\equiv 1 \pmod {6}$

$7a\equiv 14\pmod {49}\implies a\equiv 2\pmod {7}$

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.

@@ Line 25: / Line 25: @@
 === 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.
+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 ==

Page

Toolbox

Search

Difference between revisions of "Modular arithmetic"

Revision as of 20:53, 23 June 2006

Contents

Introductory

Useful Facts

Examples

Applications

Intermediate

Topics

See also