Modular arithmetic

<h2 id="congruence">Congruence</h2>
Given an <a href="/facts/Integer/PUwwrawx">integer</a> m ≥ 1, called a modulus, two integers a and b are said to be congruent modulo m, if m is a <a href="/facts/Divisor/DKNa2GvC">divisor</a> of their difference; that is, if there is an integer k such that

a − b = k m.
Congruence modulo m is a <a href="/facts/Congruence_relation/TV3njpqF">congruence relation</a>, meaning that it is an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a> that is compatible with <a href="/facts/Addition/apFWJBFB">addition</a>, <a href="/facts/Subtraction/dEUrp6k0">subtraction</a>, and <a href="/facts/Multiplication/VtcUjpNv">multiplication</a>. Congruence modulo m is denoted by

a ≡ b (mod m).
The parentheses mean that (mod m) applies to the entire equation, not just to the right-hand side (here, b). 
This notation is not to be confused with the notation b mod m (without parentheses), which refers to the remainder of b when divided by m, known as the <a href="/facts/Modulo/RSHgnLDY">modulo</a> operation: that is, b mod m denotes the unique integer r such that 0 ≤ r < m and r ≡ b (mod m).
The congruence relation may be rewritten as

a = k m + b,
explicitly showing its relationship with <a href="/facts/Euclidean_division/hgNk37et">Euclidean division</a>. However, the b here need not be the remainder in the division of a by m. Rather, a ≡ b (mod m) asserts that a and b have the same <a href="/facts/Remainder/wCmbYeeh">remainder</a> when divided by m. That is,

a = p m + r,
b = q m + r,
where 0 ≤ r < m is the common remainder. We recover the previous relation (a − b = k m) by subtracting these two expressions and setting k = p − q.
Because the congruence modulo m is defined by the <a href="/facts/Divisor/DKNa2GvC">divisibility</a> by m and because −1 is a <a href="/facts/Unit_(ring_theory)/GJSBu8Y7">unit</a> in the ring of integers, a number is divisible by −m exactly if it is divisible by m.
This means that every non-zero integer m may be taken as modulus.

<h3>Examples</h3>
In modulus 12, one can assert that:

38 ≡ 14 (mod 12)
because the difference is 38 − 14 = 24 = 2 × 12, a multiple of 12. Equivalently, 38 and 14 have the same remainder 2 when divided by 12.
The definition of congruence also applies to negative values. For example:

2
              
              
                
                ≡
                −
                3
                
                  
                  (
                  mod
                  
                  5
                  )
                
              
            
            
              
                −
                8
              
              
                
                ≡
                
                  
                    
                      +
                    
                  
                
                7
                
                  
                  (
                  mod
                  
                  5
                  )
                
              
            
            
              
                −
                3
              
              
                
                ≡
                −
                8
                
                  
                  (
                  mod
                  
                  5
                  )
                
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv {\phantom {+}}7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}

<h2 id="basic-properties">Basic properties</h2>

The congruence relation satisfies all the conditions of an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a>:

<ul><li>Reflexivity: a ≡ a (mod m)</li>
<li>Symmetry: a ≡ b (mod m) if b ≡ a (mod m).</li>
<li>Transitivity: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m)</li></ul>
If a1 ≡ b1 (mod m) and a2 ≡ b2 (mod m), or if a ≡ b (mod m), then:<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

<ul><li>a + k ≡ b + k (mod m) for any integer k (compatibility with translation)</li>
<li>k a ≡ k b (mod m) for any integer k (compatibility with scaling)</li>
<li>k a ≡ k b (mod k m) for any integer k</li>
<li>a1 + a2 ≡ b1 + b2 (mod m) (compatibility with addition)</li>
<li>a1 − a2 ≡ b1 − b2 (mod m) (compatibility with subtraction)</li>
<li>a1 a2 ≡ b1 b2 (mod m) (compatibility with multiplication)</li>
<li>ak ≡ bk (mod m) for any non-negative integer k (compatibility with exponentiation)</li>
<li>p(a) ≡ p(b) (mod m), for any <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> p(x) with integer coefficients (compatibility with polynomial evaluation)</li></ul>
If a ≡ b (mod m), then it is generally false that ka ≡ kb (mod m). However, the following is true:

