Factors, multiples and divisibility

Can every counter belong to a complete group?

Arrange 17 counters into groups of five. Three complete groups use 15 counters, leaving two. Arrange 18 counters into groups of three instead: six complete groups use all 18. The second arrangement has no leftover counter.

We say that 3 divides 18 because 18 = 3·6. In this statement 3 is a factor, or divisor, of 18, and 18 is a multiple of 3. The number 5 does not divide 17: no integer number of five-counter groups accounts for exactly 17 counters.

Compare an incomplete and a complete grouping

The 17-counter picture has three complete five-counter groups and two leftovers: 17 = 5·3+2. The 18-counter picture has six complete three-counter groups and no leftover: 18 = 3·6.

A positive factor describes a possible complete group size; a multiple describes a total built from that size. The words look in opposite directions along the same equation. For example, 3 is a factor of 18, while 18 is a multiple of 3.

Start with grouping, then keep the integer conditions

Revisit the lesson Multiplication and division for equal groups and inverse operations, and the lesson Negative numbers and absolute value for signed values and distance from zero. Use the lesson Order of operations and arithmetic properties for signed products and distribution before working with negative divisors. The lesson Place value and number systems prepares the final-digit arguments.

On a first reading, work through the counter groups, the equation defining divisibility, and the quotient-and-remainder number line. Return to the general proofs and digit identities after practising signed multiplication and distribution in the published lesson Order of operations and arithmetic properties.

The proof methods and set language needed below are explained where they are used: an integer witness establishes divisibility, and a counterexample defeats a universal claim. Later lessons develop greatest common divisors and prime factorisation; neither is needed to justify the tests in this lesson.

The vertical bar is a statement, not a division sign

For integers d and n, write d | n if there is an integer k such that n = dk. Read this as “d divides n”. Write d ∤ n if no such integer exists. The integer k is a witness: substituting it checks the whole statement.

For example, −3 | 18 because 18 = (−3)(−6), and 3 | −18 because −18 = 3(−6). Changing either sign preserves divisibility: from n = dk, we also have n = (−d)(−k) and −n = d(−k).

A divisor statement asks for an integer k in n = dk. Signed values and zero are retained in the boxes; the result explains the particular statement.

The expression d | n is true or false. The quotient n/d is a number when d ≠ 0. For nonzero d, divisibility is equivalent to n/d being an integer, not merely to the quotient existing: 17/5 exists but is not an integer.

All variables in this definition are integers. Allowing a real witness would change the relation: 5·3.4 = 17 does not prove 5 | 17. A fractional number of counters is not a complete integer group.

State the zero convention before using it

We retain the definition d | n for all integers, including d = 0. Every integer d divides zero, because 0 = d·0. In particular 0 | 0 is true under this convention; there are many integer witnesses for that one statement.

Zero divides no nonzero integer: the product 0·k is always zero. Thus 0 ∤ 18. These product statements do not assign a value to 0/0 or permit division by zero. The quotient description of divisibility still requires d ≠ 0.

−7 | 0 is true because 0 = (−7)·0. The statement 0 | 18 is false because 0·k = 0 for every integer k. The statement 0 | 0 is true by the same product equation; no quotient with denominator zero is formed.

Some settings restrict the word divisor to nonzero integers. Our product definition explicitly allows zero, so we say “positive divisors” or “nonzero divisors” when that restriction is intended. Ordinary factor lists for positive totals use positive divisors.

The multiples of a fixed integer d are dk for all integers k. For d ≠ 0 this is a two-sided, equally spaced number-line pattern including zero; for d = 0 the only multiple is zero. The positive multiples of a positive d instead use k = 1,2,3,… .

A nonzero total puts a bound on its factors

If d | n and n ≠ 0, then d and its witness k are both nonzero. Hence |k| ≥ 1, and |n| = |d||k| ≥ |d| ≥ 1. Every integer divisor of a nonzero n therefore lies between −|n| and |n|, with zero excluded.

The positive divisors of 18 are 1,2,3,6,9,18. Checking possible d from 1 through 18 is a finite exhaustive method; pair each successful d with 18/d to obtain 1·18, 2·9 and 3·6. The integer divisors also include their negatives.

A finite window of the multiples of three

With divisor 3 and witnesses −6,−5,…,6, the multiples are −18,−15,…,18. Zero uses witness zero. This finite window shows part of an infinite two-sided pattern.

The divisors of −18 are the same integers as those of 18, because changing the sign of the witness changes the sign of the product. Zero behaves differently: every integer divides it, so it has infinitely many integer divisors and no largest positive divisor.

