Divisibility & the division algorithm
a ∣ b means b = ak for some integer k — a statement about existence, which is why divisibility proofs start by naming that k. The division algorithm says that for any a and b > 0 there are UNIQUE integers q and r with a = bq + r and 0 ≤ r < b. That uniqueness is what makes remainders well defined and underpins everything that follows.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Unfold the definition immediatelyFrom a ∣ b write b = ak with k an integer, and work with the equation rather than the symbol.
- Chain divisibilities by substitutionIf a ∣ b and b ∣ c then c = b m = a k m, so a ∣ c. Transitivity is one substitution.
- Use the linear combination propertyIf d ∣ a and d ∣ b then d ∣ (ax + by) for all integers x, y. This single fact drives most divisibility proofs.
- Apply the division algorithm for case analysisEvery integer is bq + r for exactly one r in 0…b−1, so splitting into residue cases is exhaustive.
Worked example
Prove that if d ∣ a and d ∣ b then d ∣ (3a − 5b).
- From d ∣ a write a = dm; from d ∣ b write b = dn, with m, n ∈ ℤ.
- Substitute: 3a − 5b = 3dm − 5dn.
- Factor: = d(3m − 5n).
- 3m − 5n is an integer, so the product is d times an integer.
Answer. d ∣ (3a − 5b), by the linear combination property.
Where marks get dropped
These are the specific errors that cost credit on divisibility & the division algorithm questions — QED's rubric penalises each of them separately.
- Confusing a ∣ b with a/b. The first is a statement (true or false), the second is a number.
- Allowing a negative remainder. The division algorithm requires 0 ≤ r < b, so −7 = 3(−3) + 2, not 3(−2) − 1.
- Forgetting that everything divides 0, and that 0 divides only 0. These edge cases appear in exam counterexamples.
Practise this until it is automatic
Unlimited fresh questions
QED generates new divisibility & the division algorithm problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Number Theory mastery is tracked so you know when this is exam-ready.
Divisibility & the division algorithm — frequently asked questions
Why does every integer divide 0?
Because 0 = a · 0 for any a, and 0 is an integer. Conversely 0 ∣ b forces b = 0.
How do I compute the remainder for a negative number?
Choose q so the remainder lands in [0, b). For −17 divided by 5, q = −4 gives r = 3, since −17 = 5(−4) + 3.
Why is the division algorithm called an algorithm?
Historically, because repeated subtraction computes q and r. The modern statement is an existence-and-uniqueness theorem, proved via well-ordering.
The rest of Number Theory
Divisibility, primes, gcd, modular arithmetic. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Divisibility & the division algorithm
- 2Primes & unique factorisation
- 3gcd, lcm & the Euclidean algorithm
- 4Modular arithmetic & congruences
- 5Solving linear congruences
- 6Fermat’s little theorem
- 7The Chinese remainder theorem
- 8Modular inverses & fast exponentiation
- 9Euler’s totient φ(n) & Euler’s theorem
- 10Base-b representations & digit arguments
- 11RSA & modular exponentiation in cryptography
- 12Wilson’s theorem & primality testing
- 13Linear Diophantine equations ax + by = c
Ready to make divisibility & the division algorithm exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →