Modular arithmetic
https://en.wikipedia.org/wiki/Modular_arithmetic
Terms
modular arithmetic modulus wrap-around operation, wrap-around addition congruence relation
Modular arithmetic
Modular Arithmetic (MA) is a special system of integer arithmetic, where integers exhibit the wrap-around behavior after reaching a certain value, called modulus.
The modern approach to MA was developed by Carl Friedrich Gauss in his book "Disquisitiones Arithmeticae" from 1801.
An example of MA, familiar to everone is the 24-hour clock, where the hours wrap around after reaching 23. Addition in this system also wraps around, such that if it's 19 o'clock, then 8 hours later is 3 o'clock, for 27 ≡ 3 (mod 12).
The essence of modular arithmetic is the congruence relation, which is an equivalence relation, that relates two integers with the same property: they have the same remainder when divided by the same modulus.
The congruence relation is denoted by a ≡ b (mod m) meaning that a is congruent to b modulo m.
a ≡ b (mod m), where ∀_ ∈ ℤ, means:
a / m = r = b / ma and b have the same remainder, r, when divided by ma = kb + m a - m = kb
b = ka + m b - m = ab
a = km + b
km = a - b
a ≡ b (mod m) => m|(a − b)
(∀m ∈ ℤ. m > 1). (∀ab ∈ ℤ).
a ≡ b (mod m) => m|(a − b)(∀m ∈ ℤ. m > 1). (∀ab ∈ ℤ). (∃k ∈ ℤ).
k * m = a - bcongruence relation:
a ≡ b (mod n)"a is congruent to b modulo m"congruence relation:
a = kn + balt notation for congruence relationa (mod n)
5 (mod 7) ≠ 5 (mod 6) [...aren't-they-different-types?]
Modular arithmetic
Given a modulus m, where m ∈ ℤ ∧ m > 1, two integers a and b are said to be congruent modulo m if m is a divisor of their difference, i.e. if there exists an integer k such that a − b = kn, denoted:
(∀m ∈ ℤ. m > 1). (∀ab ∈ ℤ). (∃k ∈ ℤ). k * m = a - b
(∀m ∈ ℤ. m > 1). (∀ab ∈ ℤ). a ≡ b (mod m) => m|(a − b)
Two distinct moduli form incompatible classes of integers, for example 5 (mod 7) ≠ 5 (mod 6) ! Therefore, a modulus enforces a certain type constraint. Before, there were ℤ, now there are ℤ/m ℤ.
a ≡ b (mod n) -> n ∣ a−b
that is, a − b = kn (for some integer k) such that a = kn + b
Euclidean division: n/m = (q, r) that is n = mq + r
Congruence
Congruence modulo n is a congruence relation, a sort of equivalence relation, compatible with addition, subtraction and multiplication. Congruence modulo n is denoted a ≡ b (mod n).
The parentheses in the notation mean that the (mod n) part applies to the entire equation, not just to the RHS. This notation is not to be confused with b mod n, i.e. parentheses-less, which is the modulo operation.
a = b mod n denotes the unique integer a so 0 <= a < n and a ≡ b (mod n), that is, the remainder of b when divided by n.
By the way, Euclidean division is n = mq + r such that m != 0 and n,m,q ∈ ℤ and r ∈ ℕ and 0 <= r < q where m is a divisor, q a quotient (multiplier), r a remainder of dividing n with m.
n/m = (q, r) i.e. n = mq + r
Properties of congruence relation
The congruence relation satisfies all the conditions of an equivalence relation:
Reflexivity : a ≡ a (mod n)
Symmetry : ∀abn. b ≡ a (mod n) --> a ≡ b (mod n)
Transitivity : a ≡ b (mod n) ∧ b ≡ c (mod n) --> a ≡ c (mod n)
a ≡ b (mod n) ->
compatibility with translation : ∀k ∈ ℤ. a+k ≡ b+k (mod n)
compatibility with scaling : ∀k ∈ ℤ. ak ≡ bk (mod n)
compatibility with exponentiation : ∀k ∈ ℕᐩ. aᵏ ≡ bᵏ (mod n)
compatibility with polynomial evaluation: p(a) ≡ p(b) (mod n) for any polynomial p(x) with integer coefficients
a₁ ≡ b₁ (mod n) ∧ a₂ ≡ b₂ (mod n) -->
compatibility with addition : a₁+a₂ ≡ b₁+b₂ (mod n)
compatibility with subtraction : a₁-a₂ ≡ b₁-b₂ (mod n)
compatibility with multiplication : a₁a₂ ≡ b₁b₂ (mod n)
[TBC...]
Congruence classes
This set, consisting of all the integers congruent to 𝓪 modulo 𝓷, is called the congruence class (also residue or residue class) of the integer 𝓪 modulo 𝓷. When the modulus 𝓷 is known from the context, that residue may also be denoted [𝓪].
Residue systems
Each residue class modulo 𝓷 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 (since this is the proper remainder which results from division).
Any two members of different residue classes modulo 𝓷 are incongruent modulo 𝓷. Furthermore, every integer belongs to exactly one residue class modulo 𝓷.
The set of integers {0, 1, 2, …, 𝓷 − 1} is called the least residue system modulo 𝓷. Any set of 𝓷 integers, no two of which are congruent modulo 𝓷, is called a complete residue system modulo 𝓷.
(...)
Modulo operation
https://en.wikipedia.org/wiki/Modulo_operation
Modulo operation returns the signed remainder of a division, called the modulus of the operation, after one number is divided by another.
Given two positive numbers a and n, a mod n is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.
The modulo operation is to be distinguished from the symbol mod, which refers to the modulus (or divisor) one is operating from, as in 9 ≡ 21 (mod 12).
For example, 5 mod 2 = 1 since 5/2 = (q:2, r:1)
Although typically performed with a and n both being integers, many computing systems now allow other types of numeric operands. The range of numbers for an integer modulo of n is 0 to n−1 inclusive (a mod 1 is always 0; a mod 0 is undefined).
When either a or n is negative, the naive definition breaks down, and PL differ in how these values are defined.
In math, the result of the modulo operation is an equivalence class and the smallest non-negative integer that belongs to that class is chosen as the class representative, being referred to as the least positive residue.
Almost everywhere, the quotient q and the remainder r of a divided by n satisfy the following conditions: q ∈ ℤ, n = mq + r, |r| < |n|
(...)
Modular exponentiation
https://en.wikipedia.org/wiki/Modular_exponentiation
Modular exponentiation is a type of exponentiation performed over a modulus.
The operation of modular exponentiation calculates the remainder when an integer 𝓫 (the base) raised to the 𝓮ᵗʰ power (the exponent), 𝓫ᵉ, is divided by a positive integer 𝓶 (the modulus).
In symbols, given base 𝓫, exponent e, and modulus 𝓶, the modular exponentiation 𝓬 is: 𝓬 = 𝓫ᵉ mod 𝓶. From the definition of 𝓬, it follows that 0 ≤ 𝓬 < 𝓶.
(...)
Last updated
Was this helpful?