<ul><li>If c ≡ d (mod φ(m)), where φ is <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a>, then ac ≡ ad (mod m)—provided that a is <a href="/facts/Coprime/bnCxCXxs">coprime</a> with m.</li></ul>
For cancellation of common terms, we have the following rules:

<ul><li>If a + k ≡ b + k (mod m), where k is any integer, then a ≡ b (mod m).</li>
<li>If k a ≡ k b (mod m) and k is coprime with m, then a ≡ b (mod m).</li>
<li>If k a ≡ k b (mod k m) and k ≠ 0, then a ≡ b (mod m).</li></ul>
The last rule can be used to move modular arithmetic into division. If b divides a, then (a/b) mod m = (a mod b m) / b.
The <a href="/facts/Modular_multiplicative_inverse/xs8VgHPa">modular multiplicative inverse</a> is defined by the following rules:

<ul><li>Existence: There exists an integer denoted a−1 such that aa−1 ≡ 1 (mod m) if and only if a is coprime with m. This integer a−1 is called a modular multiplicative inverse of a modulo m.</li>
<li>If a ≡ b (mod m) and a−1 exists, then a−1 ≡ b−1 (mod m) (compatibility with multiplicative inverse, and, if a = b, uniqueness modulo m).</li>
<li>If ax ≡ b (mod m) and a is coprime to m, then the solution to this linear congruence is given by x ≡ a−1b (mod m).</li></ul>
The multiplicative inverse x ≡ a−1 (mod m) may be efficiently computed by solving <a href="/facts/B%25C3%25A9zout%2527s_identity/BKYSGV24">Bézout's equation</a> a x + m y = 1 for x, y, by using the <a href="/facts/Extended_Euclidean_algorithm/wmomforl">Extended Euclidean algorithm</a>.
In particular, if p is a prime number, then a is coprime with p for every a such that 0 < a < p; thus a multiplicative inverse exists for all a that is not congruent to zero modulo p.

<h2 id="advanced-properties">Advanced properties</h2>
Some of the more advanced properties of congruence relations are the following:

<ul><li><a href="/facts/Fermat%2527s_little_theorem/qIjSIm2s">Fermat's little theorem</a>: If p is prime and does not divide a, then ap−1 ≡ 1 (mod p).</li>
<li><a href="/facts/Euler%2527s_theorem/2q2DTwK3">Euler's theorem</a>: If a and m are coprime, then aφ(m) ≡ 1 (mod m), where φ is <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a>.</li>
<li>A simple consequence of Fermat's little theorem is that if p is prime, then a−1 ≡ ap−2 (mod p) is the multiplicative inverse of 0 < a < p. More generally, from Euler's theorem, if a and m are coprime, then a−1 ≡ aφ(m)−1 (mod m). Hence, if ax ≡ 1 (mod m), then x ≡ aφ(m)−1 (mod m).</li>
<li>Another simple consequence is that if a ≡ b (mod φ(m)), where φ is Euler's totient function, then ka ≡ kb (mod m) provided k is <a href="/facts/Coprime/bnCxCXxs">coprime</a> with m.</li>
<li><a href="/facts/Wilson%2527s_theorem/YzPaVmWb">Wilson's theorem</a>: p is prime if and only if (p − 1)! ≡ −1 (mod p).</li>
<li><a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a>: For any a, b and coprime m, n, there exists a unique x (mod mn) such that x ≡ a (mod m) and x ≡ b (mod n). In fact, x ≡ b mn−1 m + a nm−1 n (mod mn) where mn−1 is the inverse of m modulo n and nm−1 is the inverse of n modulo m.</li>
<li><a href="/facts/Lagrange%2527s_theorem_(number_theory)/kCXB0FJH">Lagrange's theorem</a>: If p is prime and f (x) = a0 xd + ... + ad is a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> with integer coefficients such that p is not a divisor of a0, then the congruence f (x) ≡ 0 (mod p) has at most d non-congruent solutions.</li>
<li><a href="/facts/Primitive_root_modulo_n/QS4DbIB0">Primitive root modulo m</a>: A number g is a primitive root modulo m if, for every integer a coprime to m, there is an integer k such that gk ≡ a (mod m). A primitive root modulo m exists if and only if m is equal to 2, 4, pk or 2pk, where p is an odd prime number and k is a positive integer. If a primitive root modulo m exists, then there are exactly φ(φ(m)) such primitive roots, where φ is the Euler's totient function.</li>
<li><a href="/facts/Quadratic_residue/rHD2uQdQ">Quadratic residue</a>: An integer a is a quadratic residue modulo m, if there exists an integer x such that x2 ≡ a (mod m). <a href="/facts/Euler%2527s_criterion/JkbpqqB1">Euler's criterion</a> asserts that, if p is an odd prime, and a is not a multiple of p, then a is a quadratic residue modulo p if and only if
a(p−1)/2 ≡ 1 (mod p).</li></ul>
<h2 id="congruence-classes">Congruence classes </h2>
The congruence relation is an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a>. The <a href="/facts/Equivalence_class/1d2sh0TB">equivalence class</a> modulo m of an integer a is the set of all integers of the form a + k m, where k is any integer. It is called the congruence class or residue class of a modulo m, and may be denoted (a mod m), or as a or [a] when the modulus m is known from the context.
Each residue class modulo m contains exactly one integer in the range 
 
 
 
 0
 ,
 .
 .
 .
 ,
 
 |
 
 m
 
 |
 
 −
 1
 
 
 {\displaystyle 0,...,|m|-1}
 
