View source for Modular arithmetic

{{short description|Computation modulo a fixed integer}}
{{About|the concept that uses the "''{{mvar|a}}&nbsp;(mod {{mvar|m}})''" notation|the binary operation ''mod({{mvar|a,m}})'' |modulo}}
[[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]] for [[integer]]s, 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 use of modular arithmetic is in the [[12-hour clock]], in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Simple addition would result in {{nowrap|7 + 8 {{=}} 15}}, but  15:00 reads as 3:00 on the clock face because clocks "wrap around" every 12 hours and the hour number starts again at zero when it reaches 12. We say that 15 is ''congruent'' to 3 modulo 12, written 15 &equiv; 3 (mod 12), so that 7 + 8 &equiv; 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 &equiv; 4 (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
: {{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''}}: 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''}},
where {{math|0 ≤ ''r'' < ''m''}} is the common remainder. We recover the previous relation ({{math|1=''a'' − ''b'' = ''k m''}}) by subtracting these two expressions and setting {{math|1=''k'' = ''p'' − ''q''.}}

Because the congruence modulo {{mvar|m}} is defined by the [[Divisor#Further notions and facts|divisibility]] by {{mvar|m}} and because {{math|−1}} is a [[Unit (ring theory)#Integer ring|unit]] in the ring of integers, a number is divisible by {{math|−''m''}} exactly if it is divisible by {{mvar|m}}.
This means that every non-zero integer {{mvar|m}} may be taken as modulus.
=== Examples ===
In modulus 12, one can assert that:
: {{math|38 ≡ 14 (mod 12)}}
because the difference is {{math|1=38 − 14 = 24 = 2 × 12}}, a multiple of {{math|12}}. Equivalently, {{math|38}} and {{math|14}} have the same remainder {{math|2}} when divided by {{math|12}}.

The definition of congruence also applies to negative values. For example:
: <math> \begin{align}
2 &\equiv -3 \pmod 5\\
-8 &\equiv \phantom{+}7 \pmod 5\\
-3 &\equiv -8 \pmod 5.
\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>
* {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''m'')}} for any integer {{math|''k''}} (compatibility with translation)
* {{math|''k a'' ≡ ''k b'' (mod ''m'')}} for any integer {{math|''k''}} (compatibility with scaling)
* {{math|''k a'' ≡ ''k b'' (mod ''k m'')}} for any integer {{math|''k''}}
* {{math|''a''<sub>1</sub> + ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> + ''b''<sub>2</sub> (mod ''m'')}} (compatibility with addition)
* {{math|''a''<sub>1</sub> − ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> − ''b''<sub>2</sub> (mod ''m'')}} (compatibility with subtraction)
* {{math|''a''<sub>1</sub> ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> ''b''<sub>2</sub> (mod ''m'')}} (compatibility with multiplication)
* {{math|''a''<sup>''k''</sup> ≡ ''b''<sup>''k''</sup> (mod ''m'')}} for any non-negative integer {{math|''k''}} (compatibility with exponentiation)
* {{math|''p''(''a'') ≡ ''p''(''b'') (mod ''m'')}}, for any [[polynomial]] {{math|''p''(''x'')}} with integer coefficients (compatibility with polynomial evaluation)

If {{math|''a'' ≡ ''b'' (mod ''m'')}}, then it is generally false that {{math|''k<sup>a</sup>'' ≡ ''k<sup>b</sup>'' (mod ''m'')}}. However, the following is true:
* If {{math|''c'' ≡ ''d'' (mod ''φ''(''m'')),}} where {{math|''φ''}} is [[Euler's totient function]], then {{math|''a''<sup>''c''</sup> ≡ ''a''<sup>''d''</sup> (mod ''m'')}}—provided that {{math|''a''}} is [[coprime]] with {{math|''m''}}.

For cancellation of common terms, we have the following rules:
* If {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''m'')}}, where {{math|''k''}} is any integer, then {{math|''a'' ≡ ''b'' (mod ''m'')}}.
* If {{math|''k a'' ≡ ''k b'' (mod ''m'')}} and {{math|''k''}} is coprime with {{math|''m''}}, then {{math|''a'' ≡ ''b'' (mod ''m'')}}.
* If {{math|''k a'' ≡ ''k b'' (mod ''k m'')}} and {{math|''k'' ≠ 0}}, then {{math|''a'' ≡ ''b'' (mod ''m'')}}.

