Editing Modular arithmetic (section)

== Basic properties ==
{{anchor|Properties}}
The congruence relation satisfies all the conditions of an [[equivalence relation]]:
* Reflexivity: {{math|''a'' ≡ ''a'' (mod ''m'')}} 
* Symmetry: {{math|''a'' ≡ ''b'' (mod ''m'')}} if {{math|''b'' ≡ ''a'' (mod ''m'')}}.
* Transitivity: If {{math|''a'' ≡ ''b'' (mod ''m'')}} and {{math|''b'' ≡ ''c'' (mod ''m'')}}, then {{math|''a'' ≡ ''c'' (mod ''m'')}}

If {{math|''a''<sub>1</sub> ≡ ''b''<sub>1</sub> (mod ''m'')}} and {{math|''a''<sub>2</sub> ≡ ''b''<sub>2</sub> (mod ''m'')}}, or if {{math|''a'' ≡ ''b'' (mod ''m'')}}, then:<ref>{{cite book |author1=Sandor Lehoczky |author2=Richard Rusczky |editor=David Patrick |title=the Art of Problem Solving |year=2006 |isbn=0977304566 |pages=44 |edition=7 |language=en| volume=1|publisher=AoPS Incorporated }}</ref>
* {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''m'')}} for any integer {{math|''k''}} (compatibility with translation)
* {{math|''k a'' ≡ ''k b'' (mod ''m'')}} for any integer {{math|''k''}} (compatibility with scaling)
* {{math|''k a'' ≡ ''k b'' (mod ''k m'')}} for any integer {{math|''k''}}
* {{math|''a''<sub>1</sub> + ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> + ''b''<sub>2</sub> (mod ''m'')}} (compatibility with addition)
* {{math|''a''<sub>1</sub> − ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> − ''b''<sub>2</sub> (mod ''m'')}} (compatibility with subtraction)
* {{math|''a''<sub>1</sub> ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> ''b''<sub>2</sub> (mod ''m'')}} (compatibility with multiplication)
* {{math|''a''<sup>''k''</sup> ≡ ''b''<sup>''k''</sup> (mod ''m'')}} for any non-negative integer {{math|''k''}} (compatibility with exponentiation)
* {{math|''p''(''a'') ≡ ''p''(''b'') (mod ''m'')}}, for any [[polynomial]] {{math|''p''(''x'')}} with integer coefficients (compatibility with polynomial evaluation)

If {{math|''a'' ≡ ''b'' (mod ''m'')}}, then it is generally false that {{math|''k<sup>a</sup>'' ≡ ''k<sup>b</sup>'' (mod ''m'')}}. However, the following is true:
* If {{math|''c'' ≡ ''d'' (mod ''φ''(''m'')),}} where {{math|''φ''}} is [[Euler's totient function]], then {{math|''a''<sup>''c''</sup> ≡ ''a''<sup>''d''</sup> (mod ''m'')}}—provided that {{math|''a''}} is [[coprime]] with {{math|''m''}}.

For cancellation of common terms, we have the following rules:
* If {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''m'')}}, where {{math|''k''}} is any integer, then {{math|''a'' ≡ ''b'' (mod ''m'')}}.
* If {{math|''k a'' ≡ ''k b'' (mod ''m'')}} and {{math|''k''}} is coprime with {{math|''m''}}, then {{math|''a'' ≡ ''b'' (mod ''m'')}}.
* If {{math|''k a'' ≡ ''k b'' (mod ''k m'')}} and {{math|''k'' ≠ 0}}, then {{math|''a'' ≡ ''b'' (mod ''m'')}}.

The last rule can be used to move modular arithmetic into division. If {{math|''b''}} divides {{math|''a''}}, then {{math|1=(''a''/''b'') mod ''m'' = (''a'' mod ''b m'') / ''b''}}.

The [[modular multiplicative inverse]] is defined by the following rules:
* Existence: There exists an integer denoted {{math|''a''<sup>−1</sup>}} such that {{math|''aa''<sup>−1</sup> ≡ 1 (mod ''m'')}} if and only if {{math|''a''}} is coprime with {{math|''m''}}. This integer {{math|''a''<sup>−1</sup>}} is called a ''modular multiplicative inverse'' of {{mvar|a}} modulo {{math|''m''}}.
* If {{math|''a'' ≡ ''b'' (mod ''m'')}} and {{math|''a''<sup>−1</sup>}} exists, then {{math|''a''<sup>−1</sup> ≡ ''b''<sup>−1</sup> (mod ''m'')}} (compatibility with multiplicative inverse, and, if {{math|1=''a'' = ''b''}}, uniqueness modulo {{math|''m''}}).
* If {{math|''ax'' ≡ ''b'' (mod ''m'')}} and {{math|''a''}} is coprime to {{math|''m''}}, then the solution to this linear congruence is given by {{math|''x'' ≡ ''a''<sup>−1</sup>''b'' (mod ''m'')}}.

The multiplicative inverse {{math|''x'' ≡ ''a''<sup>−1</sup> (mod ''m'')}}  may be efficiently computed by solving [[Bézout's identity|Bézout's equation]] {{math|1=''a x'' + ''m y'' = 1}} for {{math|''x''}}, {{math|''y''}}, by using the [[Extended Euclidean algorithm]].

In particular, if {{math|''p''}} is a prime number, then {{math|''a''}} is coprime with {{math|''p''}} for every {{math|''a''}} such that {{math|0 < ''a'' < ''p''}}; thus a multiplicative inverse exists for all {{math|''a''}} that is not congruent to zero modulo {{math|''p''}}.