. Thus, these 
 
 
 
 
 |
 
 m
 
 |
 
 
 
 {\displaystyle |m|}
 
 integers are <a href="/facts/Representative_(mathematics)/1d2sh0TB">representatives</a> 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, (a mod m) denotes generally the unique integer r such that 0 ≤ r < m and r ≡ a (mod m); it is called the residue of a modulo m.
In particular, (a mod m) = (b mod m) is equivalent to a ≡ b (mod m), and this explains why "=" is often used instead of "≡" in this context.

<h2 id="residue-systems">Residue systems</h2>
Each residue class modulo 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<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> (since this is the proper remainder which results from division). Any two members of different residue classes modulo m are incongruent modulo m. Furthermore, every integer belongs to one and only one residue class modulo m.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
The set of integers {0, 1, 2, ..., m − 1} is called the least residue system modulo m. Any set of m integers, no two of which are congruent modulo m, is called a complete residue system modulo m.
The least residue system is a complete residue system, and a complete residue system is simply a set containing precisely one <a href="/facts/Representative_(mathematics)/1d2sh0TB">representative</a> of each residue class modulo m.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> For example, the least residue system modulo 4 is {0, 1, 2, 3}. Some other complete residue systems modulo 4 include:

<ul><li>{1, 2, 3, 4}</li>
<li>{13, 14, 15, 16}</li>
<li>{−2, −1, 0, 1}</li>
<li>{−13, 4, 17, 18}</li>
<li>{−5, 0, 6, 21}</li>
<li>{27, 32, 37, 42}</li></ul>
Some sets that are not complete residue systems modulo 4 are:

<ul><li>{−5, 0, 6, 22}, since 6 is congruent to 22 modulo 4.</li>
<li>{5, 15}, since a complete residue system modulo 4 must have exactly 4 incongruent residue classes.</li></ul>
<h3>Reduced residue systems</h3>
Main article: <a href="/facts/Reduced_residue_system/IfK9wRHX">Reduced residue system</a>
Given the <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a> φ(m), any set of φ(m) integers that are <a href="/facts/Coprime_integers/bnCxCXxs">relatively prime</a> to m and mutually incongruent under modulus m is called a reduced residue system modulo m.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> The set {5, 15} from above, for example, is an instance of a reduced residue system modulo 4.

<h3>Covering systems</h3>
Main article: <a href="/facts/Covering_system/sXppI4U9">Covering system</a>
Covering systems represent yet another type of residue system that may contain residues with varying moduli.

<h2 id="integers-modulo-m">Integers modulo m</h2>
In the context of this paragraph, the modulus m is almost always taken as positive.
The set of all congruence classes modulo m is a <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a> called the ring of integers modulo m, and is denoted 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\textstyle \mathbb {Z} /m\mathbb {Z} }
 
, 
 
 
 
 
 Z
 
 
 /
 
 m
 
 
 {\displaystyle \mathbb {Z} /m}
 