The last rule can be used to move modular arithmetic into division. If {{math|''b''}} divides {{math|''a''}}, then {{math|1=(''a''/''b'') mod ''m'' = (''a'' mod ''b m'') / ''b''}}.

The [[modular multiplicative inverse]] is defined by the following rules:
* Existence: There exists an integer denoted {{math|''a''<sup>−1</sup>}} such that {{math|''aa''<sup>−1</sup> ≡ 1 (mod ''m'')}} if and only if {{math|''a''}} is coprime with {{math|''m''}}. This integer {{math|''a''<sup>−1</sup>}} is called a ''modular multiplicative inverse'' of {{mvar|a}} modulo {{math|''m''}}.
* If {{math|''a'' ≡ ''b'' (mod ''m'')}} and {{math|''a''<sup>−1</sup>}} exists, then {{math|''a''<sup>−1</sup> ≡ ''b''<sup>−1</sup> (mod ''m'')}} (compatibility with multiplicative inverse, and, if {{math|1=''a'' = ''b''}}, uniqueness modulo {{math|''m''}}).
* If {{math|''ax'' ≡ ''b'' (mod ''m'')}} and {{math|''a''}} is coprime to {{math|''m''}}, then the solution to this linear congruence is given by {{math|''x'' ≡ ''a''<sup>−1</sup>''b'' (mod ''m'')}}.

The multiplicative inverse {{math|''x'' ≡ ''a''<sup>−1</sup> (mod ''m'')}}  may be efficiently computed by solving [[Bézout's identity|Bézout's equation]] {{math|1=''a x'' + ''m y'' = 1}} for {{math|''x''}}, {{math|''y''}}, by using the [[Extended Euclidean algorithm]].

In particular, if {{math|''p''}} is a prime number, then {{math|''a''}} is coprime with {{math|''p''}} for every {{math|''a''}} such that {{math|0 < ''a'' < ''p''}}; thus a multiplicative inverse exists for all {{math|''a''}} that is not congruent to zero modulo {{math|''p''}}.

