Incubator escapee wiki

Modular arithmetic

Article Discussion
(Redirected from Modulo arithmetic)

Template:Short description Template:About

File:Clock group.svg
Time-keeping on this clock uses arithmetic modulo 12. Adding 4 hours to 9 o'clock gives 1 o'clock, since 13 is congruent to 1 modulo 12.

In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

A familiar example of modular arithmetic is the hour hand on a 12-hour clock. If the hour hand points to 7 now, then 8 hours later it will point to 3. Ordinary addition would result in Template:Nowrap, 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 is congruent 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).

CongruenceEdit

Given an integer Template:Math, called a modulus, two integers Template:Mvar and Template:Mvar are said to be congruent modulo Template:Mvar, if Template:Mvar is a divisor of their difference; that is, if there is an integer Template:Math such that

Template:Math.

Congruence modulo Template:Mvar is a congruence relation, meaning that it is an equivalence relation that is compatible with addition, subtraction, and multiplication. Congruence modulo Template:Mvar is denoted by

Template:Math.

The parentheses mean that Template:Math applies to the entire equation, not just to the right-hand side (here, Template:Mvar).

This notation is not to be confused with the notation Template:Math (without parentheses), which refers to the remainder of Template:Math when divided by Template:Math, known as the modulo operation: that is, Template:Math denotes the unique integer Template:Mvar such that Template:Math and Template:Math.

The congruence relation may be rewritten as

Template:Math,

explicitly showing its relationship with Euclidean division. However, the Template:Math here need not be the remainder in the division of Template:Math by Template:Math Rather, Template:Math asserts that Template:Math and Template:Math have the same remainder when divided by Template:Math. That is,

Template:Math,
Template:Math,

where Template:Math is the common remainder. We recover the previous relation (Template:Math) by subtracting these two expressions and setting Template:Math

Because the congruence modulo Template:Mvar is defined by the divisibility by Template:Mvar and because Template:Math is a unit in the ring of integers, a number is divisible by Template:Math exactly if it is divisible by Template:Mvar. This means that every non-zero integer Template:Mvar may be taken as modulus.

ExamplesEdit

In modulus 12, one can assert that:

Template:Math

because the difference is Template:Math, a multiple of Template:Math. Equivalently, Template:Math and Template:Math have the same remainder Template:Math when divided by Template:Math.

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 propertiesEdit

Template:Anchor The congruence relation satisfies all the conditions of an equivalence relation:

If Template:Math and Template:Math, or if Template:Math, then:<ref>Template:Cite book</ref>

If Template:Math, then it is generally false that Template:Math. However, the following is true:

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

The last rule can be used to move modular arithmetic into division. If Template:Math divides Template:Math, then Template:Math.

The modular multiplicative inverse is defined by the following rules:

The multiplicative inverse Template:Math may be efficiently computed by solving Bézout's equation Template:Math for Template:Math, Template:Math, by using the Extended Euclidean algorithm.

In particular, if Template:Math is a prime number, then Template:Math is coprime with Template:Math for every Template:Math such that Template:Math; thus a multiplicative inverse exists for all Template:Math that is not congruent to zero modulo Template:Math.

Advanced propertiesEdit

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

Congruence classes Edit

The congruence relation is an equivalence relation. The equivalence class modulo Template:Mvar of an integer Template:Math is the set of all integers of the form Template:Math, where Template:Mvar is any integer. It is called the congruence class or residue class of Template:Math modulo Template:Math, and may be denoted Template:Math, or as Template:Math or Template:Math when the modulus Template:Math is known from the context.

Each residue class modulo Template:Math contains exactly one integer in the range <math>0, ..., |m| - 1</math>. Thus, these <math>|m|</math> integers are 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, Template:Math denotes generally the unique integer Template:Mvar such that Template:Math and Template:Math; it is called the residue of Template:Math modulo Template:Math.

In particular, Template:Math is equivalent to Template:Math, and this explains why "Template:Math" is often used instead of "Template:Math" in this context.

Residue systemsEdit

Each residue class modulo Template:Math 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>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> (since this is the proper remainder which results from division). Any two members of different residue classes modulo Template:Math are incongruent modulo Template:Math. Furthermore, every integer belongs to one and only one residue class modulo Template:Math.<ref>Template:Harvtxt</ref>

