Divisibility

01Start with one complete packet

The positive integers 1, 2, 3, … count whole objects. Include 0 and the negative numbers $-1, -2, -3$, … and we obtain the integers, often denoted by $\mathbb Z$. Negative integers can record an opposite direction or a decrease; they do not mean a negative fraction of a counter. Our packet picture will begin with nonnegative quantities, meaning zero or a positive integer.

Press “Next packing step” below. Each press puts four counters into a complete packet. A teal group is one packet; grey counters are still waiting. Six packets use $6 \times 4 = 24$ counters. Subtracting 24 from 26 leaves 2. Since 2 is less than the four needed for another packet, we must stop. The last step marks those two in gold: they are now the remainder. Press “Pack one at a time” to play, “Next packing step” to move one packet, and “Reset animation” to start over. Changing either quantity starts the construction again.

Change the total to 24 while keeping four in each packet. We get exactly six packets: $24 = 4 \times 6$, with nothing left. We write this whole-number relationship as $4 \mid 24$, read “4 divides 24”. The vertical line is not a division sign. It states something that can be true or false. The statement $4 \mid 24$ is true, while $4 \mid 26$ is false. The calculation $26 \div 4 = 6.5$ is valid, but 6.5 is not an integer number of complete packets.

Here $d$ is the size of a part, $n$ is the total and $q$ is the integer multiplier. This is a definition: it says what divisibility means, rather than claiming something we must prove. “Some integer $q$” means at least one suitable integer, not every integer. For $3 \mid 12$, the witness is $q = 4$ because $12 = 3 \times 4$. To see why 5 does not divide 12, compare neighbouring multiples: $5 \times 2 = 10 < 12 < 15 = 5 \times 3$. There is no integer between 2 and 3, so there is no suitable $q$.

The equation definition goes further than our picture. We have $3 \mid 0$ because $0 = 3 \times 0$; $3 \mid -12$ because $-12 = 3 \times (-4)$; and $-3 \mid 12$ because $12 = (-3) \times (-4)$. Every nonzero integer therefore divides 0, and a negative sign need not prevent divisibility. The divisors $d$ and $-d$ divide exactly the same integers: replace the multiplier $q$ by $-q$.

02A remainder, and why it is unique

Our 26 counters gave six packets of four and two left over, so $26 = 4 \times 6 + 2$. The number of complete packets, 6, is the quotient; the final leftover, 2, is the remainder. The equation alone is not enough: 26 also equals $4 \times 5 + 6$, but those six leftovers can fill another packet. To record a finished division, the remainder must be at least zero and strictly smaller than the divisor.

For positive $n$ we can keep removing $d$ until fewer than $d$ remain. What about negative $n$? Dividing $-17$ by 5 does not give $-2$ as our standard remainder. Place $-17$ between the neighbouring multiples $-20$ and $-15$. Starting from the left multiple $-20$, move three units right to reach $-17$. Thus $-17 = 5 \times (-4) + 3$: the quotient is $-4$ and the remainder is 3, with $0 \le 3 < 5$. The remainder records a position inside a length-five interval on the number line.

Why can every integer $n$ be written this way? Mark all the multiples of $d$ on the number line: …, $-2d, -d, 0, d, 2d$, …, each $d$ apart from the next. Then $n$ lies in one gap, from some multiple $dq$ up to, but not including, the next multiple $d(q + 1)$. Call $r$ its distance to the right of $dq$. Then $n = dq + r$ with $0 \le r < d$. The $-17$ example was exactly this: it lies between $-20$ and $-15$, three units from $-20$.

Why two different answers cannot both satisfy the rule

Try it with numbers first: 26 can also be written $4 \times 5 + 6$, but the six left over can fill another packet, so that version is not allowed. The remainder must be smaller than one packet, so there is only one answer. The letters below say the same thing again; skip them if you like.Suppose the same $n$ has two permitted descriptions, $n = dq + r = dq' + r'$, with both remainders between 0 and $d - 1$. Subtract $dq'$ and $r$ to get $d(q - q') = r' - r$. The right side lies strictly between $-d$ and $d$. The left side is an integer multiple of $d$: if $q - q' \ge 1$ it is at least $d$; if $q - q' \le -1$ it is at most $-d$. Only $q - q' = 0$ can fit inside that range. Hence $q = q'$, and substituting back gives $r = r'$. Both answers are unique.

