divisibilitet

Divisibility is a relation between integers. For integers a and b, a is said to divide b if there exists an integer k such that b = a·k. The relation is written as a | b. In this sense, a is a divisor of b and b is a multiple of a. For example, 3 | 12 because 12 = 3·4, while 5 does not divide 14.

Basic properties: If a ≠ 0 and a | b and a | c, then a | (b + c) and a | (b − c). If a | b, then a | (k·b) for any integer k. Every nonzero a divides itself, a | a. The divisibility relation is reflexive (a | a) and transitive (if a | b and b | c, then a | c). In the integers, restricting to positive a gives a partial order on the positive integers up to units ±1.

Common divisibility tests: 2 | n if n is even; 3 | n if the sum of digits is divisible by 3; 5 | n if the last digit is 0 or 5. A prime number is a positive integer greater than 1 whose only positive divisors are 1 and itself. The fundamental theorem of arithmetic states that every integer greater than 1 has a unique prime factorization, up to order and sign; divisibility underpins gcd, lcm, and congruences. In modular arithmetic, a ≡ b (mod n) means n divides a − b. Divisibility is used in problems from factoring to cryptography.