Content deleted Content added
No edit summary |
→Basic properties: congruence equation Tag: Reverted |
||
Line 70:
* 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 equation 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]].
| |||