Consequently $d \mid n$ exactly when the standard remainder is zero. A zero remainder gives $n = dq$, which is the definition of divisibility. Conversely, if $n = dk$, the pair $(k, 0)$ already satisfies the remainder rules. Uniqueness forces the standard remainder to be zero. “Exactly when”, or “if and only if”, makes a claim in both directions; we have checked each one.

03Turn divisibility into useful equations

When we see $d \mid a$, we can replace it with $a = ds$ for an integer $s$. That equation lets us calculate. For example, $6 \mid 18$ and $6 \mid 30$ mean $18 = 6 \times 3$ and $30 = 6 \times 5$. Adding gives $18 + 30 = 6 \times (3 + 5) = 6 \times 8$, so 6 divides the sum. Subtracting gives $30 - 18 = 6 \times (5 - 3) = 6 \times 2$, so it divides the difference too.

Here is the general argument. If $a = ds$ and $b = dt$, choose any integers $u$ and $v$. Then $ua + vb = u(ds) + v(dt) = d(us + vt)$. The expression $us + vt$ is an integer because sums and products of integers are integers. Thus $d \mid (ua + vb)$. We call $ua + vb$ an integer linear combination of $a$ and $b$: we add integer multiples of the two numbers. Negative multiples are allowed, so this includes subtraction.

We can also follow a chain of multiples. If $a \mid b$ and $b \mid c$, write $b = as$ and $c = bt$. Substitute the first into the second: $c = (as)t = a(st)$. Since $st$ is an integer, $a \mid c$. For instance, $3 \mid 12$ and $12 \mid 60$ give $60 = 12 \times 5 = 3 \times 4 \times 5 = 3 \times 20$. This property is called transitivity; the reason is the integer equation we just constructed.

04Why common divisors survive

Sometimes we want the same packet size to divide two quantities without leftovers. The positive divisors of 18 are 1, 2, 3, 6, 9 and 18. Those of 30 are 1, 2, 3, 5, 6, 10, 15 and 30. We can pair them as $18 = 1 \times 18 = 2 \times 9 = 3 \times 6$ and $30 = 1 \times 30 = 2 \times 15 = 3 \times 10 = 5 \times 6$. Test each positive candidate from 1 up to the input; keep exactly those that divide it with no remainder. That gives the complete list. No larger positive divisor is possible, and the next paragraph explains why. For 18: $1 \times 18$, $2 \times 9$, $3 \times 6$ — the paired factors have all appeared. The shared entries 1, 2, 3 and 6 are their common divisors; the greatest is 6. We write $\gcd (18,30) = 6$, where $\gcd$ abbreviates greatest common divisor.

Why does a greatest common divisor exist? For positive $a$ and $b$, the number 1 divides both, so the list is nonempty. If a positive $d$ divides $a$, the multiplier in $a = dq$ must be a positive integer, at least 1; hence $d \le a$. Similarly $d \le b$. Common divisors therefore lie in a finite list from 1 to the smaller input, so a greatest one exists. Numbers whose $\gcd$ is 1 are called coprime; this does not say that each number must itself be prime.

Listing all divisors becomes slow for larger numbers. We want to replace a pair by smaller numbers without losing any common divisor. Try 84 and 30: $84 = 2 \times 30 + 24$. Removing two copies of 30 leaves 24. Each “Next division” below cuts the dividend into complete copies of the divisor and a gold remainder, keeping the same length scale. The next pair is the divisor and the remainder. Earlier equations remain in the table, and you can go back or reset.

Prove that the replacement preserves the whole list

First take a common divisor $d$ of 84 and 30. It divides the integer combination $84 - 2 \times 30 = 24$, so it is a common divisor of 30 and 24. Conversely, a common divisor of 30 and 24 divides $2 \times 30 + 24 = 84$, so it also divides 84 and 30. We have preserved the entire list in both directions, not merely happened to retain its largest entry. The greatest entries must therefore agree.

