Modular arithmetic: Difference between revisions

Revision as of 22:30, 9 April 2025

Revision as of 00:24, 23 April 2025

Line 12:

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 [[modulo]] operation, 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