divisibility

Divisibility is a relation between integers that formalizes the idea of one number containing another as a repeated unit. For integers a and b, we say that a divides b, written a | b, if there exists an integer k such that b = a k. In standard use, a ≠ 0 is assumed. If a | b, then b is a multiple of a and a is a divisor of b.

A key consequence is that every multiple of a is obtained by multiplying a by an integer. The number 0 is divisible by every nonzero integer, since 0 = a · 0. Conversely, in this setup, 0 does not divide any nonzero number.

Divisors and multiples: The divisors of a positive integer n are the integers d with d | n; when restricted to positive divisors, these are the positive divisors of n. The multiples of a are the integers a k with k ∈ Z.

Fundamental results include the prime factorization theorem: every integer greater than 1 has a unique representation as a product of primes. This underlies the greatest common divisor (gcd) and least common multiple (lcm): gcd(a,b) is the largest integer dividing both, and lcm(a,b) is the smallest integer divisible by both. Bézout’s identity states that gcd(a,b) is a linear combination of a and b, and the gcd can be computed efficiently by the Euclidean algorithm.

Modulo arithmetic and tests: In modular arithmetic, a ≡ b (mod n) means n divides a − b. Simple tests exist: a number is divisible by 2 if it is even; by 3 if the sum of its digits is divisible by 3; by 5 if it ends in 0 or 5.

Examples: 12 | 60, 7 | 21, but 4 ∤ 18.