In mathematics, modular arithmetic is a system of arithmetic for integers, 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 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 over at zero when it reaches 12. We say that 15 is congruent to 3 modulo 12, written 15 ≡ 3 (mod 12), so that 7 + 8 ≡ 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 ≡ 4 (mod 12).

Congruence

Given an integer m ≥ 1, called a modulus, two integers a and b are said to be congruent modulo m, if m is a divisor of their difference; that is, if there is an integer k such that

a − b = k m.

Congruence modulo 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 m is denoted

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 modulo operation, the remainder of b when divided by m: 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 Euclidean division. 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 remainder 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 divisibility by m and because -1 is a unit 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.

Examples

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:

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

Basic properties

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

• Reflexivity: a ≡ a (mod m)
• Symmetry: a ≡ b (mod m) if b ≡ a (mod m).
• Transitivity: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m)

If a₁ ≡ b₁ (mod m) and a₂ ≡ b₂ (mod m), or if a ≡ b (mod m), then:^[1]

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

If a ≡ b (mod m), then it is generally false that k^a ≡ k^b (mod m). However, the following is true:

• If c ≡ d (mod φ(m)), where φ is Euler's totient function, then a^c ≡ a^d (mod m)—provided that a is coprime with m.

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

• If a + k ≡ b + k (mod m), where k is any integer, then a ≡ b (mod m).
• If k a ≡ k b (mod m) and k is coprime with m, then a ≡ b (mod m).
• If k a ≡ k b (mod k m) and k ≠ 0, then a ≡ b (mod m).

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 modular multiplicative inverse is defined by the following rules:

• Existence: There exists an integer denoted a⁻¹ such that aa⁻¹ ≡ 1 (mod m) if and only if a is coprime with m. This integer a⁻¹ is called a modular multiplicative inverse of a modulo m.
• If a ≡ b (mod m) and a⁻¹ exists, then a⁻¹ ≡ b⁻¹ (mod m) (compatibility with multiplicative inverse, and, if a = b, uniqueness modulo m).
• If ax ≡ b (mod m) and a is coprime to m, then the solution to this linear congruence is given by x ≡ a⁻¹b (mod m).

The multiplicative inverse x ≡ a⁻¹ (mod m) may be efficiently computed by solving Bézout's equation a x + m y = 1 for x, y, by using the Extended Euclidean algorithm.

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.

Advanced properties

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

• Fermat's little theorem: If p is prime and does not divide a, then a^p−1 ≡ 1 (mod p).
• Euler's theorem: If a and m are coprime, then a^φ(m) ≡ 1 (mod m), where φ is Euler's totient function.
• A simple consequence of Fermat's little theorem is that if p is prime, then a⁻¹ ≡ a^p−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⁻¹ ≡ a^φ(m)−1 (mod m).
• Another simple consequence is that if a ≡ b (mod φ(m)), where φ is Euler's totient function, then k^a ≡ k^b (mod m) provided k is coprime with m.
• Wilson's theorem: p is prime if and only if (p − 1)! ≡ −1 (mod p).
• Chinese remainder theorem: For any a, b and coprime m, n, there exists a unique x (mod m n) such that x ≡ a (mod m) and x ≡ b (mod n). In fact, x ≡ b m_n⁻¹ m + a n_m⁻¹ n (mod mn) where m_n⁻¹ is the inverse of m modulo n and n_m⁻¹ is the inverse of n modulo m.
• Lagrange's theorem: The congruence f (x) ≡ 0 (mod p), where p is prime, and f (x) = a₀ x^m + ... + a_m is a polynomial with integer coefficients such that a₀ ≠ 0 (mod p), has at most m roots.
• Primitive root modulo m: A number g is a primitive root modulo m if, for every integer a coprime to m, there is an integer k such that g^k ≡ a (mod m). A primitive root modulo m exists if and only if m is equal to 2, 4, p^k or 2p^k, 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.
• Quadratic residue: An integer a is a quadratic residue modulo m, if there exists an integer x such that x² ≡ a (mod m). Euler's criterion 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).

Congruence classes

The congruence relation is an equivalence relation. The equivalence class 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 as (a mod m), or as a or when the modulus m is known from the context.

Each residue class modulo m contains exactly one integer in the range ${\displaystyle 0,...,|m|-1}$. Thus, these ${\displaystyle |m|}$ 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, (a mod m) denotes generally the unique integer k such that 0 ≤ k < m and k ≡ 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.

Residue systems

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^[2] (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.^[3]

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 representative of each residue class modulo m.^[4] For example, the least residue system modulo 4 is {0, 1, 2, 3}. Some other complete residue systems modulo 4 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 are not complete residue systems modulo 4 are:

• {−5, 0, 6, 22}, since 6 is congruent to 22 modulo 4.
• {5, 15}, since a complete residue system modulo 4 must have exactly 4 incongruent residue classes.

Reduced residue systems

Given the Euler's totient function φ(m), any set of φ(m) integers that are relatively prime to m and mutually incongruent under modulus m is called a reduced residue system modulo m.^[5] The set {5, 15} from above, for example, is an instance of a reduced residue system modulo 4.

Covering systems

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 m is almost always taken as positive.

The set of all congruence classes modulo m is called the ring of integers modulo m,^[6] and is denoted ${\textstyle \mathbb {Z} /m\mathbb {Z} }$, ${\displaystyle \mathbb {Z} /m}$, or ${\displaystyle \mathbb {Z} _{m}}$.^[7] The notation ${\displaystyle \mathbb {Z} _{m}}$ is, however, not recommended because it can be confused with the set of m-adic integers. The ring ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ is fundamental to various branches of mathematics (see § Applications below).

For m > 0 one has

${\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, ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ is the zero ring; when m = 0, ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ is not an empty set; rather, it is isomorphic to ${\displaystyle \mathbb {Z} }$, since a₀ = {a}.

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

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

The properties given before imply that, with these operations, ${\displaystyle \mathbb{Z}}$Zdroj:https://en.wikipedia.org?pojem=Integers_modulo_n
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.