Divisibility — Mathematics Knowledge System

Overview

A divisor of an integer n is an integer d that can be multiplied by some integer to produce n; equivalently, n is a multiple of d. An integer n is divisible (or evenly divisible) by d if d is a divisor of n — meaning n divided by d leaves no remainder. For example, 7 is a divisor of 42 because 7 × 6 = 42, so 42 is divisible by 7. Divisibility is the most basic relation in number theory, underlying primes, factorization, the Euclidean algorithm, and modular arithmetic.

Intuition

Divisibility is about splitting a whole number into equal, whole-number-sized groups with nothing left over. 12 objects can be divided into 3 equal groups of 4 — no leftovers — so 3 (and 4) divide 12. But 12 objects can't be divided into 5 equal whole groups; you'd have leftovers, so 5 does not divide 12. This 'no remainder' idea is exactly what the division algorithm formalizes: any integer division leaves a well-defined remainder between 0 and the divisor minus 1, and divisibility is precisely the case where that remainder is 0.

Formal Definition

Definition

For integers a and b with a ≠ 0, a divides b (written a ∣ b) if there exists an integer k such that:

a \mid b \iff \exists k \in \mathbb{Z} : b = ka

Definition

7 \mid 42 \iff 42 = 7 \times 6

Example: 7 divides 42 because 42 = 7 × 6

b = aq + r, \quad 0 \le r < |a|

Any integer b can be written uniquely as a multiple of a plus a remainder r; a ∣ b exactly when r = 0

Division algorithm

Notation

Notation	Meaning
$a \mid b$	a divides b (b is a multiple of a)
$a \nmid b$	a does not divide b
$\{d : d \mid n\}$	The set of all positive divisors of n, e.g. Div(60) = {1,2,3,4,5,6,10,12,15,20,30,60}

Properties

Reflexivity

a \mid a \text{ for every nonzero integer } a

Transitivity

a \mid b \text{ and } b \mid c \implies a \mid c

Linearity (closure under sum/difference)

a \mid b \text{ and } a \mid c \implies a \mid (b+c) \text{ and } a \mid (b-c)

Multiplicativity by a constant

a \mid b \implies a \mid bc \text{ for any integer } c

Cancellation

ka = b \iff kac = bc \quad (c \neq 0)

Every integer divides 0; 1 and -1 divide every integer

a \mid 0 \text{ for all } a \neq 0; \quad 1 \mid n \text{ for all } n

Applications

Divisibility tests (by 2, 3, 5, 9, 11, etc.) are used in checksum and hash algorithms, and modular reduction via divisibility underlies cryptographic primitives like RSA.

Worked Examples

Check if there's an integer k with 84 = 6k.
$84 / 6 = 14 \in \mathbb{Z}$

Answer: Yes, 6 ∣ 84, since 84 = 6 × 14.

Practice Problems

Difficulty 2/10

Is 9 a divisor of 123?

Difficulty 4/10

If a ∣ b and a ∣ c, prove a ∣ (2b - 3c).

Difficulty 4/10

A warehouse must ship 1,260 items in full boxes with no leftovers. Can boxes of 8 be used? Boxes of 9? Use divisibility rules.

Common Mistakes

Common Mistake

Thinking 0 divides every number, or that a number can divide 0 the same way any pair divides.

By definition a ∣ b requires a ≠ 0 (division by zero is undefined), but every nonzero a DOES divide 0, since 0 = a·0.

Common Mistake

Assuming divisibility is symmetric — if a ∣ b then b ∣ a.

Divisibility is generally NOT symmetric: 3 ∣ 12 but 12 ∤ 3. It's only symmetric when a = ±b.

Quiz

'a divides b' (a ∣ b) means:

b/a is less than 1there is an integer k with b = k·a (no remainder)a is bigger than ba and b are prime

A number is divisible by 9 exactly when:

it ends in 9the sum of its digits is divisible by 9it is evenits last digit is 0

Summary

a divides b (a ∣ b) when b = ka for some integer k — b is a multiple of a with no remainder.
The division algorithm writes any b uniquely as b = aq + r with 0 ≤ r < |a|; divisibility is the r = 0 case.
Divisibility is reflexive and transitive, and is preserved under addition, subtraction, and scalar multiplication.
Divisibility is not symmetric: 3∣12 does not imply 12∣3.
Divisibility underlies GCD/LCM, modular arithmetic, and the Euclidean algorithm.

References

BookBurton, D.M. Elementary Number Theory, 7th ed. Ch. 2.
WebsiteWikipedia — Divisor