Movatterモバイル変換

[0]ホーム

Jump to content

Modular arithmetic

Edit links

From Wikipedia, the free encyclopedia

Computation modulo a fixed integer

This article is about the concept that uses the "a (modm)" notation. For the binary operationmod(a,m), seeModulo.

This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Modular arithmetic" – news ·newspapers ·books ·scholar ·JSTOR(June 2025) (Learn how and when to remove this message)

Left: Analog clock reading 9 o'clock. Right: After four hours have passed, the clock now reads 1 o'clock. — 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.

Inmathematics,modular arithmetic is a system ofarithmetic operations forintegers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called themodulus. The modern approach tonumber theory using modular arithmetic was developed byCarl Friedrich Gauss in his bookDisquisitiones Arithmeticae, published in 1801.^[1]

A familiar example of modular arithmetic is the hour hand on a12-hour clock. If the hour hand points to 7 now, then 8 hours later it will point to 3. Ordinary addition would result in7 + 8 = 15, but 15 reads as 3 on the clock face. This is because the hour hand makes one rotation every 12 hours and the hour number starts over when the hour hand passes 12. We say that 15 iscongruent to 3 modulo 12, written 15 ≡ 3 (mod 12), so that 7 + 8 ≡ 3 (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

[edit]

Given anintegerm ≥ 1, called amodulus, two integersa andb are said to becongruent modulom, ifm is adivisor of their difference; that is, if there is an integerk such that

a −b =k m.

Congruence modulom is acongruence relation, meaning that it is anequivalence relation that is compatible withaddition,subtraction, andmultiplication. Congruence modulom is denoted by

a\equiv b~({\text{mod }}m).

The parentheses mean that(modm) applies to the entire equation, not just to the right-hand side (here,b).

This notation is not to be confused with the notationb modm (without parentheses), which refers to the remainder ofb when divided bym, known as themodulo operation: that is,b modm denotes the unique integerr such that0 ≤r <m andr ≡b (modm). Indeed, the expressionb modm does not appear in the statementa ≡b (modm), since it is parsed as

(a\equiv b){\bmod {m}}.

The congruence relation may be rewritten as

a =k m +b,

explicitly showing its relationship withEuclidean division. However, theb here need not be the remainder in the division ofa bym. Rather,a ≡b (modm) asserts thata andb have the sameremainder when divided bym. That is,

a =p m +r,

b =q m +r,

where0 ≤r <m is the common remainder. We recover the previous relation (a −b =k m) by subtracting these two expressions and settingk =p −q.

Because the congruence modulom is defined by thedivisibility bym and because−1 is aunit in the ring of integers, a number is divisible by−m exactly if it is divisible bym.This means that every non-zero integerm may be taken as a modulus.

Examples

[edit]

In modulus 12, one can assert that:

38 ≡ 14 (mod 12)

because the difference is38 − 14 = 24 = 2 × 12, a multiple of12. Equivalently,38 and14 have the same remainder2 when divided by12.

The definition of congruence also applies to negative values. For example:

{\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv {\phantom {+}}7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}

Basic properties

[edit]

The congruence relation satisfies all the conditions of anequivalence relation:

Reflexivity:a ≡a (modm)
Symmetry:a ≡b (modm) if and only ifb ≡a (modm).
Transitivity: Ifa ≡b (modm) andb ≡c (modm), thena ≡c (modm)

Ifa₁ ≡b₁ (modm) anda₂ ≡b₂ (modm), or ifa ≡b (modm), then:^[2]

a +k ≡b +k (modm) for any integerk (compatibility with translation)
k a ≡k b (modm) for any integerk (compatibility with scaling)
k a ≡k b (modk m) for any integerk
a₁ +a₂ ≡b₁ +b₂ (modm) (compatibility with addition)
a₁ −a₂ ≡b₁ −b₂ (modm) (compatibility with subtraction)
a₁a₂ ≡b₁b₂ (modm) (compatibility with multiplication)
a^k ≡b^k (modm) for any non-negative integerk (compatibility with exponentiation)
p(a) ≡p(b) (modm), for anypolynomialp(x) with integer coefficients (compatibility with polynomial evaluation)

Ifa ≡b (modm), then it is generally false thatk^a ≡k^b (modm). However, the following is true:

Ifc ≡d (modφ(m)), whereφ isEuler's totient function, thena^c ≡a^d (modm)—provided thata iscoprime withm.

Ifa ≡b (modmn), thena ≡b (modm) anda ≡b (modn).

For cancellation of common terms, we have the following rules:

Ifa +k ≡b +k (modm), wherek is any integer, thena ≡b (modm).
Ifk a ≡k b (modm) andk is coprime withm, thena ≡b (modm).
Ifk a ≡k b (modk m) andk ≠ 0, thena ≡b (modm).

The last rule can be used to move modular arithmetic into division. Ifb dividesa, then(a/b) modm = (a modb m) /b.

Themodular multiplicative inverse is defined by the following rules:

Existence: There exists an integer denoteda⁻¹ such thataa⁻¹ ≡ 1 (modm) if and only ifa is coprime withm. This integera⁻¹ is called amodular multiplicative inverse ofa modulom.
Ifa ≡b (modm) anda⁻¹ exists, thena⁻¹ ≡b⁻¹ (modm) (compatibility with multiplicative inverse, and, ifa =b, uniqueness modulom).
Ifax ≡b (modm) anda is coprime tom, then the solution to this linear congruence is given byx ≡a⁻¹b (modm).

The multiplicative inversex ≡a⁻¹ (modm) may be efficiently computed by solvingBézout's equationa x +m y = 1 forx,y, by using theExtended Euclidean algorithm.

In particular, ifp is a prime number, thena is coprime withp for everya such that0 <a <p; thus a multiplicative inverse exists for alla that is not congruent to zero modulop.

Advanced properties

[edit]

Some of the more advanced properties of congruence relations are the following:

Fermat's little theorem: Ifp is prime and does not dividea, thena^p−1 ≡ 1 (modp).
Euler's theorem: Ifa andm are coprime, thena^φ(m) ≡ 1 (modm), whereφ isEuler's totient function.
A simple consequence of Fermat's little theorem is that ifp is prime, thena⁻¹ ≡a^p−2 (modp) is the multiplicative inverse of0 <a <p. More generally, from Euler's theorem, ifa andm are coprime, thena⁻¹ ≡a^φ(m)−1 (modm). Hence, ifax ≡1 (modm), thenx ≡a^φ(m)−1 (modm).
Another simple consequence is that ifa ≡b (modφ(m)), whereφ is Euler's totient function, thenk^a ≡k^b (modm) providedk iscoprime withm.
Wilson's theorem:p is prime if and only if(p − 1)! ≡ −1 (modp).
Chinese remainder theorem: For anya,b and coprimem,n, there exists a uniquex (modmn) such thatx ≡a (modm) andx ≡b (modn). In fact,x ≡b m_n⁻¹m +a n_m⁻¹n (modmn) wherem_n⁻¹ is the inverse ofm modulon andn_m⁻¹ is the inverse ofn modulom.
Lagrange's theorem: Ifp is prime andf (x) =a₀x^d + ... +a_d is apolynomial with integer coefficients such thatp is not a divisor ofa₀, then the congruencef (x) ≡ 0 (modp) has at mostd non-congruent solutions.
Primitive root modulom: A numberg is a primitive root modulom if, for every integera coprime tom, there is an integerk such thatg^k ≡a (modm). A primitive root modulom exists if and only ifm is equal to2, 4,p^k or 2p^k, wherep is an odd prime number andk is a positive integer. If a primitive root modulom exists, then there are exactlyφ(φ(m)) such primitive roots, whereφ is the Euler's totient function.
Quadratic residue: An integera is a quadratic residue modulom, if there exists an integerx such thatx² ≡a (modm).Euler's criterion asserts that, ifp is an odd prime, anda is not a multiple ofp, thena is a quadratic residue modulop if and only if
a^(p−1)/2 ≡ 1 (modp).

Congruence classes

[edit]

The congruence relation is anequivalence relation. Theequivalence class modulom of an integera is the set of all integers of the forma +k m, wherek is any integer. It is called thecongruence class orresidue class ofa modulo m, and may be denoted(a modm), or asa or[a] when the modulusm is known from the context.

Each residue class modulo m contains exactly one integer in the range $0,...,|m|-1$ . Thus, these $|m|$ integers arerepresentatives 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 modm) denotes generally the unique integerr such that0 ≤r <m andr ≡a (modm); it is called theresidue ofa modulo m.

