Try the code and the simulations beside the lesson.
What you will be able to do
write any whole number, positive or negative, as a=bq+r with 0≤r<b, and prove that q and r are unique;
use the rules of divisibility, above all the rule for a combination ax+by;
prove a statement for every whole number by splitting into cases by the remainder.
Teams and leftovers
A school has 100 students. They are put into teams of 7. You get 14 teams, and 2 students are left over. In symbols,
100=7×14+2.
The 14 is the quotient and the 2 is the remainder. The remainder is smaller than the team size. If it were 7 or more, we could make one more team.
The division algorithm
In number theory, "number" means a whole number, positive, negative or zero. Mathematicians call these the integers.
The division algorithm. Let a and b be integers with b>0. Then there are integers q and r with
a=bq+r,0≤r<b,
and there is only one such pair.
Why is it true? Look at the multiples of b on the number line: …,−2b,−b,0,b,2b,…. They are b apart. The number a lies between two neighbours, so take bq to be the largest multiple of b that is not above a. Then r=a−bq is at least 0 and less than b.
Why only one pair? Suppose a=bq+r=bq′+r′, with both remainders in the range from 0 to b−1. Then b(q−q′)=r′−r. The right side lies strictly between −b and b. The only multiple of b there is 0. So r=r′ and q=q′.
Negative numbers
The rule 0≤r<b holds for a negative a as well. Divide −17 by 5. The largest multiple of 5 that is not above −17 is −20. So
−17=5×(−4)+3.
The remainder is 3, not −2.
A number line from -25 to 5 with the multiples of 5 marked as blue dots at -25, -20, -15, -10, -5 and 0. A red dot marks -17. A green bar runs from -20 up to -17 and is labelled r = 3. A label under the line reads -17 = 5 times (-4) + 3, so the remainder is 3 and not -2.
Python's // and % follow this rule. Some other languages, and some calculators, give −2 instead. In this chapter a remainder is never negative.
Divisibility
We say that bdividesa, and write b∣a, when a=bk for some integer k. Then b is a divisor (or factor) of a, and a is a multiple of b. For example 6∣42 and 5∤42. Every integer divides 0.
These rules follow straight from the definition. Prove each one yourself by writing a=bk.
If a∣b and b∣c, then a∣c.
If d∣a and d∣b, then d∣ax+by for all integers x and y.
If a∣b and b=0, then ∣a∣≤∣b∣.
If a∣b and b∣a, then a=b or a=−b.
Rule 2 is the workhorse of the chapter. If d divides two numbers, it divides their sum, their difference and any combination of them. Here is a quick use. If d∣7n+3 and d∣5n+2, then d divides 5(7n+3)−7(5n+2)=1. So d=±1. The two numbers never share a factor bigger than 1.
Sorting by remainders
The division algorithm says that every integer leaves one of the remainders 0,1,…,b−1 on division by b. So every integer is of the form 2k or 2k+1. Every integer is of the form 3k, 3k+1 or 3k+2. A proof about all integers can check these cases one at a time.
Squares on division by 4. If n=2k, then n2=4k2, which leaves 0. If n=2k+1, then n2=4(k2+k)+1, which leaves 1. So a square never leaves 2 or 3 on division by 4. The same work shows that an odd square leaves 1 on division by 8, because k2+k=k(k+1) is even.
A worked example
Prove that 6∣n3−n for every integer n.
Factorise.n3−n=(n−1)n(n+1), a product of three consecutive integers.
The factor 2. Of two consecutive integers, one is even. So 2 divides the product.
The factor 3. Of three consecutive integers, one leaves remainder 0 on division by 3. So 3 divides the product.
Combine. The number is a multiple of 2 and of 3. Since 2 and 3 share no factor, it is a multiple of 6.
The last step needs care. A number divisible by 4 and by 6 need not be divisible by 24: think of 12. We may multiply the two divisors only when they share no factor bigger than 1. Course 2 proves why.
In fact the product of any k consecutive integers is divisible by k!, because the quotient is a binomial coefficient, which counts something and so is a whole number.
Practise with new numbers
Try it in Python
The program writes three divisions in the form a=bq+r. It tests the claim 6∣n3−n on two thousand numbers. Then it lists the remainders that squares leave on division by 3, 4 and 8.
Common mistakes
A negative remainder. The remainder of −17 on division by 5 is 3. It is never negative.
Multiplying divisors that share a factor.4∣12 and 6∣12, but 24∤12.
Splitting a divisor of a product.6∣4×9, yet 6∤4 and 6∤9. Only a prime may be split this way, as lesson 3 shows.
Checking a few numbers and calling it a proof. A table can find a pattern. Only an argument for every case proves it.
Remember these
Division algorithm: a=bq+r with 0≤r<b, and q, r are unique.
b∣a means a=bk for an integer k.
If d∣a and d∣b, then d∣ax+by.
A square leaves 0 or 1 on division by 3 and by 4. An odd square leaves 1 on division by 8.
The product of k consecutive integers is divisible by k!.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Divide −50 by 8. What are the quotient and the remainder?
A number leaves remainder 5 when it is divided by 12. What remainder does it leave when it is divided by 4?
Show that no two of the numbers 4n+3 and 3n+2 share a factor bigger than 1, for any integer n.
Can n2+2 be a multiple of 4 for some integer n?
Explain why the product of four consecutive integers is always divisible by 24.
References
David M. Burton, Elementary Number Theory, Chapter 2, sections 2.2 and 2.3 on the division algorithm and divisibility.
NCERT, Mathematics Textbook for Class X, Chapter 1 (Real Numbers), for the division of integers in school form.
Enroll free in Division, Divisibility Rules and Primes
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.