Modular arithmetic: Difference between revisions

Revision as of 23:25, 19 March 2025

Latest revision as of 12:54, 20 August 2025

(22 intermediate revisions by 15 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.

Line 152 ⟶ 154:

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]]. 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]].