In particular,(a modm) = (b modm) is equivalent toa ≡b (modm), and this explains why "=" is often used instead of "≡" in this context.

Residue systems

[edit]

Each residue class modulom 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^[3] (since this is the proper remainder which results from division). Any two members of different residue classes modulom are incongruent modulom. Furthermore, every integer belongs to one and only one residue class modulom.^[4]

The set of integers{0, 1, 2, ...,m − 1} is called theleast residue system modulom. Any set ofm integers, no two of which are congruent modulom, is called acomplete residue system modulom.

The least residue system is a complete residue system, and a complete residue system is simply a set containing precisely onerepresentative of each residue class modulom.^[5] For example, the least residue system modulo4 is{0, 1, 2, 3}. Some other complete residue systems modulo4 include:

{1, 2, 3, 4}
{13, 14, 15, 16}
{−2, −1, 0, 1}
{−13, 4, 17, 18}
{−5, 0, 6, 21}
{27, 32, 37, 42}

Some sets that arenot complete residue systems modulo 4 are:

{−5, 0, 6, 22}, since6 is congruent to22 modulo4.
{5, 15}, since a complete residue system modulo4 must have exactly4 incongruent residue classes.

Reduced residue systems

[edit]

Main article:Reduced residue system

Given theEuler's totient functionφ(m), any set ofφ(m) integers that arerelatively prime tom and mutually incongruent under modulusm is called areduced residue system modulom.^[6] The set{5, 15} from above, for example, is an instance of a reduced residue system modulo 4.

Covering systems

[edit]

Main article:Covering system

Covering systems represent yet another type of residue system that may contain residues with varying moduli.

Integers modulom

[edit]

In the context of this paragraph, the modulusm is almost always taken as positive.

The set of allcongruence classes modulom is aring called thering of integers modulom, and is denoted ${\textstyle \mathbb {Z} /m\mathbb {Z} }$ , $\mathbb {Z} /m$ , or $\mathbb {Z} _{m}$ .^[7] The ring $\mathbb {Z} /m\mathbb {Z}$ is fundamental to various branches of mathematics (see§ Applications below).(In some parts ofnumber theory the notation $\mathbb {Z} _{m}$ is avoided because it can be confused with the set ofm-adic integers.)

Form > 0 one has

\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\}.

Whenm = 1, $\mathbb {Z} /m\mathbb {Z}$ is thezero ring; whenm = 0, $\mathbb {Z} /m\mathbb {Z}$ is not anempty set; rather, it isisomorphic to $\mathbb {Z}$ , sincea₀ = {a}.

Addition, subtraction, and multiplication are defined on $\mathbb {Z} /m\mathbb {Z}$ by the following rules:

${\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}$
${\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}$
${\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.$

The properties given before imply that, with these operations, $\mathbb {Z} /m\mathbb {Z}$ is acommutative ring. For example, in the ring $\mathbb {Z} /24\mathbb {Z}$ , one has

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

as in the arithmetic for the 24-hour clock.

The notation $\mathbb {Z} /m\mathbb {Z}$ is used because this ring is thequotient ring of $\mathbb {Z}$ by theideal $m\mathbb {Z}$ , the set formed by all multiples ofm, that is, all numbersk m with $k\in \mathbb {Z} .$

Under addition, $\mathbb {Z} /m\mathbb {Z}$ is acyclic group. All finite cyclic groups are isomorphic with $\mathbb {Z} /m\mathbb {Z}$ for somem.^[8]

The ring of integers modulom is afield; that is, every nonzero element has amultiplicative inverse, if and only ifm isprime. Ifm =p^k is aprime power withk > 1, there exists a unique (up to isomorphism) finite field $\mathrm {GF} (m)=\mathbb {F} _{m}$ withm elements, which isnot isomorphic to $\mathbb {Z} /m\mathbb {Z}$ , which fails to be a field because it haszero-divisors.

Ifm > 1, $(\mathbb {Z} /m\mathbb {Z} )^{\times }$ denotes themultiplicative group of the integers modulom that are invertible. It consists of the congruence classesa_m, whereais coprime tom; these are precisely the classes possessing a multiplicative inverse. They form anabelian group under multiplication; its order isφ(m), whereφ isEuler's totient function.

Applications

[edit]

In pure mathematics, modular arithmetic is one of the foundations ofnumber theory, touching on almost every aspect of its study, and it is also used extensively ingroup theory,ring theory,knot theory, andabstract algebra. In applied mathematics, it is used incomputer algebra,cryptography,computer science,chemistry and thevisual andmusical 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 Numbers (IBANs) use modulo 97 arithmetic to spot user input errors in bank account numbers. In chemistry, the last digit of theCAS registry number (a unique identifying number for each chemical compound) is acheck 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 underpinspublic key systems such asRSA andDiffie–Hellman, and providesfinite fields which underlieelliptic curves, and is used in a variety ofsymmetric key algorithms includingAdvanced Encryption Standard (AES),International Data Encryption Algorithm (IDEA), andRC4. RSA and Diffie–Hellman usemodular exponentiation.

In computer algebra, modular arithmetic is commonly used to limit the size of integer coefficients in intermediate calculations and data. It is used inpolynomial factorization, a problem for which all known efficient algorithms use modular arithmetic. It is used by the most efficient implementations ofpolynomial greatest common divisor, exactlinear algebra andGröbner basis algorithms over the integers and the rational numbers. As posted onFidonet in the 1980s and archived atRosetta Code, modular arithmetic was used to disproveEuler's sum of powers conjecture on aSinclair QL microcomputer using just one-fourth of the integer precision used by aCDC 6600 supercomputer to disprove it two decades earlier via abrute force search.^[9]

In computer science, modular arithmetic is often applied inbitwise operations and other operations involving fixed-width, cyclicdata structures. The modulo operation, as implemented in manyprogramming languages andcalculators, is an application of modular arithmetic that is often used in this context. The logical operatorXOR sums 2 bits, modulo 2.

The use oflong division to turn a fraction into arepeating decimal in any baseb is equivalent to modular multiplication ofb modulo the denominator. For example, for decimal,b = 10.

In music, arithmetic modulo 12 is used in the consideration of the system oftwelve-tone equal temperament, whereoctave andenharmonic equivalency occurs (that is, pitches in a 1:2 or 2:1 ratio are equivalent, and C-sharp is considered the same as D-flat).

The method ofcasting 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 theDoomsday algorithm make heavy use of modulo-7 arithmetic.

More generally, modular arithmetic also has application in disciplines such aspolitics (for example,apportionment),economics (for example,game theory) and other areas of thesocial sciences, whereproportional division and allocation of resources plays a central part of the analysis.

Computational complexity

[edit]

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 inpolynomial time with a form ofGaussian elimination, for details seelinear congruence theorem. Algorithms, such asMontgomery reduction, also exist to allow simple arithmetic operations, such as multiplication andexponentiation modulo m, to be performed efficiently on large numbers.

Some operations, like finding adiscrete logarithm or aquadratic congruence appear to be as hard asinteger factorization and thus are a starting point forcryptographic algorithms andencryption. These problems might beNP-intermediate.

Solving a system of non-linear modular arithmetic equations isNP-complete.^[10]

Notes

[edit]

^Gray, Jeremy. A History of Abstract Algebra: From Algebraic Equations to Modern Algebra. Germany, Springer International Publishing, 2018. 143.
^Lehoczky & Rusczky 2006.
^Weisstein.
^Pettofrezzo & Byrkit 1970, p. 90.
^Long 1972, p. 78.
^Long 1972, p. 85.
^Denton 2013.
^Sengadir T.,Discrete Mathematics and Combinatorics, p. 293, atGoogle Books
^"Euler's sum of powers conjecture".rosettacode.org.Archived from the original on 26 March 2023. Retrieved11 November 2020.
^Garey & Johnson 1979.

References

[edit]

Apostol, Tom M. (1976),Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag,ISBN 978-0-387-90163-3,MR 0434929,Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic.

Berggren, John L."Modular arithmetic".Encyclopædia Britannica.

Bullynck, Maarten."Modular Arithmetic before C. F. Gauss: Systematisations and discussions on remainder problems in 18th-century Germany"(PDF). Archived fromthe original(PDF) on 2 November 2013. Retrieved3 February 2018.

Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford (2001). "31.3: Modular arithmetic".Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 862–868.ISBN 0-262-03293-7.

Denton, Tom (16 November 2013)."2.3: Integers Modulo n".Mathematics LibreTexts.Archived from the original on 19 April 2021. Retrieved12 August 2020.

Garey, M. R.; Johnson, D. S. (1979).Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman.ISBN 0716710447.

Gioia, Anthony (2001).Number Theory: An Introduction (Reprint ed.). Dover.ISBN 0-486-41449-3.

Lehoczky, Sandor;Rusczky, Richard (2006). Patrick, David (ed.).The Art of Problem Solving. Vol. 1 (7 ed.). AoPS Incorporated. p. 44.ISBN 0977304566.

Long, Calvin T. (1972).Elementary Introduction to Number Theory (2nd ed.). Lexington:D. C. Heath and Company.LCCN 77171950.

Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970).Elements of Number Theory. Englewood Cliffs:Prentice Hall.ISBN 9780132683005.LCCN 71081766.

Sengadir, T. (2009).Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India.ISBN 978-81-317-1405-8.OCLC 778356123.

Weisstein, Eric W."Modular Arithmetic".Wolfram MathWorld.Archived from the original on 14 July 2023. Retrieved12 August 2020.

External links

[edit]

"Congruence",Encyclopedia of Mathematics,EMS Press, 2001 [1994]
In thismodular art article, one can learn more about applications of modular arithmetic in art.
Anarticle on modular arithmetic on the GIMPS wiki
Modular Arithmetic and patterns in addition and multiplication tables

v t e Number theory
Fields	Algebraic number theory (class field theory,non-abelian class field theory,Iwasawa theory,Iwasawa–Tate theory,Kummer theory) Analytic number theory (analytic theory of L-functions,probabilistic number theory,sieve theory) Geometric number theory Computational number theory Transcendental number theory Diophantine geometry (Arakelov theory,Hodge–Arakelov theory) Arithmetic combinatorics (additive number theory) Arithmetic geometry (anabelian geometry,p-adic Hodge theory) Arithmetic topology Arithmetic dynamics
Key concepts	Numbers 0 Natural numbers Unity Prime numbers Composite numbers Rational numbers Irrational numbers Algebraic numbers Transcendental numbers p-adic numbers (p-adic analysis) Arithmetic Modular arithmetic Chinese remainder theorem Arithmetic functions
Advanced concepts	Quadratic forms Modular forms L-functions Diophantine equations Diophantine approximation Irrationality measure Simple continued fractions
Category List of topics List of recreational topics Wikibook Wikiversity