Modular arithmetic: Difference between revisions

Content deleted Content added
m Applications: Still too wordy.
Reverted 1 edit by Nihilux (talk): Do not mix raw html and math formtting inside formulas
 
(17 intermediate revisions by 12 users not shown)
Line 1:
{{short description|Computation modulo a fixed integer}}
{{About|the concept that uses the "''{{mvar|a}} (mod {{mvar|m}})''" notation|the binary operation ''mod({{mvar|a,m}})'' |moduloModulo}}
{{More citations needed|date=June 2025}}
[[File:Clock group.svg|thumb|upright=1.1|right|Time-keeping on this clock uses arithmetic modulo 12. Adding 4 hours to 9 o'clock gives 1 o'clock, since 13 is congruent to 1 modulo 12.]]
 
Line 12 ⟶ 13:
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
Line 96 ⟶ 97:
It is generally easier to work with integers than sets of integers; that is, the representatives most often considered, rather than their residue classes.
 
Consequently, {{math|(''a'' mod ''m'')}} denotes generally the unique integer {{mvar|kr}} such that {{math|0 ≤ ''kr'' < ''m''}} and {{math|''kr'' ≡ ''a'' (mod ''m'')}}; it is called the '''residue''' of {{math|''a''}} modulo&nbsp;{{math|''m''}}.
 
In particular, {{math|1=(''a'' mod ''m'') = (''b'' mod ''m'')}} is equivalent to {{math|''a'' ≡ ''b'' (mod ''m'')}}, and this explains why "{{math|1==}}" is often used instead of "{{math|≡}}" in this context.
Line 119 ⟶ 120:
=== Reduced residue systems ===
{{main|Reduced residue system}}
 
Given the [[Euler's totient function]] {{math|''φ''(''m'')}}, any set of {{math|''φ''(''m'')}} integers that are [[Coprime integers|relatively prime]] to {{math|''m''}} and mutually incongruent under modulus {{math|''m''}} is called a '''reduced residue system modulo {{math|''m''}}'''.<ref>{{harvtxt|Long|1972|p=85}}</ref> The set {{math|{{mset|5, 15}}}} from above, for example, is an instance of a reduced residue system modulo&nbsp;4.