, or 
 
 
 
 
 
 Z
 
 
 m
 
 
 
 
 {\displaystyle \mathbb {Z} _{m}}
 
.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 
The ring 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 is fundamental to various branches of mathematics (see § Applications below).
(In some parts of <a href="/facts/Number_theory/zhoa7zrc">number theory</a> the notation 
 
 
 
 
 
 Z
 
 
 m
 
 
 
 
 {\displaystyle \mathbb {Z} _{m}}
 
 is avoided because it can be confused with the set of <a href="/facts/P-adic_integer/SDgDbkLF">m-adic integers</a>.) 
For m > 0 one has

Z
        
        
          /
        
        m
        
          Z
        
        =
        
          {
          
            
              
                
                  a
                  ¯
                
              
              
                m
              
            
            ∣
            a
            ∈
            
              Z
            
          
          }
        
        =
        
          {
          
            
              
                
                  0
                  ¯
                
              
              
                m
              
            
            ,
            
              
                
                  1
                  ¯
                
              
              
                m
              
            
            ,
            
              
                
                  2
                  ¯
                
              
              
                m
              
            
            ,
            …
            ,
            
              
                
                  
                    m
                    
                      −
                    
                    1
                  
                  ¯
                
              
              
                m
              
            
          
          }
        
        .
      
    
    {\displaystyle \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\}.}

When m = 1, 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 is the <a href="/facts/Zero_ring/trFjtDJ1">zero ring</a>; when m = 0, 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 is not an <a href="/facts/Empty_set/ffEk3eA6">empty set</a>; rather, it is <a href="/facts/Isomorphism/pj8KgkxU">isomorphic</a> to 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
, since a0 = {a}.
Addition, subtraction, and multiplication are defined on 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 by the following rules:

<ul><li>
 
 
 
 
 
 
 a
 ¯
 
 
 
 m
 
 
 +
 
 
 
 b
 ¯
 
 
 
 m
 
 
 =
 
 
 
 
 (
 a
 +
 b
 )
 
 ¯
 
 
 
 m
 
 
 
 
 {\displaystyle {\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}}
 
</li>
<li>
 
 
 
 
 
 
 a
 ¯
 
 
 
 m
 
 
 −
 
 
 
 b
 ¯
 
 
 
 m
 
 
 =
 
 
 
 
 (
 a
 −
 b
 )
 
 ¯
 
 
 
 m
 
 
 
 
 {\displaystyle {\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}}
 
</li>
<li>
 
 
 
 
 
 
 a
 ¯
 
 
 
 m
 
 
 
 
 
 b
 ¯
 
 
 
 m
 
 
 =
 
 
 
 
 (
 a
 b
 )
 
 ¯
 
 
 
 m
 
 
 .
 
 
 {\displaystyle {\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.}
 
</li></ul>
The properties given before imply that, with these operations, 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 is a <a href="/facts/Commutative_ring/QS1r2ovR">commutative ring</a>. For example, in the ring 
 
 
 
 
 Z
 
 
 /
 
 24
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /24\mathbb {Z} }
 
, one has

12
              ¯
            
          
          
            24
          
        
        +
        
          
            
              21
              ¯
            
          
          
            24
          
        
        =
        
          
            
              33
              ¯
            
          
          
            24
          
        
        =
        
          
            
              9
              ¯
            
          
          
            24
          
        
      
    
    {\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}}

as in the arithmetic for the 24-hour clock.
The notation 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 is used because this ring is the <a href="/facts/Quotient_ring/X2WkXyEw">quotient ring</a> of 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
 by the <a href="/facts/Ideal_(ring_theory)/vCvytduX">ideal</a> 
 
 
 
 m
 
 Z
 
 
 
 {\displaystyle m\mathbb {Z} }
 
, the set formed by all multiples of m, i.e., all numbers k m with 
 
 
 
 k
 ∈
 
 Z
 
 .
 
 
 {\displaystyle k\in \mathbb {Z} .}

Under addition, 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 is a <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a>. All finite cyclic groups are isomorphic with 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
 for some m.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
