Content deleted Content added
→Basic properties: ni I didnt Tags: Reverted Mobile edit Mobile app edit Android app edit App section source |
|||
(8 intermediate revisions by 7 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}})'' |
{{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 40 ⟶ 41:
\end{align}</math>
== Basic properties ==
{{anchor|Properties}}
The congruence relation satisfies all the conditions of an [[equivalence relation]]:
* Reflexivity: {{math|''a'' ≡ ''a'' (mod ''m'')}}
* Symmetry: {{math|''a'' ≡ ''b'' (mod ''m'')}} if {{math|''b'' ≡ ''a'' (mod ''m'')}}.
* Transitivity: If {{math|''a'' ≡ ''b'' (mod ''m'')}} and {{math|''b'' ≡ ''c'' (mod ''m'')}}, then {{math|''a'' ≡ ''c'' (mod ''m'')}}
If {{math|''a''<sub>1</sub> ≡ ''b''<sub>1</sub> (mod ''m'')}} and {{math|''a''<sub>2</sub> ≡ ''b''<sub>2</sub> (mod ''m'')}}, or if {{math|''a'' ≡ ''b'' (mod ''m'')}}, then:<ref>{{cite book |author1=Sandor Lehoczky |author2=Richard Rusczky |editor=David Patrick |title=the Art of Problem Solving |year=2006 |isbn=0977304566 |pages=44 |edition=7 |language=en| volume=1|publisher=AoPS Incorporated }}</ref>
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 4.
|