The modulo operation produces the remainder after dividing one integer by another. For integers a and n (with n>0), division produces a quotient q and remainder r satisfying a = qn + r, where typically 0 ≤ r < n. A simple example is 5 modulo 2 = 1 because 5 = 2·2 + 1. Notation varies: mathematicians write a ≡ b (mod n) for congruence and often use the shorthand "a mod n"; computer languages commonly use symbols such as % or functions named mod. See mathematics for background concepts and integers for the number set involved.

Basic definitions and distinctions

Two related ideas are important to keep distinct. The remainder is the nonnegative leftover r from Euclidean division. Congruence modulo n is an equivalence relation: a and b are congruent modulo n when their difference is divisible by n, written a ≡ b (mod n). The modulus n is the divisor that defines the equivalence classes. In some contexts people allow different conventions for the remainder (for example negative remainders), so it helps to state the convention used when communicating results. The words "modulo" and "mod" are used in both arithmetic and formal expressions; see entries about whole numbers and division.

Key algebraic properties

Modulo arithmetic preserves many familiar operations, allowing computations to be reduced modulo n at intermediate steps. Important properties include:

  • Addition: (a + b) mod n = ((a mod n) + (b mod n)) mod n.
  • Multiplication: (a·b) mod n = ((a mod n)·(b mod n)) mod n.
  • Exponentiation: a^k mod n can be computed efficiently by repeated squaring, reducing modulo n at each step.
  • Modular inverse: a has an inverse modulo n (an x with ax ≡ 1 (mod n)) precisely when gcd(a,n) = 1; the extended Euclidean algorithm finds such inverses.

Computation and programming notes

When implemented on computers and calculators, the exact result for negative operands can differ between languages and libraries. Some systems return a remainder that shares the sign of the dividend, others guarantee a nonnegative result between 0 and n−1. Because of that, many programmers explicitly normalize results to a chosen representative r in the canonical interval. Efficient algorithms for modular arithmetic are central to cryptography and number-theoretic code.

History, applications, and notable facts

Modular ideas date back to classical divisibility and the Euclidean algorithm; systematic study of congruences was popularized by Carl Friedrich Gauss in 1801. Today modular arithmetic appears across mathematics and computing: clock arithmetic is a familiar everyday example (hours on a 12-hour clock are taken mod 12), hashing and checksums use remainders to map data to fixed ranges, and public-key cryptography relies on modular exponentiation and inverses. The Chinese Remainder Theorem shows how simultaneous congruences modulo coprime moduli combine into a single solution modulo their product.

Examples and practical tips

Concrete examples help build intuition: 17 mod 5 = 2 because 17 = 3·5 + 2; (-3) mod 4 is often taken as 1 in the nonnegative convention because -3 = (-1)·4 + 1. In algorithm design reduce large intermediate values by applying mod frequently to avoid overflow and to keep numbers small. When solving equations, modular reduction converts infinite integer problems into finite computations on residue classes, which is a powerful simplification in number theory and cryptography.