Do not replace divisibility by an inequality. Although 5 < 17, five does not divide 17. The size bound is necessary for a divisor of a nonzero total; it is not sufficient.

Mutual divisibility determines magnitude, not always sign

Every integer divides itself, using k = 1. Divisibility is not symmetric: 3 | 18 but 18 ∤ 3. Nevertheless, two different signed integers can divide each other: 3 | −3 and −3 | 3.

If a | b and b | a with a ≠ 0, write b = au and a = bv for integers u,v. Substitution gives a = auv, so cancelling the nonzero a gives uv = 1. The only integer possibilities are u = v = 1 or u = v = −1; therefore b = a or b = −a.

If a = 0 and b | a together with a | b, the latter condition forces b = 0. Combining both cases, mutual divisibility implies |a| = |b| for all integers. For positive integers, signs are fixed, so mutual divisibility implies a = b. This last property is called antisymmetry; it fails on all signed integers.

Cancellation needs its nonzero hypothesis. From 0 = 0·uv one cannot infer uv = 1. Separating the zero case avoids using an invalid division step.

Adding and subtracting preserve a common divisor

Suppose d | a and d | b. Choose integer witnesses a = du and b = dv. Then a+b = d(u+v) and a−b = d(u−v). The new witnesses are integers, so d divides both the sum and the difference.

More generally, for any integers s and t, sa+tb = d(su+tv). Thus d | (sa+tb). The expression sa+tb is an integer linear combination: multiply each input by an integer coefficient, then add. The proof also works when d = 0 because no division was used.

For example, 3 divides 12 and −6. It therefore divides 12+(−6) = 6, 12−(−6) = 18, and 2·12+5·(−6) = −6. The equation supplies a reason for every result, not just a pattern seen in a few examples.

The coefficients must remain integers. Although 3 | 6, the fractional coefficient 1/6 gives (1/6)·6 = 1, which 3 does not divide. With coefficient 1/4 the result 3/2 is not even an integer in the relation’s domain.

A divisor of a divisor is still a divisor

If a | b and b | c, choose fresh integers u and v with b = au and c = bv. Substituting gives c = a(uv). Since uv is an integer, a | c. This property is transitivity; the same proof includes all zero cases allowed by the definition.

Also, if d | a and t is an integer, then d | at because a = du gives at = d(ut). A multiple can be multiplied by another integer and remain a multiple of d.

The converse product claim is false in general: 6 | (2·3), but 6 ∤ 2 and 6 ∤ 3. Nor can a common divisor of a sum be assumed to divide each summand: 3 | (1+2), but it divides neither 1 nor 2. Track which direction the proved implication permits.

Keep the remainder between zero and a positive divisor

For an integer n and a positive integer d, there are unique integers q and r satisfying n = dq+r and 0 ≤ r < d. This is Euclidean division. The integer q is the quotient and r is the remainder; the phrase “division algorithm” names this theorem even before a computing procedure is specified.

For n = 17 and d = 5, use 17 = 5·3+2. For n = −17 and the same divisor, use −17 = 5·(−4)+3. The multiple −20 is at or to the left of −17, and the next multiple −15 is to its right; moving three units right from −20 reaches −17.

Compare the same divisor on opposite sides of zero

For −17 with divisor 5 the left multiple is −20 and the next is −15. The remainder is the distance 3 from −20 to −17. For 17 with divisor 5 the corresponding pair is 15 and 20, with remainder 2.

The equation −17 = 5·(−3)−2 is also arithmetically correct, but −2 is not an allowed Euclidean remainder. Choose the multiple at or immediately to the left of n. In symbols q = floor(n/d), where floor means the greatest integer at most the real quotient.

Remainder zero is exactly divisibility by positive d. If n = dk, the pair q = k,r = 0 meets the required interval and is the unique pair. Conversely a zero remainder writes n as d times an integer. Zero dividend has q = 0,r = 0 for every positive d.

Adjacent multiples explain existence and uniqueness

To see existence for any signed n, consider the nonnegative integers of the form n−dk with integer k. This collection is nonempty: for example k = −|n| gives n+d|n| ≥ 0 when d ≥ 1. Every nonempty collection of nonnegative integers has a smallest member; choose that member r = n−dq.

If r ≥ d, then r−d = n−d(q+1) is another nonnegative member, smaller than r. That contradicts minimality. Therefore 0 ≤ r < d, giving the required pair. The argument explains the boundary even for negative dividends.

For uniqueness, suppose n = dq+r = dq′+r′ with both remainders in that interval. Then d(q−q′) = r′−r and |r′−r| < d. A nonzero integer multiple of positive d has magnitude at least d, so q−q′ must be zero. The same equation then gives r = r′.

