propertiesdivisibility

Divisibility is a relation between integers. For integers a and b, a divides b (written a|b) if there exists an integer k such that b = a·k. When a ≠ 0, this means b is a multiple of a; in particular, a divides 0 for every nonzero a.

Basic properties follow from the definition. If a|b, then a| (b + a·t) for any integer t, since b + a·t = a·(k + t). If a|b and b|c, then a|c (transitivity). If a|b, then a|b·d for any integer d. If gcd(a,b) = 1 and a|b·c, then a|c (Euclid’s lemma). For primes p, if p|a·b then p|a or p|b (prime divisibility).

The relation interacts with greatest common divisor and least common multiple. The gcd of a and b is the largest positive integer that divides both a and b. The lcm of a and b is the smallest positive integer that is divisible by both. A fundamental relation is gcd(a,b)·lcm(a,b) = |a·b|.

Divisibility underpins many tests and concepts in number theory, including modular arithmetic, factoring strategies, and algorithms like the Euclidean algorithm for computing gcd. It also yields practical criteria for checking divisibility, such as prime-power tests and residue-based arguments in modular contexts.

Examples: 6|30 since 30 = 6·5. 4 does not divide 18, but 3|18 and 6|18. More generally, 12|144 since 144 = 12·12.