Modular arithmetic

Modular arithmetic a special type of arithmetic that involves only integers. If two integers ${a},{b}$ leave the same remainder when they are divided by some positive integer ${m}$ , we say that ${a}$ and $b$ are congruent modulo ${m}$ or $a\equiv b \pmod {m}$ .

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.

Simple 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.

Page

Toolbox

Search

Modular arithmetic

Contents

Operations

Simple Examples

Applications

Examples

See also