The ring of integers modulo m is a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a>, i.e., every nonzero element has a <a href="/facts/Modular_multiplicative_inverse/xs8VgHPa">multiplicative inverse</a>, if and only if m is <a href="/facts/Prime_number/L20FLkgn">prime</a>. If m = pk is a <a href="/facts/Prime_power/R0vo3uYp">prime power</a> with k > 1, there exists a unique (up to isomorphism) finite field 
 
 
 
 
 G
 F
 
 (
 m
 )
 =
 
 
 F
 
 
 m
 
 
 
 
 {\displaystyle \mathrm {GF} (m)=\mathbb {F} _{m}}
 
 with m elements, which is not isomorphic to 
 
 
 
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /m\mathbb {Z} }
 
, which fails to be a field because it has <a href="/facts/Zero-divisor/5GraAU8o">zero-divisors</a>.
If m > 1, 
 
 
 
 (
 
 Z
 
 
 /
 
 m
 
 Z
 
 
 )
 
 ×
 
 
 
 
 {\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}
 
 denotes the <a href="/facts/Multiplicative_group_of_integers_modulo_n/IACS6cgH">multiplicative group of the integers modulo m</a> that are invertible. It consists of the congruence classes am, where a <a href="/facts/Coprime_integers/bnCxCXxs">is coprime</a> to m; these are precisely the classes possessing a multiplicative inverse. They form an <a href="/facts/Abelian_group/FfWwmx4R">abelian group</a> under multiplication; its order is φ(m), where φ is <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a>.

