Congruence (number theory)

Congruence modulo a positive integer means two integers have the same remainder when divided by that modulus. Equivalently, their difference is divisible by the modulus.

Modular arithmetic: Arithmetic in which integers are identified when they differ by a multiple of a fixed modulus. Congruence is the relation that makes this arithmetic possible.
Divisibility: The relation in which one integer is a multiple of another integer. Two integers are congruent exactly when their difference is divisible by the modulus.
Linear congruence: A modular equation of the form ax ≡ b (mod n), with integer coefficients and unknown. Its solvability is governed by the common divisors of the coefficient and modulus.
Equality: The relation stating that two mathematical objects are the same object. Congruent integers may differ, while equal integers cannot.
Residue class: The set of integers congruent to a given integer modulo a fixed modulus. Each congruence class groups precisely the integers equivalent under this relation.
Greatest common divisor: The greatest positive integer that divides each of two integers. It determines whether a coefficient can be cancelled or inverted modulo the modulus.
Fermat's little theorem: A theorem stating that a^(p−1) ≡ 1 modulo prime p when p does not divide a. It reduces large powers in calculations modulo a prime.
Approximate equality: A relation indicating that two values are close under a chosen tolerance or approximation. Congruence measures agreement of remainders, not closeness of integer values.
Euclidean division: The expression of an integer as a quotient times a positive divisor plus a remainder in a fixed range. Equal remainders in Euclidean division characterize congruent integers.
Prime number: An integer greater than 1 whose only positive divisors are 1 and itself. Prime moduli make every nonzero residue invertible.

Linked from 23 pages