Difference between revisions of "Modular arithmetic"

 
(See also)
Line 29: Line 29:
 
=== See also ===
 
=== See also ===
  
 +
* [[Number theory]]
 
* [[Quadratic residues]]
 
* [[Quadratic residues]]

Revision as of 09:45, 18 June 2006

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}$.

Operations

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 operations are allowed:

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

Examples

See also