For the general equation, a common divisor of $a$ and $b$ divides $r = a - qb$; a common divisor of $b$ and $r$ divides $a = qb + r$. Repeating the replacement takes (84,30) to (30,24), then (24,6), then (6,0). The three divisions are $84 = 2 \times 30 + 24, 30 = 1 \times 24 + 6$ and $24 = 4 \times 6 + 0$.

Why stop here? Every nonzero integer divides 0, so the positive common divisors of 6 and 0 are exactly the divisors of 6, with greatest member 6. Every row preserved the common divisors, hence $\gcd (84,30)$ is also 6. More generally $\gcd (a,0) = a$ for positive a. This repeated division is the Euclidean algorithm. It must stop: each new remainder is a nonnegative integer strictly smaller than the current positive divisor. We cannot descend strictly forever within the finite list 0, 1, …, $b - 1$. The zero remainder is not the answer; the answer is the last nonzero number before it.

05Trace the remainder back to the original numbers

The algorithm gives more than the answer 6. It records how each remainder came from the preceding pair. We want to express 6 using only the original 84 and 30. Then any divisor of those inputs must also divide this expression. Begin with $6 = 30 - 24$. The 24 is not an original input, but the first row says $24 = 84 - 2 \times 30$. Substitute that whole expression for 24.

The minus sign before the bracket acts on every term inside: subtracting “84 minus two copies of 30” means subtracting 84 and adding back those two copies. The strips below show these calculations: 84 minus two copies of 30 gives the remainder; 30 minus that remainder gives the next length. After substitution, the three copies of 30 can be joined to check the result. Dashed red marks the removed length and gold marks what remains. Selecting a step holds the picture still so we can compare it with the algebra.

$A$ and $B$ are the two numbers kept at this step; $u$, $v$, $s$ and $t$ record how many copies of $a$ and $b$ each one contains. When the letters get heavy, look at the worked numbers below and come back.Why does this work for other positive inputs? Initially $a = 1a + 0b$ and $b = 0a + 1b$ are integer combinations. If the current pair is $A = ua + vb$ and $B = sa + tb$, the next remainder $R = A - qB$ equals $(u - qs)a + (v - qt)b$. Its coefficients are still integers. Thus both original inputs and every number retained later keep this form. The last nonzero number can be an initial input: in $6 = 2 \times 3 + 0$, the answer 3 equals $0 \times 6 + 1 \times 3$ rather than a newly computed nonzero remainder. Together with the algorithm proof, this gives integers $u$ and $v$ satisfying $au + bv = \gcd (a,b)$. This is Bézout’s identity. It comes from the records of the divisions.

The condition that lets us separate a product

Return to the inference about a product. Now suppose $\gcd (a,b) = 1$ and $a \mid bc$. Bézout gives $au + bv = 1$. Multiply by $c$ so that the known product $bc$ appears: $acu + bcv = c$. The first term is a multiple of a. The second is too: write $bc = ak$ for an integer $k$, so $bcv = a(kv)$. Adding gives $c = a(cu + kv)$, with an integer in brackets. Hence $a \mid c$. The coprime condition matters: without it we cannot start with the identity equal to 1.

For example, 4 and 9 are coprime: $9 - 2 \times 4 = 1$, so any positive common divisor divides 1 and must be 1. If $4 \mid 9c$, then $4 \mid c$; explicitly $c = 9c - 2 \times 4c$ is a difference of multiples of 4. By contrast, $6 \mid 2 \times 3$ does not imply $6 \mid 3$, because $\gcd (6,2) = 2$. The required condition is absent.

06Why primes are the pieces of multiplication

Write $60 = 6 \times 10$, then split 6 into $2 \times 3$ and 10 into $2 \times 5$. We obtain $60 = 2 \times 3 \times 2 \times 5 = 2^{2} \times 3 \times 5$. The notation $2^{2}$ abbreviates two copies of 2 multiplied together. Each final factor is greater than 1 and has no positive divisor other than 1 and itself. It cannot be split into two positive integers both greater than 1. Such a number is prime. An integer greater than 1 that is not prime is composite; 1 is neither prime nor composite.