== Advanced properties ==
Some of the more advanced properties of congruence relations are the following:
* [[Fermat's little theorem]]: If {{math|''p''}} is prime and does not divide {{math|''a''}}, then {{math|''a''{{i sup|''p''−1}} ≡ 1 (mod ''p'')}}.
* [[Euler's theorem]]: If {{math|''a''}} and {{math|''m''}} are coprime, then {{math|''a''{{i sup|''φ''(''m'')}} ≡ 1 (mod ''m'')}}, where {{math|''φ''}} is [[Euler's totient function]].
* A simple consequence of Fermat's little theorem is that if {{math|''p''}} is prime, then {{math|''a''<sup>−1</sup> ≡ ''a''{{i sup|''p''−2}} (mod ''p'')}} is the multiplicative inverse of {{math|0 < ''a'' < ''p''}}. More generally, from Euler's theorem, if {{math|''a''}} and {{math|''m''}} are coprime, then {{math|''a''{{i sup|−1}} ≡ ''a''{{i sup|''φ''(''m'')−1}} (mod ''m'')}}. Hence, if {{math|''ax'' ≡ ''1'' (mod ''m'')}}, then {{math|''x'' ≡ ''a''{{i sup|''φ''(''m'')−1}} (mod ''m'')}}.
* Another simple consequence is that if {{math|''a'' ≡ ''b'' (mod ''φ''(''m''))}}, where {{math|''φ''}} is Euler's totient function, then {{math|''k''<sup>''a''</sup> ≡ ''k''<sup>''b''</sup> (mod ''m'')}} provided {{math|''k''}} is [[coprime]] with {{math|''m''}}.
* [[Wilson's theorem]]: {{math|''p''}} is prime if and only if {{math|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* [[Chinese remainder theorem]]: For any {{math|''a''}}, {{math|''b''}}  and coprime {{math|''m''}}, {{math|''n''}}, there exists a unique {{math|''x'' (mod ''mn'')}} such that {{math|''x'' ≡ ''a'' (mod ''m'')}} and {{math|''x'' ≡ ''b'' (mod ''n'')}}. In fact,  {{math|''x'' ≡ ''b m''<sub>''n''</sub><sup>−1</sup> ''m'' + ''a n''<sub>''m''</sub><sup>−1</sup> ''n'' (mod ''mn'')}} where {{math|''m''<sub>''n''</sub><sup>−1</sup>}} is the inverse of {{math|''m''}} modulo {{math|''n''}} and {{math|''n''<sub>''m''</sub><sup>−1</sup>}} is the inverse of {{math|''n''}} modulo {{math|''m''}}.
* [[Lagrange's theorem (number theory)|Lagrange's theorem]]: If {{math|''p''}} is prime and {{math|''f'' (''x'') {{=}} ''a''<sub>0</sub> ''x''<sup>''d''</sup> + ... + ''a''<sub>''d''</sub>}} is a [[polynomial]] with integer coefficients such that {{mvar|p}} is not a divisor of {{math|''a''<sub>0</sub>}}, then the congruence {{math|''f'' (''x'') ≡ 0 (mod ''p'')}}  has at most {{math|''d''}} non-congruent solutions.
* [[Primitive root modulo n|Primitive root modulo {{math|''m''}}]]: A number {{math|''g''}} is a primitive root modulo {{math|''m''}} if, for every integer {{math|''a''}} coprime to {{math|''m''}}, there is an integer {{math|''k''}} such that {{math|''g''<sup>''k''</sup> ≡ ''a'' (mod ''m'')}}. A primitive root modulo {{math|''m''}} exists if and only if {{math|''m''}} is equal to {{math|2, 4, ''p''<sup>''k''</sup>}} or {{math| 2''p''<sup>''k''</sup>}}, where {{math|''p''}} is an odd prime number and {{math|''k''}} is a positive integer. If a primitive root modulo {{math|''m''}} exists, then there are exactly {{math|''φ''(''φ''(''m''))}} such primitive roots, where {{math|''φ''}} is the Euler's totient function.
* [[Quadratic residue]]: An integer {{math|''a''}} is a quadratic residue modulo {{math|''m''}}, if there exists an integer {{math|''x''}} such that {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''m'')}}. [[Euler's criterion]] asserts that, if {{math|''p''}} is an odd prime, and {{mvar|a}} is not a multiple of {{mvar|p}}, then {{math|''a''}} is a quadratic residue modulo {{math|''p''}} if and only if
*: {{math|''a''{{i sup|(''p''−1)/2}} ≡ 1 (mod ''p'')}}.

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

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|k}} such that {{math|0 ≤ ''k'' < ''m''}} and {{math|''k'' ≡ ''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.

== Residue systems ==
Each residue class modulo {{math|''m''}} may be represented by any one of its members, although we usually represent each residue class by the smallest nonnegative integer which belongs to that class<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Modular Arithmetic|url=https://mathworld.wolfram.com/ModularArithmetic.html|access-date=2020-08-12|website=Wolfram MathWorld|language=en|archive-date=2023-07-14|archive-url=https://web.archive.org/web/20230714132828/https://mathworld.wolfram.com/ModularArithmetic.html|url-status=live}}</ref> (since this is the proper remainder which results from division). Any two members of different residue classes modulo {{math|''m''}} are incongruent modulo {{math|''m''}}. Furthermore, every integer belongs to one and only one residue class modulo {{math|''m''}}.<ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=90}}</ref>

The set of integers {{math|{{mset|0, 1, 2, ..., ''m'' − 1}}}} is called the '''least residue system modulo {{math|''m''}}'''. Any set of {{math|''m''}} integers, no two of which are congruent modulo {{math|''m''}}, is called a '''complete residue system modulo {{math|''m''}}'''.

The least residue system is a complete residue system, and a complete residue system is simply a set containing precisely one [[representative (mathematics)|representative]] of each residue class modulo {{math|''m''}}.<ref>{{harvtxt|Long|1972|p=78}}</ref> For example, the least residue system modulo {{math|4}} is {{math|{{mset|0, 1, 2, 3}}}}. Some other complete residue systems modulo {{math|4}} include:
* {{math|{{mset|1, 2, 3, 4}}}}
* {{math|{{mset|13, 14, 15, 16}}}}
* {{math|{{mset|−2, −1, 0, 1}}}}
* {{math|{{mset|−13, 4, 17, 18}}}}
* {{math|{{mset|−5, 0, 6, 21}}}}
* {{math|{{mset|27, 32, 37, 42}}}}

Some sets that are ''not'' complete residue systems modulo 4 are:
* {{math|{{mset|−5, 0, 6, 22}}}}, since {{math|6}} is congruent to {{math|22}} modulo {{math|4}}.
* {{math|{{mset|5, 15}}}}, since a complete residue system modulo {{math|4}} must have exactly {{math|4}} incongruent residue classes.<!-- This example is used in the following subsection so please do not alter it. -->

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

=== Covering systems ===
{{main|Covering system}}
Covering systems represent yet another type of residue system that may contain residues with varying moduli.

== 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 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).

For {{math|''m'' > 0}} one has
: <math>\mathbb{Z}/m\mathbb{Z} = \left\{ \overline{a}_m \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0}_m, \overline{1}_m, \overline{2}_m,\ldots, \overline{m{-}1}_m \right\}.</math>

When {{math|1=''m'' = 1}}, <math>\mathbb{Z}/m\mathbb{Z}</math> is the [[zero ring]]; when {{math|1=''m'' = 0}}, <math>\mathbb{Z}/m\mathbb{Z}</math> is not an [[empty set]]; rather, it is [[isomorphism|isomorphic]] to <math>\mathbb{Z}</math>, since {{math|1={{overline|''a''}}<sub>0</sub> = {{mset|''a''}}}}.

Addition, subtraction, and multiplication are defined on <math>\mathbb{Z}/m\mathbb{Z}</math> by the following rules:
* <math>\overline{a}_m + \overline{b}_m = \overline{(a + b)}_m</math>
* <math>\overline{a}_m - \overline{b}_m = \overline{(a - b)}_m</math>
* <math>\overline{a}_m \overline{b}_m = \overline{(a b)}_m.</math>

The properties given before imply that, with these operations, <math>\mathbb{Z}/m\mathbb{Z}</math> is a [[commutative ring]]. For example, in the ring <math>\mathbb{Z}/24\mathbb{Z}</math>, one has
: <math>\overline{12}_{24} + \overline{21}_{24} = \overline{33}_{24}= \overline{9}_{24}</math>
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 {{math|''k m''}} with <math>k\in\mathbb{Z}.</math>

Considered as a [[group (mathematics)|group]] under addition, <math>\mathbb Z/m\Z</math> is a [[cyclic group]], and all 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]] 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]].

