Editing Modular arithmetic (section)

== Congruence ==
Given an [[integer]] {{math|''m'' ≥ 1}}, called a '''modulus''', two integers {{mvar|a}} and {{mvar|b}} are said to be '''congruent''' modulo {{mvar|m}}, if {{mvar|m}} is a [[divisor]] of their difference; that is, if there is an integer {{math|''k''}} such that
: {{math|1=''a'' − ''b'' = ''k m''}}.
Congruence modulo {{mvar|m}} is a [[congruence relation]], meaning that it is an [[equivalence relation]] that is compatible with [[addition]], [[subtraction]], and [[multiplication]]. Congruence modulo {{mvar|m}} is denoted by
: {{math|''a'' ≡ ''b'' (mod ''m'')}}.

The parentheses mean that {{math|(mod ''m'')}} applies to the entire equation, not just to the right-hand side (here, {{mvar|b}}). 

This notation is not to be confused with the notation {{math|''b'' mod ''m''}} (without parentheses), which refers to the remainder of {{math|''b''}} when divided by {{math|''m''}}, known as  the [[modulo]] operation: that is, {{math|''b'' mod ''m''}} denotes the unique integer {{mvar|r}} such that {{math|0 ≤ ''r'' < ''m''}} and {{math|''r'' ≡ ''b'' (mod ''m'')}}.

The congruence relation may be rewritten as
: {{math|1=''a'' = ''k m'' + ''b''}},
explicitly showing its relationship with [[Euclidean division]]. However, the {{math|''b''}} here need not be the remainder in the division of {{math|''a''}} by {{math|''m''.}} Rather, {{math|''a'' ≡ ''b'' (mod ''m'')}} asserts that {{math|''a''}} and {{math|''b''}} have the same [[remainder]] when divided by {{math|''m''}}. That is,
: {{math|1=''a'' = ''p m'' + ''r''}},
: {{math|1=''b'' = ''q m'' + ''r''}},
where {{math|0 ≤ ''r'' < ''m''}} is the common remainder. We recover the previous relation ({{math|1=''a'' − ''b'' = ''k m''}}) by subtracting these two expressions and setting {{math|1=''k'' = ''p'' − ''q''.}}

Because the congruence modulo {{mvar|m}} is defined by the [[Divisor#Further notions and facts|divisibility]] by {{mvar|m}} and because {{math|−1}} is a [[Unit (ring theory)#Integer ring|unit]] in the ring of integers, a number is divisible by {{math|−''m''}} exactly if it is divisible by {{mvar|m}}.
This means that every non-zero integer {{mvar|m}} may be taken as modulus.
=== Examples ===
In modulus 12, one can assert that:
: {{math|38 ≡ 14 (mod 12)}}
because the difference is {{math|1=38 − 14 = 24 = 2 × 12}}, a multiple of {{math|12}}. Equivalently, {{math|38}} and {{math|14}} have the same remainder {{math|2}} when divided by {{math|12}}.

The definition of congruence also applies to negative values. For example:
: <math> \begin{align}
2 &\equiv -3 \pmod 5\\
-8 &\equiv \phantom{+}7 \pmod 5\\
-3 &\equiv -8 \pmod 5.
\end{align}</math>