This convention keeps 1 out of the prime pieces. Allowing it would let us insert any number of extra factors 1 without changing the product, so the number of pieces could not be unique. Prime factorisation records the factors greater than 1. We must now prove two things: every integer greater than 1 can be fully split, and different routes cannot give different final prime pieces.

Existence: splitting cannot leave an unsplittable exception

Suppose some integer greater than 1 cannot be written as a product of primes. Choose the least such $N$, using the least-member property again. It cannot be prime: a prime itself is a one-factor prime product. Thus $N$ is composite, so $N = ab$ with $a > 1$ and $b > 1$. Since $b \ge 2$, we get $a = N/b \le N/2 < N$; similarly $b < N$. Both are smaller than the least exception, so each has a prime factorisation. Multiplying those factorizations produces one for $N$, a contradiction. No exception exists.

Uniqueness: a prime factor must appear on both sides

We first need one tool. If a prime $p$ divides $ab$, either $p$ divides a or it does not. The first case already gives a factor it divides. In the second case, the only positive divisors of $p$ are 1 and $p$, and $p$ is not a divisor of a. Hence $\gcd (p,a) = 1$. The coprime rule from the preceding section gives $p \mid b$. Thus a prime dividing a product divides at least one factor. For a longer finite product, separate its first factor from the rest and repeat on the rest when necessary. The finite number of factors ensures we reach one that $p$ divides.

Suppose one positive integer has two prime factorizations. Take the first prime $p$ on the left. It divides the left product, hence the equal product on the right. The preceding argument says it divides some prime $q$ on the right. The only positive divisors of $q$ are 1 and $q$; since $p > 1, p = q$. Move $q$ to the front and divide both sides by the nonzero $p$, removing a matching pair. Repeat for the remaining products until one side has no factors. The other must then have none either: an empty product is 1, but a nonempty product of primes is at least 2. Thus the prime factors and their numbers of occurrences agree, apart from order.

Existence together with uniqueness up to order is called the fundamental theorem of arithmetic. The name labels the result; its justification is the two arguments above. We now have a reason why counting copies of a prime factor does not depend on which splitting route we chose.

07Common copies and enough copies

Compare $60 = 2^{2} \times 3 \times 5$ with $72 = 2^{3} \times 3^{2}$. Check the latter step by step: $72 = 2 \times 36 = 2 \times 2 \times 18 = 2 \times 2 \times 2 \times 9 = 2^{3} \times 3^{2}$. Each row below contains one kind of prime, and each chip is one factor in a product. Look at how many copies both columns can supply: two copies of 2, one of 3, and no shared copy of 5. Teal chips pair these common copies.

Why do copies determine divisibility? If $d \mid a$, write $a = dk$ with positive integer $k$. Factor $d$ and $k$ and multiply. Uniqueness says that the count of each prime in $d$ plus its count in $k$ equals its count in a. Thus $d$ cannot contain more copies of any prime than a. Conversely, if $d$ needs no more of any prime than a contains, remove those copies from a’s factorisation. The remaining product is an integer $k$, giving $a = dk$. Both directions hold.

To divide both inputs, we may take only the smaller count of each prime. Here the common product is $2^{2} \times 3 = 4 \times 3 = 12$. It divides both: $60 = 12 \times 5$ and $72 = 12 \times 6$. Every other common divisor has no more copies of any prime than this product, so it divides 12 and cannot exceed 12. This proves $\gcd (60,72) = 12$, beyond what the picture alone suggests.

Now reverse the question: find the smallest positive integer that is a multiple of both 60 and 72. This is their least common multiple, abbreviated $\operatorname{lcm}$. To contain both inputs, it needs at least the larger count of each prime. Take $2^{3} \times 3^{2} \times 5 = 8 \times 9 \times 5 = 360$. Indeed $360 = 60 \times 6 = 72 \times 5$. Every other positive common multiple contains at least these copies, so it is a positive integer multiple of 360 and cannot be smaller. Hence $\operatorname{lcm} (60,72) = 360$. We require a positive multiple because zero is also a multiple of both and would change the question.