Without the remainder interval many pairs describe the same number: 17 = 5·2+7 = 5·3+2 = 5·4−3. Without d > 0 the interval stated here would not have the intended positive length. We do not use this theorem with d = 0.

Use the last one, two or three decimal places

For a nonnegative integer N in base ten, separate the final digit u: N = 10T+u with 0 ≤ u ≤ 9. Since 10T is divisible by 2, 5 and 10, each of those divisors divides N if and only if it divides u. This proves the even-final-digit test, the final-0-or-5 test, and the final-zero test respectively.

Separate the final two digits as a number v from 0 through 99: N = 100T+v. Since 100 = 4·25, 4 | N if and only if 4 | v. Similarly N = 1000T+w with 0 ≤ w ≤ 999, and 1000 = 8·125 gives 8 | N if and only if 8 | w.

See which decimal places the proof retains

Keep the final three-digit value

Both directions follow from adding or subtracting a known multiple. If the small ending is divisible, adding the earlier-place multiple gives N; if N is divisible, subtracting that multiple gives the small ending. It is an equivalence, not only a one-way shortcut.

For 1208, the final digit is 8, the final two-digit number is 8, and the final three-digit number is 208. Leading zeros in the ending do not change its value: 08 represents 8. Hence 1208 is divisible by 2,4,8, but not by 5 or 10. A shorter number can be padded with leading zeros for these tests.

Replace each power of ten by one for the digit sum

Write a finite decimal expansion N = a₀+a₁10+…+aₘ10ᵐ, with integer digits 0 through 9 and a₀ the units digit. Let S = a₀+a₁+…+aₘ. The difference N−S is the sum of aⱼ(10ʲ−1) over j ≥ 1.

For every integer j ≥ 1, 10ʲ−1 = 9(1+10+…+10ʲ⁻¹). Thus each term of N−S is a multiple of 9, and also of 3. The integer linear-combination property makes the whole finite difference a multiple of each divisor.

A digit sum preserves divisibility by nine

Sum the digits with weight one

Consequently 3 | N if and only if 3 | S, and 9 | N if and only if 9 | S. For 12348 the digit sum is 1+2+3+4+8 = 18, so both tests pass. For 1208 the sum is 11, so neither passes.

A digit sum need not be a single digit; check divisibility of the sum or repeat the same proved test on it. Ordinary digit sums do not test divisibility by 11: 29 has sum 11 but is not a multiple of 11.

For eleven, alternate signs from the units place

With the same digit indices, set A = a₀−a₁+a₂−a₃+…+(−1)ᵐaₘ. Begin with a plus sign at the units digit, then alternate while moving left. A can be negative, zero or positive; all integer multiples of 11, including zero, pass the test.

Each difference 10ʲ−(−1)ʲ is divisible by 11. At j = 0 it is zero. If the claim holds at j, then 10ʲ⁺¹−(−1)ʲ⁺¹ = 10[10ʲ−(−1)ʲ]+11(−1)ʲ, again a multiple of 11. Starting with j = 0 justifies the claim for every needed finite place.

Alternating signs preserve divisibility by eleven

Alternate plus and minus from the units place

For 4312 the 11-test weights, read from left to right, are −1,+1,−1,+1. Their digit contributions are −4,+3,−1,+2, summing to zero. The removed difference is 4312 = 11·392. The table records the selected test’s actual digits and weights.

Therefore N−A is an integer sum of multiples of 11. Adding or subtracting that difference proves 11 | N if and only if 11 | A. No modular arithmetic notation is required for the proof.

For 4312, read from the units digit: 2−1+3−4 = 0, so 11 divides 4312. For 12348 the value is 8−4+3−2+1 = 6, so it does not. Starting at the opposite end either gives the same value or its negative; divisibility is unchanged, but a fixed convention avoids a sign mix-up.

Use the test on a magnitude, then restore the sign

The decimal tests describe digits of N ≥ 0. For a negative integer n, apply them to |n|: d | n exactly when d | |n|. A minus sign is not a digit. For n = 0, every listed positive divisor passes, consistently with 0 = d·0 and the digit 0.

Choose the relevant reduction, check the small integer it produces, and explain why the removed difference is divisible by d. A successful test is backed by a proof; a finite interactive table is an illustration, not that proof.

If one of these tests fails, it rules out that particular divisor. If it passes, it establishes that divisor only. For example, 4 | 12 does not imply 8 | 12. Combining different tests without a proof can be misleading: 2 | 12 and 4 | 12 do not imply 8 | 12.

For an unfamiliar positive divisor, Euclidean division remains a complete check: compute n = dq+r with 0 ≤ r < d and decide whether r is zero. Keep the integer domain, the positive division divisor and any zero exception visible through the calculation.

Worked examples

Try it yourself

1. Decide 4 | 20, 20 | 4 and 4 | 18. Give a witness for every true statement.

   Show the answer and reasoning

   4 | 20 is true with witness 5. The other two statements are false.

   20 = 4·5. But 4/20 and 18/4 are not integers, so they cannot be integer witnesses for the reversed and final statements.

2. Decide −7 | 0, 0 | −7 and 0 | 0 under the product definition. Does any answer define 0/0?

   Show the answer and reasoning

   True, false, true respectively. None defines 0/0.

   0 = (−7)·0 and 0 = 0·0 give witnesses. Every product 0·k is zero, so it cannot equal −7. Divisibility is a product statement; division by zero remains undefined.

3. For nonzero n, does 1 ≤ |d| ≤ |n| guarantee d | n? Also explain why this bound cannot be applied to n = 0.

   Show the answer and reasoning

   No: d = 5,n = 17 meets the bound but 5 ∤ 17. For n = 0 every integer is a divisor, with no such finite bound.

   The proof uses a nonzero witness k to get |k| ≥ 1. When n = 0 a nonzero divisor can use k = 0; large d still gives d·0 = 0.

4. If a | b and b | a, must a = b? State what changes when both are positive.

   Show the answer and reasoning

   Not for all integers: 5 and −5 divide each other but are unequal. For positive a and b, mutual divisibility does imply a = b.

   In the nonzero case integer witnesses have product 1, so b = a or −a. Positivity removes the negative option. If either is zero, mutual divisibility forces both to be zero.

5. If d | x and d | (x+y), prove d | y without dividing by d.

   Show the answer and reasoning

   Write x = du and x+y = dv. Then y = d(v−u), with integer witness v−u.

   Subtract the two equations. This is valid even when d = 0: the assumptions then give x = 0 and x+y = 0, hence y = 0.

6. A learner says that 6 | xy implies 6 | x or 6 | y for all integers x,y. Give a counterexample.

   Show the answer and reasoning

   x = 2,y = 3: 6 | 6, but 6 ∤ 2 and 6 ∤ 3.

   A divisor of a product need not divide an individual factor. The valid forward rule says d | x implies d | xy for integer y; reversing it changes the claim.

7. Find the Euclidean pairs for n = −19,d = 4 and n = −20,d = 4. Which dividend is divisible by 4?

   Show the answer and reasoning

   For −19: q = −5,r = 1. For −20: q = −5,r = 0. Only −20 is divisible by 4.

   Both equations use the left multiple −20. The remainders 1 and 0 lie in [0,4). A zero remainder, rather than the sign of the dividend, decides divisibility.

8. Which of 4,8,9,11 divide 1001? Show the reduced integers used by the tests.

   Show the answer and reasoning

   Only 11. The last-two and last-three values are both 1, the digit sum is 2, and the alternating sum is 1−0+0−1 = 0.

   01 and 001 represent 1, which is divisible by neither 4 nor 8. The sum 2 fails 9. The alternating sum 0 passes 11; indeed 1001 = 11·91.

9. Explain why digit sum 11 does not prove 11 | 29, and state the correct 11 test on 29.

   Show the answer and reasoning

   The ordinary digit-sum proof applies to 3 and 9. For 11 use 9−2 = 7, which is not a multiple of 11; hence 11 ∤ 29.

   Ten differs from 1 by 9, not by a multiple of 11. It differs from −1 by 11, which produces alternating digit signs instead of an ordinary sum.

10. The equations 26 = 7·3+5 and 26 = 7·2+12 are correct. Why is only one a Euclidean division pair?

    Show the answer and reasoning

    Only q = 3,r = 5 has 0 ≤ r < 7. The remainder 12 is too large.

    Move one more complete group of seven from the remainder into the quotient: 12 = 7+5. The bounded-remainder condition makes the representation unique.

What to carry forward

• d | n is the integer-witness statement n = dk; a factor and a multiple are the two roles in this equation.
• Every integer divides zero; zero divides only zero under our stated convention. These facts never permit division by zero.
• A divisor of nonzero n has 1 ≤ |d| ≤ |n|. Mutual integer divisibility gives equal magnitudes, with equality when both integers are positive.
• Common divisors divide integer linear combinations; multiplying witnesses proves transitivity without a quotient.
• For positive d, Euclidean division has one pair n = dq+r with 0 ≤ r < d, including when n is negative.
• Decimal tests work because a number differs from its chosen ending, digit sum or alternating sum by a known multiple of the tested divisor.