Editing Modular arithmetic (section)

== Advanced properties ==
Some of the more advanced properties of congruence relations are the following:
* [[Fermat's little theorem]]: If {{math|''p''}} is prime and does not divide {{math|''a''}}, then {{math|''a''{{i sup|''p''−1}} ≡ 1 (mod ''p'')}}.
* [[Euler's theorem]]: If {{math|''a''}} and {{math|''m''}} are coprime, then {{math|''a''{{i sup|''φ''(''m'')}} ≡ 1 (mod ''m'')}}, where {{math|''φ''}} is [[Euler's totient function]].
* A simple consequence of Fermat's little theorem is that if {{math|''p''}} is prime, then {{math|''a''<sup>−1</sup> ≡ ''a''{{i sup|''p''−2}} (mod ''p'')}} is the multiplicative inverse of {{math|0 < ''a'' < ''p''}}. More generally, from Euler's theorem, if {{math|''a''}} and {{math|''m''}} are coprime, then {{math|''a''{{i sup|−1}} ≡ ''a''{{i sup|''φ''(''m'')−1}} (mod ''m'')}}. Hence, if {{math|''ax'' ≡ ''1'' (mod ''m'')}}, then {{math|''x'' ≡ ''a''{{i sup|''φ''(''m'')−1}} (mod ''m'')}}.
* Another simple consequence is that if {{math|''a'' ≡ ''b'' (mod ''φ''(''m''))}}, where {{math|''φ''}} is Euler's totient function, then {{math|''k''<sup>''a''</sup> ≡ ''k''<sup>''b''</sup> (mod ''m'')}} provided {{math|''k''}} is [[coprime]] with {{math|''m''}}.
* [[Wilson's theorem]]: {{math|''p''}} is prime if and only if {{math|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* [[Chinese remainder theorem]]: For any {{math|''a''}}, {{math|''b''}}  and coprime {{math|''m''}}, {{math|''n''}}, there exists a unique {{math|''x'' (mod ''mn'')}} such that {{math|''x'' ≡ ''a'' (mod ''m'')}} and {{math|''x'' ≡ ''b'' (mod ''n'')}}. In fact,  {{math|''x'' ≡ ''b m''<sub>''n''</sub><sup>−1</sup> ''m'' + ''a n''<sub>''m''</sub><sup>−1</sup> ''n'' (mod ''mn'')}} where {{math|''m''<sub>''n''</sub><sup>−1</sup>}} is the inverse of {{math|''m''}} modulo {{math|''n''}} and {{math|''n''<sub>''m''</sub><sup>−1</sup>}} is the inverse of {{math|''n''}} modulo {{math|''m''}}.
* [[Lagrange's theorem (number theory)|Lagrange's theorem]]: If {{math|''p''}} is prime and {{math|''f'' (''x'') {{=}} ''a''<sub>0</sub> ''x''<sup>''d''</sup> + ... + ''a''<sub>''d''</sub>}} is a [[polynomial]] with integer coefficients such that {{mvar|p}} is not a divisor of {{math|''a''<sub>0</sub>}}, then the congruence {{math|''f'' (''x'') ≡ 0 (mod ''p'')}}  has at most {{math|''d''}} non-congruent solutions.
* [[Primitive root modulo n|Primitive root modulo {{math|''m''}}]]: A number {{math|''g''}} is a primitive root modulo {{math|''m''}} if, for every integer {{math|''a''}} coprime to {{math|''m''}}, there is an integer {{math|''k''}} such that {{math|''g''<sup>''k''</sup> ≡ ''a'' (mod ''m'')}}. A primitive root modulo {{math|''m''}} exists if and only if {{math|''m''}} is equal to {{math|2, 4, ''p''<sup>''k''</sup>}} or {{math| 2''p''<sup>''k''</sup>}}, where {{math|''p''}} is an odd prime number and {{math|''k''}} is a positive integer. If a primitive root modulo {{math|''m''}} exists, then there are exactly {{math|''φ''(''φ''(''m''))}} such primitive roots, where {{math|''φ''}} is the Euler's totient function.
* [[Quadratic residue]]: An integer {{math|''a''}} is a quadratic residue modulo {{math|''m''}}, if there exists an integer {{math|''x''}} such that {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''m'')}}. [[Euler's criterion]] asserts that, if {{math|''p''}} is an odd prime, and {{mvar|a}} is not a multiple of {{mvar|p}}, then {{math|''a''}} is a quadratic residue modulo {{math|''p''}} if and only if
*: {{math|''a''{{i sup|(''p''−1)/2}} ≡ 1 (mod ''p'')}}.