In general, suppose a prime occurs $\alpha$ times in a and $\beta$ times in $b$. The $\gcd$ takes the smaller count and the $\operatorname{lcm}$ the larger. Their product has $\alpha + \beta$ copies: if $\alpha \le \beta$ this is $\alpha + \beta$; otherwise it is $\beta + \alpha$. The product $ab$ has that same count. Since this holds for each prime, uniqueness gives $\gcd (a,b) \times \operatorname{lcm} (a,b) = ab$. Here $12 \times 360 = 4320 = 60 \times 72$.

08Use the tools in complete proofs

Example 1: consecutive integers have no common factor greater than 1

Take a positive integer $n$. If a positive $d$ divides both $n$ and $n + 1$, it divides their difference $(n + 1) - n = 1$. If $d$ divides 1, then $1 = dk$ with positive integers $d$ and $k$, both at least 1. Only $d = k = 1$ can give that product. Thus every positive common divisor is 1, and 1 does divide both, so $\gcd (n,n + 1) = 1$. We kept $n$ arbitrary; the argument used only the difference of one.

Example 2: the product of three consecutive integers is divisible by 6

Take any integer $n$, including negative ones, and put $P = n(n + 1)(n + 2)$. First find a factor 2. Division with remainder says $n$ has remainder 0 or 1 when divided by 2. If $n = 2k$, $n$ contains that factor. If $n = 2k + 1$, then $n + 1 = 2(k + 1)$ does. Hence $P = 2u$ for an integer $u$. These are all possible remainders, so there is no third case left unchecked.

Next find a factor 3. The possible remainders are 0, 1 and 2. If $n = 3k$, $n$ is a multiple of 3. If $n = 3k + 1$, then $n + 2 = 3(k + 1)$. If $n = 3k + 2$, then $n + 1 = 3(k + 1)$. Hence $3 \mid P$. To combine the factors, recall $P = 2u$ and therefore $3 \mid 2u$. Since $\gcd (3,2) = 1$, the coprime rule gives $3 \mid u$, so $u = 3v$. Substituting yields $P = 2 \times 3v = 6v$. That proves $6 \mid P$ rather than merely asserting that separate divisibility by 2 and 3 is enough.

Example 3: a finite list cannot contain every prime

Suppose someone claims to have listed every prime as $p_{1},p_{2},\dots ,p_{k}$. The list is finite and includes at least the prime 2. Multiply its entries and add one: $N = p_{1}p_{2}\cdots p_{k} + 1$. Since $N > 1$, the factorisation existence proof guarantees a prime factor $q$ of $N$. If $q$ were on the list, it would divide the product $p_{1}p_{2}\cdots p_{k}$. It also divides $N$, so it would divide their difference 1. But a prime $q > 1$ cannot divide 1. Therefore $q$ is absent from the list, contradicting the claim of completeness. There cannot be only finitely many primes.

Notice exactly what we proved: $N$ has a prime factor outside the list, not that $N$ itself is always prime. For the list 2,3,5,7,11,13 successive products are 6, 30, 210, 2310, 30030, so the product plus one is 30031, and $30031 = 59 \times 509$ because $59 \times (500 + 9) = 29500 + 531$. $N$ being composite does not harm the argument; a prime factor outside the list is enough. A proof should not claim more than its reasoning establishes.

09Practise with reasons

Try writing the reason for each answer before opening the solution. Check whether a rule was reversed without justification, whether any integer or remainder cases were missed, and whether each division was permitted.

We can now do more than count leftovers. The integer-multiple definition lets us combine equations; those combinations explain why the Euclidean algorithm preserves common divisors; and substitution back explains cancellation under a coprime condition. This chain will be useful for congruences and integer equations. The following pages will recall the needed reasoning where it is used, rather than requiring us to supply it from memory.