<h2 id="applications">Applications</h2>
In pure mathematics, modular arithmetic is one of the foundations of <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, touching on almost every aspect of its study, and it is also used extensively in <a href="/facts/Group_theory/NfowcI5H">group theory</a>, <a href="/facts/Ring_theory/VW6svEFe">ring theory</a>, <a href="/facts/Knot_theory/mb7rtqVP">knot theory</a>, and <a href="/facts/Abstract_algebra/YNNE1CNz">abstract algebra</a>. In applied mathematics, it is used in <a href="/facts/Computer_algebra/hjun1KAX">computer algebra</a>, <a href="/facts/Cryptography/e94PEVau">cryptography</a>, <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, <a href="/facts/Chemistry/SrNqkGVm">chemistry</a> and the <a href="/facts/Visual_arts/95RgxP8e">visual</a> and <a href="/facts/Music/hDVP0xsQ">musical</a> arts.
A very practical application is to calculate checksums within serial number identifiers. For example, <a href="/facts/International_Standard_Book_Number/15AdSPa9">International Standard Book Number</a> (ISBN) uses modulo 11 (for 10-digit ISBN) or modulo 10 (for 13-digit ISBN) arithmetic for error detection. Likewise, <a href="/facts/International_Bank_Account_Number/q22HuznY">International Bank Account Numbers</a> (IBANs) use modulo 97 arithmetic to spot user input errors in bank account numbers. In chemistry, the last digit of the <a href="/facts/CAS_registry_number/zjXjCGPx">CAS registry number</a> (a unique identifying number for each chemical compound) is a <a href="/facts/Check_digit/qMlumJpU">check digit</a>, 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 <a href="/facts/Public-key_cryptography/gowoFTxS">public key</a> systems such as <a href="/facts/RSA_(algorithm)/XTzyfHuq">RSA</a> and <a href="/facts/Diffie%25E2%2580%2593Hellman_key_exchange/xR4YQcaD">Diffie–Hellman</a>, and provides <a href="/facts/Finite_field/UkMGJo3m">finite fields</a> which underlie <a href="/facts/Elliptic_curve/60jvaHSA">elliptic curves</a>, and is used in a variety of <a href="/facts/Symmetric_key_algorithm/5zfe0b76">symmetric key algorithms</a> including <a href="/facts/Advanced_Encryption_Standard/HdXGBY2Q">Advanced Encryption Standard</a> (AES), <a href="/facts/International_Data_Encryption_Algorithm/HuRBKLQY">International Data Encryption Algorithm</a> (IDEA), and <a href="/facts/RC4/HAR5kL0T">RC4</a>. RSA and Diffie–Hellman use <a href="/facts/Modular_exponentiation/0STECS3P">modular exponentiation</a>.
In computer algebra, modular arithmetic is commonly used to limit the size of integer coefficients in intermediate calculations and data. It is used in <a href="/facts/Polynomial_factorization/1S9HRKcI">polynomial factorization</a>, a problem for which all known efficient algorithms use modular arithmetic. It is used by the most efficient implementations of <a href="/facts/Polynomial_greatest_common_divisor/4c3dUbJr">polynomial greatest common divisor</a>, exact <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a> and <a href="/facts/Gr%25C3%25B6bner_basis/efMrjM7w">Gröbner basis</a> algorithms over the integers and the rational numbers. As posted on <a href="/facts/Fidonet/dM4jyojM">Fidonet</a> in the 1980s and archived at <a href="/facts/Rosetta_Code/HAN5rwmX">Rosetta Code</a>, modular arithmetic was used to disprove <a href="/facts/Euler%2527s_sum_of_powers_conjecture/EvxpmgB1">Euler's sum of powers conjecture</a> on a <a href="/facts/Sinclair_QL/Dn5dIVkR">Sinclair QL</a> <a href="/facts/Microcomputer/ETW22UTv">microcomputer</a> using just one-fourth of the integer precision used by a <a href="/facts/CDC_6600/QpnT1Ltl">CDC 6600</a> <a href="/facts/Supercomputer/HT9NwGAN">supercomputer</a> to disprove it two decades earlier via a <a href="/facts/Brute_force_search/YU2fzBIt">brute force search</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
In computer science, modular arithmetic is often applied in <a href="/facts/Bitwise_operation/0gkqnUda">bitwise operations</a> and other operations involving fixed-width, cyclic <a href="/facts/Data_structure/yNsNvL1I">data structures</a>. The modulo operation, as implemented in many <a href="/facts/Programming_language/cWTYbgWa">programming languages</a> and <a href="/facts/Calculator/eeLfRS8L">calculators</a>, is an application of modular arithmetic that is often used in this context. The logical operator <a href="/facts/XOR/FHyr7hGQ">XOR</a> sums 2 bits, modulo 2.
The use of <a href="/facts/Long_division/W8Vd90Kw">long division</a> to turn a fraction into a <a href="/facts/Repeating_decimal/yo5T4m2M">repeating decimal</a> 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 <a href="/facts/Twelve-tone_equal_temperament/89BK2lpj">twelve-tone equal temperament</a>, where <a href="/facts/Octave/RA4gWvkV">octave</a> and <a href="/facts/Enharmonic/lSwDb7JN">enharmonic</a> equivalency occurs (that is, pitches in a 1:2 or 2:1 ratio are equivalent, and C-<a href="/facts/Sharp_(music)/dUgIJtHX">sharp</a> is considered the same as D-<a href="/facts/Flat_(music)/gS2acguR">flat</a>).
The method of <a href="/facts/Casting_out_nines/c2Eo0pP4">casting out nines</a> 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, <a href="/facts/Zeller%2527s_congruence/qgktaxfI">Zeller's congruence</a> and the <a href="/facts/Doomsday_algorithm/5TXr6fsc">Doomsday algorithm</a> make heavy use of modulo-7 arithmetic.
More generally, modular arithmetic also has application in disciplines such as <a href="/facts/Law/luzxWkg0">law</a> (e.g., <a href="/facts/Apportionment_(politics)/5dfqPcV0">apportionment</a>), <a href="/facts/Economics/HYctA2Dn">economics</a> (e.g., <a href="/facts/Game_theory/zkEIj1ya">game theory</a>) and other areas of the <a href="/facts/Social_science/hAbm1xtD">social sciences</a>, where <a href="/facts/Proportional_(fair_division)/nScaIg1F">proportional</a> division and allocation of resources plays a central part of the analysis.

<h2 id="computational-complexity">Computational complexity</h2>
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 <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> with a form of <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a>, for details see <a href="/facts/Linear_congruence_theorem/7wwFIkuV">linear congruence theorem</a>. Algorithms, such as <a href="/facts/Montgomery_reduction/C1UyVrKJ">Montgomery reduction</a>, also exist to allow simple arithmetic operations, such as multiplication and <a href="/facts/Modular_exponentiation/0STECS3P">exponentiation modulo m</a>, to be performed efficiently on large numbers.
Some operations, like finding a <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithm</a> or a <a href="/facts/Quadratic_congruences/rHD2uQdQ">quadratic congruence</a> appear to be as hard as <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> and thus are a starting point for <a href="/facts/Cryptography/e94PEVau">cryptographic algorithms</a> and <a href="/facts/Encryption/16q29Fdv">encryption</a>. These problems might be <a href="/facts/NP-intermediate/cCg3QdjF">NP-intermediate</a>.
Solving a system of non-linear modular arithmetic equations is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h2 id="see-also">See also</h2>

