Modular arithmetic: Difference between revisions

Revision as of 22:18, 15 March 2025

Revision as of 15:33, 16 March 2025

Line 66:

The [[modular multiplicative inverse]] is defined by the following rules:

* Existence: There exists an integer denoted by {{math|''a''⁻¹}} such that {{math|''aa''⁻¹ ≡ 1 (mod ''m'')}} if and only if {{math|''a''}} is coprime with {{math|''m''}}. This integer {{math|''a''⁻¹}} is called a ''modular multiplicative inverse'' of {{mvar|a}} modulo {{math|''m''}}.

* If {{math|''a'' ≡ ''b'' (mod ''m'')}} and {{math|''a''⁻¹}} exists, then {{math|''a''⁻¹ ≡ ''b''⁻¹ (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''⁻¹''b'' (mod ''m'')}}.

Line 88:

== Congruence classes <span class="anchor" id="Residue"></span><span class="anchor" id="Residue class"></span><span class="anchor" id="Congruence class"></span> ==

The congruence relation is an [[equivalence relation]]. The [[equivalence class]] modulo {{mvar|m}} of an integer {{math|''a''}} is the set of all integers of the form {{math|''a'' + ''k m''}}, where {{mvar|k}} is any integer. It is called the '''congruence class''' or '''residue class''' of {{math|''a''}} modulo&nbsp;{{math|''m''}}, and may be denoted as {{math|(''a'' mod ''m'')}}, or as {{math|{{overline|''a''}}}} or {{math|[''a'']}} when the modulus {{math|''m''}} is known from the context.

Each residue class modulo&nbsp;{{math|''m''}} contains exactly one integer in the range <math>0, ..., |m| - 1</math>. Thus, these <math>|m|</math> integers are [[representative (mathematics)|representatives]] of their respective residue classes.