In computer algebra, modular arithmetic is commonly used to limit the size of integer coefficients in intermediate calculations and data. It is used in [[polynomial factorization]], a problem for which all known efficient algorithms use modular arithmetic. It is used by the most efficient implementations of [[polynomial greatest common divisor]], exact [[linear algebra]] and [[Gröbner basis]] algorithms over the integers and the rational numbers. As posted on [[Fidonet]] in the 1980s and archived at [[Rosetta Code]], modular arithmetic was used to disprove [[Euler's sum of powers conjecture]] on a [[Sinclair QL]] [[microcomputer]] using just one-fourth of the integer precision used by a [[CDC 6600]] [[supercomputer]] to disprove it two decades earlier via a [[brute force search]].<ref>{{Cite web|title=Euler's sum of powers conjecture|url=https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#QL_SuperBASIC|access-date=2020-11-11|website=rosettacode.org|language=en|archive-date=2023-03-26|archive-url=https://web.archive.org/web/20230326025754/https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#QL_SuperBASIC|url-status=live}}</ref>

In computer science, modular arithmetic is often applied in [[bitwise operation]]s and other operations involving fixed-width, cyclic [[data structure]]s. The modulo operation, as implemented in many [[programming language]]s and [[calculator]]s, is an application of modular arithmetic that is often used in this context. The logical operator [[XOR]] sums 2 bits, modulo 2.

The use of [[long division]] to turn a fraction into a [[repeating decimal]] in any base b is equivalent to modular multiplication of b modulo the denominator. For example, for decimal, b = 10.

In music, arithmetic modulo 12 is used in the consideration of the system of [[twelve-tone equal temperament]], where [[octave]] and [[enharmonic]] equivalency occurs (that is, pitches in a 1:2 or 2:1 ratio are equivalent, and C-[[Sharp (music)|sharp]] is considered the same as D-[[Flat (music)|flat]]).

The method of [[casting out nines]] offers a quick check of decimal arithmetic computations performed by hand. It is based on modular arithmetic modulo 9, and specifically on the crucial property that 10 ≡ 1 (mod 9).

Arithmetic modulo 7 is used in algorithms that determine the day of the week for a given date. In particular, [[Zeller's congruence]] and the [[Doomsday algorithm]] make heavy use of modulo-7 arithmetic.

More generally, modular arithmetic also has application in disciplines such as [[law]] (e.g., [[Apportionment (politics)|apportionment]]), [[economics]] (e.g., [[game theory]]) and other areas of the [[social science]]s, where [[Proportional (fair division)|proportional]] division and allocation of resources plays a central part of the analysis.

== Computational complexity ==
Since modular arithmetic has such a wide range of applications, it is important to know how hard it is to solve a system of congruences. A linear system of congruences can be solved in [[polynomial time]] with a form of [[Gaussian elimination]], for details see [[linear congruence theorem]]. Algorithms, such as [[Montgomery reduction]], also exist to allow simple arithmetic operations, such as multiplication and [[Modular exponentiation|exponentiation modulo&nbsp;{{math|''m''}}]], to be performed efficiently on large numbers.

Some operations, like finding a [[discrete logarithm]] or a [[Quadratic congruences|quadratic congruence]] appear to be as hard as [[integer factorization]] and thus are a starting point for [[Cryptography|cryptographic algorithms]] and [[encryption]]. These problems might be [[NP-intermediate]].

Solving a system of non-linear modular arithmetic equations is [[NP-complete]].<ref>{{cite book |first1=M. R. |last1=Garey |first2=D. S. |last2=Johnson |title=Computers and Intractability, a Guide to the Theory of NP-Completeness |url=https://archive.org/details/computersintract0000gare |url-access=registration |publisher=W. H. Freeman |year=1979 |isbn=0716710447 }}</ref>

== See also ==
{{Div col|colwidth=25em}}
* [[Boolean ring]]
* [[Circular buffer]]
* [[Division (mathematics)]]
* [[Finite field]]
* [[Legendre symbol]]
* [[Modular exponentiation]]
* [[Modulo (mathematics)]]
* [[Multiplicative group of integers modulo n]]
* [[Pisano period]] (Fibonacci sequences modulo ''n'')
* [[Primitive root modulo n]]
* [[Quadratic reciprocity]]
* [[Quadratic residue]]
* [[Rational reconstruction (mathematics)]]
* [[Reduced residue system]]
* [[Serial number arithmetic]] (a special case of modular arithmetic)
* [[Two-element Boolean algebra]]
* Topics relating to the group theory behind modular arithmetic:
** [[Cyclic group]]
** [[Multiplicative group of integers modulo n]]
* Other important theorems relating to modular arithmetic:
** [[Carmichael function|Carmichael's theorem]]
** [[Chinese remainder theorem]]
** [[Euler's theorem]]
** [[Fermat's little theorem]] (a special case of Euler's theorem)
** [[Lagrange's theorem (group theory)|Lagrange's theorem]]
** [[Thue's lemma]]
{{div col end}}

== Notes ==
{{reflist}}

== References ==
* John L. Berggren. [https://www.britannica.com/EBchecked/topic/920687/modular-arithmetic "modular arithmetic"]. [[Encyclopædia Britannica]].
* {{Apostol IANT}}. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
* Maarten Bullynck "[https://web.archive.org/web/20131102014013/http://www.kuttaka.org/Gauss_Modular.pdf Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany]"
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Section 31.3: Modular arithmetic, pp.&nbsp;862–868.
* [http://genealogy.math.ndsu.nodak.edu/id.php?id=3545 Anthony Gioia], ''Number Theory, an Introduction'' Reprint (2001) Dover. {{isbn|0-486-41449-3}}.
* {{cite book |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |edition=2nd |publisher=[[D. C. Heath and Company]] |location=Lexington |lccn=77171950}}
* {{cite book |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |url=https://archive.org/details/elementsofnumber0000pett |url-access=registration |publisher=[[Prentice Hall]] |location=Englewood Cliffs |isbn=9780132683005 |lccn=71081766}}
* {{cite book |last=Sengadir |first=T. |title=Discrete Mathematics and Combinatorics |year=2009 |publisher=Pearson Education India |location=Chennai, India |isbn=978-81-317-1405-8 |oclc=778356123}}

== External links ==
* {{springer|title=Congruence|id=p/c024850}}
* In this [https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm modular art] article, one can learn more about applications of modular arithmetic in art.
* An [https://web.archive.org/web/20160220061222/http://mersennewiki.org/index.php/Modular_arithmetic article] on modular arithmetic on the GIMPS wiki
* [http://www.cut-the-knot.org/blue/Modulo.shtml Modular Arithmetic and patterns in addition and multiplication tables]

{{Number theory}}

[[Category:Modular arithmetic| ]]
[[Category:Finite rings]]
[[Category:Group theory]]
[[Category:Articles with example C code]]