<ul><li><a href="/facts/Boolean_ring/lgko4uqq">Boolean ring</a></li>
<li><a href="/facts/Circular_buffer/Xu7vpzmP">Circular buffer</a></li>
<li><a href="/facts/Division_(mathematics)/FqLKNkmq">Division (mathematics)</a></li>
<li><a href="/facts/Finite_field/UkMGJo3m">Finite field</a></li>
<li><a href="/facts/Legendre_symbol/MwHrJ7as">Legendre symbol</a></li>
<li><a href="/facts/Modular_exponentiation/0STECS3P">Modular exponentiation</a></li>
<li><a href="/facts/Modulo_(mathematics)/lg6V4FF9">Modulo (mathematics)</a></li>
<li><a href="/facts/Multiplicative_group_of_integers_modulo_n/IACS6cgH">Multiplicative group of integers modulo n</a></li>
<li><a href="/facts/Pisano_period/omyF34hb">Pisano period</a> (Fibonacci sequences modulo n)</li>
<li><a href="/facts/Primitive_root_modulo_n/QS4DbIB0">Primitive root modulo n</a></li>
<li><a href="/facts/Quadratic_reciprocity/leCHbu5B">Quadratic reciprocity</a></li>
<li><a href="/facts/Quadratic_residue/rHD2uQdQ">Quadratic residue</a></li>
<li><a href="/facts/Rational_reconstruction_(mathematics)/qKjE6mtF">Rational reconstruction (mathematics)</a></li>
<li><a href="/facts/Reduced_residue_system/IfK9wRHX">Reduced residue system</a></li>
<li><a href="/facts/Serial_number_arithmetic/FgTE1YTJ">Serial number arithmetic</a> (a special case of modular arithmetic)</li>
<li><a href="/facts/Two-element_Boolean_algebra/8nIWUpwd">Two-element Boolean algebra</a></li>
<li>Topics relating to the group theory behind modular arithmetic:
<ul><li><a href="/facts/Cyclic_group/JL5zfFuL">Cyclic group</a></li>
<li><a href="/facts/Multiplicative_group_of_integers_modulo_n/IACS6cgH">Multiplicative group of integers modulo n</a></li></ul></li>
<li>Other important theorems relating to modular arithmetic:
<ul><li><a href="/facts/Carmichael_function/D0l0I6od">Carmichael's theorem</a></li>
<li><a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a></li>
<li><a href="/facts/Euler%2527s_theorem/2q2DTwK3">Euler's theorem</a></li>
<li><a href="/facts/Fermat%2527s_little_theorem/qIjSIm2s">Fermat's little theorem</a> (a special case of Euler's theorem)</li>
<li><a href="/facts/Lagrange%2527s_theorem_(group_theory)/VgyNjGlz">Lagrange's theorem</a></li>
<li><a href="/facts/Thue%2527s_lemma/c8fjyxNB">Thue's lemma</a></li></ul></li></ul>

<h2 id="notes">Notes</h2>

