Divisibility and the Division Algorithm
Fix what divides means, prove that division leaves a unique quotient and remainder, and use that uniqueness as the base of everything after it.
What a learner can do afterwards
- Prove basic divisibility facts directly from the definition rather than by example
- State and prove the division algorithm, including the uniqueness of the remainder
- Use the remainder cases to prove a statement about all integers
1 · Read
To say a divides b means some integer c gives b = a times c, and proofs must start from that sentence rather than from examples. From this one definition flow the workhorse facts: divisibility passes through sums, through multiples, and through chains, so if a divides b and b divides c, then a divides c.
The division algorithm promises that for any integer a and positive d, exactly one pair q and r satisfies a = d times q plus r with 0 <= r < d. Existence says a remainder can always be found, and uniqueness says only one qualifies. For example, 47 = 6 times 7 plus 5, and negative 16 = 26 times negative 1 plus 10, where the remainder is 10 rather than negative 6 because remainders cannot be negative.
The nonnegativity condition does the heavy lifting: it forces exactly one remainder to qualify and throws out lookalikes like negative 6. Every proof about remainders starts by invoking this pair, so learn its statement word perfect before using it.
Remainder cases prove statements about all integers at once. Every integer is even or odd, so write n as 2k or 2k plus 1 and square. An even square is 4 times k squared, leaving remainder 0, and an odd square is 4 times k times k plus 1 plus 1, leaving remainder 1. Hence every integer squared leaves remainder 0 or 1 on division by 4.
Divisibility means a product exists, division leaves one legal remainder, and remainder cases settle claims about all integers.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.