The set of integers Template:Math is called the least residue system modulo Template:Math. Any set of Template:Math integers, no two of which are congruent modulo Template:Math, is called a complete residue system modulo Template:Math.

The least residue system is a complete residue system, and a complete residue system is simply a set containing precisely one representative of each residue class modulo Template:Math.<ref>Template:Harvtxt</ref> For example, the least residue system modulo Template:Math is Template:Math. Some other complete residue systems modulo Template:Math include:

Some sets that are not complete residue systems modulo 4 are:

Reduced residue systemsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Given the Euler's totient function Template:Math, any set of Template:Math integers that are relatively prime to Template:Math and mutually incongruent under modulus Template:Math is called a reduced residue system modulo Template:Math.<ref>Template:Harvtxt</ref> The set Template:Math from above, for example, is an instance of a reduced residue system modulo 4.

Covering systemsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Covering systems represent yet another type of residue system that may contain residues with varying moduli.

Integers modulo mEdit

In the context of this paragraph, the modulus Template:Math is almost always taken as positive.

The set of all congruence classes modulo Template:Math is a ring called the ring of integers modulo Template:Math, and is denoted <math display=inline>\mathbb{Z}/m\mathbb{Z}</math>, <math>\mathbb{Z}/m</math>, or <math>\mathbb{Z}_m</math>.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> The ring <math>\mathbb{Z}/m\mathbb{Z}</math> is fundamental to various branches of mathematics (see Template:Section link below). (In some parts of number theory the notation <math>\mathbb{Z}_m</math> is avoided because it can be confused with the set of [[P-adic integer|Template:Math-adic integers]].)

For Template:Math 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 Template:Math, <math>\mathbb{Z}/m\mathbb{Z}</math> is the zero ring; when Template:Math, <math>\mathbb{Z}/m\mathbb{Z}</math> is not an empty set; rather, it is isomorphic to <math>\mathbb{Z}</math>, since Template:Math.

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 <math>m\mathbb{Z}</math>, the set formed by all multiples of Template:Math, i.e., all numbers Template:Math with <math>k\in\mathbb{Z}.</math>

Under addition, <math>\mathbb Z/m\Z</math> is a cyclic group. All finite cyclic groups are isomorphic with <math>\mathbb Z/m\mathbb Z</math> for some Template:Mvar.<ref>Sengadir T., Template:Google books</ref>

The ring of integers modulo Template:Math is a field, i.e., every nonzero element has a multiplicative inverse, if and only if Template:Math is prime. If Template:Math is a prime power with Template:Math, there exists a unique (up to isomorphism) finite field <math>\mathrm{GF}(m) =\mathbb F_m</math> with Template:Math elements, which is not isomorphic to <math>\mathbb Z/m\mathbb Z</math>, which fails to be a field because it has zero-divisors.

If Template:Math, <math>(\mathbb Z/m\mathbb Z)^\times</math> denotes the [[multiplicative group of integers modulo n|multiplicative group of the integers modulo Template:Math]] that are invertible. It consists of the congruence classes Template:Math, where Template:Math is coprime to Template:Math; these are precisely the classes possessing a multiplicative inverse. They form an abelian group under multiplication; its order is Template:Math, where Template:Mvar is Euler's totient function.

ApplicationsEdit

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 and musical 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 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 systems such as RSA and Diffie–Hellman, and provides finite fields which underlie elliptic curves, and is used in a variety of symmetric key algorithms 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>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

In computer science, modular arithmetic is often applied in bitwise operations and other operations involving fixed-width, cyclic data structures. The modulo operation, as implemented in many programming languages and calculators, 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 is considered the same as D-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), economics (e.g., game theory) and other areas of the social sciences, where proportional division and allocation of resources plays a central part of the analysis.

Computational complexityEdit

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 Template:Math]], to be performed efficiently on large numbers.

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

Solving a system of non-linear modular arithmetic equations is NP-complete.<ref>Template:Cite book</ref>

See alsoEdit

Template:Div col

Template:Div col end

NotesEdit

Template:Reflist

ReferencesEdit

External linksEdit

Template:Number theory

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Modular_arithmetic&oldid=12998"