<ul><li>John L. Berggren. <a href="https://www.britannica.com/EBchecked/topic/920687/modular-arithmetic">"modular arithmetic"</a>. <a href="/facts/Encyclop%25C3%25A6dia_Britannica/CEyVsjlN">Encyclopædia Britannica</a>.</li>
<li><a href="/facts/Tom_M._Apostol/S6vGtJWN">Apostol, Tom M.</a> (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-90163-3, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0434929">0434929</a>, <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0335.10001">0335.10001</a>. See in particular chapters 5 and 6 for a review of basic modular arithmetic.</li>
<li>Maarten Bullynck "<a href="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</a>"</li>
<li><a href="/facts/Thomas_H._Cormen/qJ2Ys15T">Thomas H. Cormen</a>, <a href="/facts/Charles_E._Leiserson/6Uf19apB">Charles E. Leiserson</a>, <a href="/facts/Ronald_L._Rivest/nQsIcAKa">Ronald L. Rivest</a>, and <a href="/facts/Clifford_Stein/5ajkVbCm">Clifford Stein</a>. <a href="/facts/Introduction_to_Algorithms/o9n7KDsg">Introduction to Algorithms</a>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.</li>
<li><a href="http://genealogy.math.ndsu.nodak.edu/id.php?id=3545">Anthony Gioia</a>, Number Theory, an Introduction Reprint (2001) Dover. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-41449-3.</li>
<li>Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: <a href="/facts/D._C._Heath_and_Company/qRMDoWMz">D. C. Heath and Company</a>. <a href="/facts/LCCN_(identifier)/5hb5Cw2V">LCCN</a> <a href="https://lccn.loc.gov/77171950">77171950</a>.</li>
<li>Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). <a href="https://archive.org/details/elementsofnumber0000pett">Elements of Number Theory</a>. Englewood Cliffs: <a href="/facts/Prentice_Hall/bynWAuat">Prentice Hall</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780132683005. <a href="/facts/LCCN_(identifier)/5hb5Cw2V">LCCN</a> <a href="https://lccn.loc.gov/71081766">71081766</a>.</li>
<li>Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-81-317-1405-8. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/778356123">778356123</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.encyclopediaofmath.org/index.php?title=Congruence">"Congruence"</a>, <a href="/facts/Encyclopedia_of_Mathematics/WC6mGtPm">Encyclopedia of Mathematics</a>, <a href="/facts/European_Mathematical_Society/B3h7b672">EMS Press</a>, 2001 [1994]</li>
<li>In this <a href="https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm">modular art</a> article, one can learn more about applications of modular arithmetic in art.</li>
<li>An <a href="https://web.archive.org/web/20160220061222/http://mersennewiki.org/index.php/Modular_arithmetic">article</a> on modular arithmetic on the GIMPS wiki</li>
<li><a href="http://www.cut-the-knot.org/blue/Modulo.shtml">Modular Arithmetic and patterns in addition and multiplication tables</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Sandor Lehoczky; Richard Rusczky (2006). David Patrick (ed.). the Art of Problem Solving. Vol. 1 (7 ed.). AoPS Incorporated. p. 44. ISBN 0977304566. <a href="0977304566" target="_blank">0977304566</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Weisstein, Eric W. "Modular Arithmetic". Wolfram MathWorld. Archived from the original on 2023-07-14. Retrieved 2020-08-12. <a href="https://mathworld.wolfram.com/ModularArithmetic.html" target="_blank">https://mathworld.wolfram.com/ModularArithmetic.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Pettofrezzo & Byrkit (1970, p. 90) - Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. ISBN 9780132683005. LCCN 71081766. <a href="https://archive.org/details/elementsofnumber0000pett" target="_blank">https://archive.org/details/elementsofnumber0000pett</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Long (1972, p. 78) - Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950. <a href="https://lccn.loc.gov/77171950" target="_blank">https://lccn.loc.gov/77171950</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Long (1972, p. 85) - Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950. <a href="https://lccn.loc.gov/77171950" target="_blank">https://lccn.loc.gov/77171950</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"2.3: Integers Modulo n". Mathematics LibreTexts. 2013-11-16. Archived from the original on 2021-04-19. Retrieved 2020-08-12. <a href="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" target="_blank">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</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Sengadir T., Discrete Mathematics and Combinatorics, p. 293, at Google Books <a href="https://books.google.com/books?id=nglisrt9IewC&pg=PA293&dq=%22Zn+is+generated+by+1%22" target="_blank">https://books.google.com/books?id=nglisrt9IewC&pg=PA293&dq=%22Zn+is+generated+by+1%22</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">"Euler's sum of powers conjecture". rosettacode.org. Archived from the original on 2023-03-26. Retrieved 2020-11-11. <a href="https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#QL_SuperBASIC" target="_blank">https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#QL_SuperBASIC</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Garey, M. R.; Johnson, D. S. (1979). Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0716710447. <a href="0716710447" target="_blank">0716710447</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Modular arithmetic open-in-new

Modular arithmetic