Modular arithmetic: Difference between revisions

Content deleted Content added
Congruence: and another
Reverted 1 edit by Nihilux (talk): Do not mix raw html and math formtting inside formulas
 
(47 intermediate revisions by 20 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.]]
 
In [[mathematics]], '''modular arithmetic''' is a system of [[arithmetic]] operations for [[integer]]s, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the '''modulus'''. The modern approach to modular arithmetic was developed by [[Carl Friedrich Gauss]] in his book ''[[Disquisitiones Arithmeticae]]'', published in 1801.
 
A familiar useexample of modular arithmetic is in the hour hand on a [[12-hour clock]],. in whichIf the day is divided into two 12-hour periods.hand Ifpoints the time isto 7:00 now, then 8 hours later it will bepoint to 3:00. SimpleOrdinary addition would result in {{nowrap|7 + 8 {{=}} 15}}, but 15:00 reads as 3:00 on the clock face. This is because clocksthe hour hand makes "wrapone around"rotation every 12 hours and the hour number starts over atwhen zerothe whenhour ithand reachespasses 12. We say that 15 is ''congruent'' to 3 modulo 12, written 15 ≡ 3 (mod 12), so that 7 + 8 ≡ 3 (mod 12). Similarly, 8:00 represents a period of 8 hours, and twice this would give 16:00, which reads as 4:00 on the clock face, written as 2 × 8 ≡ 4 (mod 12).
 
Similarly, if one starts at 12 and waits 8 hours, the hour hand will be at 8. If one instead waited twice as long, 16 hours, the hour hand would be on 4. This can be written as 2 × 8 ≡ 4 (mod 12). Note that after a wait of exactly 12 hours, the hour hand will always be right where it was before, so 12 acts the same as zero, thus 12 ≡ 0 (mod 12).
 
== Congruence ==
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 the operations of [[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
: {{math|1=''a'' = ''k m'' + ''b''}},
explicitly showing its relationship with [[Euclidean division]]. However, the {{math|''b''}} here need not be the remainder in the division of {{math|''a''}} by {{math|''m''.}} Rather, {{math|''a'' ≡ ''b'' (mod ''m'')}} asserts that {{math|''a''}} and {{math|''b''}} have the same [[remainder]] when divided by {{math|''m''}}. That is,
: {{math|1=''a'' = ''p m'' + ''r''}},
: {{math|1=''b'' = ''q m'' + ''r''}},
Line 34 ⟶ 37:
: <math> \begin{align}
2 &\equiv -3 \pmod 5\\
-8 &\equiv \phantom{+}7 \pmod 5\\
-3 &\equiv -8 \pmod 5.
\end{align}</math>
Line 88 ⟶ 91:
 
== 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.
Line 94 ⟶ 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 117 ⟶ 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.
 
Line 124 ⟶ 128:
 
== Integers modulo ''m'' ==
Remark: In the context of this paragraph, the modulus {{math|''m''}} is almost always taken as positive.
 
The set of all [[#Congruence classes|congruence classes]] modulo {{math|''m''}} is a [[ring (mathematics)|ring]] called the '''ring of integers modulo {{math|''m''}}''',<ref>It is a [[ring (mathematics)|ring]], as shown below.</ref> and is denoted <math display=inline>\mathbb{Z}/m\mathbb{Z}</math>, <math>\mathbb{Z}/m</math>, or <math>\mathbb{Z}_m</math>.<ref>{{Cite web|date=2013-11-16|title=2.3: Integers Modulo n|url=https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Book%3A_Introduction_to_Algebraic_Structures_(Denton)/02%3A_Groups_I/2.03%3A_Integers_Modulo_n|access-date=2020-08-12|website=Mathematics LibreTexts|language=en|archive-date=2021-04-19|archive-url=https://web.archive.org/web/20210419035455/https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Book%3A_Introduction_to_Algebraic_Structures_(Denton)/02%3A_Groups_I/2.03%3A_Integers_Modulo_n|url-status=live}}</ref>
The notation <math>\mathbb{Z}_m</math> is, however, not recommended because it can be confused with the set of [[P-adic integer|{{math|''m''}}-adic integers]]. The [[ring (mathematics)|ring]] <math>\mathbb{Z}/m\mathbb{Z}</math> is fundamental to various branches of mathematics (see ''{{section link|#Applications}}'' below).
(In some parts of [[number theory]] the notation <math>\mathbb{Z}_m</math> is avoided because it can be confused with the set of [[P-adic integer|{{math|''m''}}-adic integers]].)
 
For {{math|''m'' > 0}} one has
Line 142 ⟶ 148:
as in the arithmetic for the 24-hour clock.
 
The notation <math>\mathbb{Z}/m\mathbb{Z}</math> is used because this ring is the [[quotient ring]] of <math>\mathbb{Z}</math> by the [[ideal (ring theory)|ideal]] <math>m\mathbb{Z}</math>, the set formed by all multiples of {{math|''m''}}, i.e., all numbers {{math|''k m''}} with <math>k\in\mathbb{Z}.</math>
 
Considered as a [[group (mathematics)|group]] underUnder addition, <math>\mathbb Z/m\Z</math> is a [[cyclic group]],. andAll allfinite cyclic groups are isomorphic with <math>\mathbb Z/m\mathbb Z</math> for some {{mvar|m}}.<ref>Sengadir T., {{Google books|id=nglisrt9IewC|page=293|text=Zn is generated by 1|title=Discrete Mathematics and Combinatorics}}</ref>
 
The ring of integers modulo {{math|''m''}} is a [[field (mathematics)|field]], i.e., every nonzero element has a [[Modular multiplicative inverse|multiplicative inverse]], if and only if {{math|''m''}} is [[Prime number|prime]] (this ensures that every nonzero element has a [[Modular multiplicative inverse|multiplicative inverse]]). If {{math|1=''m'' = ''p''{{i sup|''k''}}}} is a [[prime power]] with {{math|''k'' > 1}}, there exists a unique (up to isomorphism) finite field <math>\mathrm{GF}(m) =\mathbb F_m</math> with {{math|''m''}} elements, which is ''not'' isomorphic to <math>\mathbb Z/m\mathbb Z</math>, which fails to be a field because it has [[zero-divisor]]s.
 
If {{math|''m'' > 1}}, <math>(\mathbb Z/m\mathbb Z)^\times</math> denotes the [[multiplicative group of integers modulo n|multiplicative group of the integers modulo {{math|''m''}}]] that are invertible. It consists of the congruence classes {{math|{{overline|''a''}}{{sub|''m''}}}}, where {{math|''a''}} [[coprime integers|is coprime]] to {{math|''m''}}; these are precisely the classes possessing a multiplicative inverse. They form an [[abelian group]] under multiplication; its order is {{math|''φ''(''m'')}}, where {{mvar|φ}} is [[Euler's totient function]].
 
== Applications ==
In pure mathematics, modular arithmetic is one of the foundations of [[number theory]], touching on almost every aspect of its study, and it is also used extensively in [[group theory]], [[ring theory]], [[knot theory]], and [[abstract algebra]]. In applied mathematics, it is used in [[computer algebra]], [[cryptography]], [[computer science]], [[chemistry]] and the [[visual arts|visual]] and [[music]]al arts.
 
A very practical application is to calculate checksums within serial number identifiers. For example, [[International Standard Book Number]] (ISBN) uses modulo 11 (for 10-digit ISBN) or modulo 10 (for 13-digit ISBN) arithmetic for error detection. Likewise, [[International Bank Account Number]]s (IBANs), for example, make use of modulo 97 arithmetic to spot user input errors in bank account numbers. In chemistry, the last digit of the [[CAS registry number]] (a unique identifying number for each chemical compound) is a [[check digit]], which is calculated by taking the last digit of the first two parts of the CAS registry number times 1, the previous digit times 2, the previous digit times 3 etc., adding all these up and computing the sum modulo 10.
 
In cryptography, modular arithmetic directly underpins [[Public-key cryptography|public key]] systems such as [[RSA (algorithm)|RSA]] and [[Diffie–Hellman key exchange|Diffie–Hellman]], and provides [[finite field]]s which underlie [[elliptic curve]]s, and is used in a variety of [[symmetric key algorithm]]s including [[Advanced Encryption Standard]] (AES), [[International Data Encryption Algorithm]] (IDEA), and [[RC4]]. RSA and Diffie–Hellman use [[modular exponentiation]].