HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Division, Divisibility Rules and Primes
  1. 1The division algorithm and divisibility
  2. 2Divisibility rules and why they work
  3. 3Primes and the fundamental theorem
  1. Mathematics
  2. /Division, Divisibility Rules and Primes
  3. /The division algorithm and divisibility

Course 27.1·Lesson 1 of 3

The division algorithm and divisibility

For whole numbers aaa and bbb with b>0b > 0b>0

Lesson 1 of 3Show all lessonsHide
Division, Divisibility Rules and Primes
  1. 1The division algorithm and divisibility
  2. 2Divisibility rules and why they work
  3. 3Primes and the fundamental theorem

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+ra = bq + ra=bq+r with 0≤r<b0 \le r < b0≤r<b, and prove that qqq and rrr are unique;
  • use the rules of divisibility, above all the rule for a combination ax+byax + byax+by;
  • prove a statement for every whole number by splitting into cases by the remainder.

Teams and leftovers

A school has 100100100 students. They are put into teams of 777. You get 141414 teams, and 222 students are left over. In symbols,

100=7×14+2.\displaystyle 100 = 7 \times 14 + 2.100=7×14+2.

The 141414 is the quotient and the 222 is the remainder. The remainder is smaller than the team size. If it were 777 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 aaa and bbb be integers with b>0b > 0b>0. Then there are integers qqq and rrr with

a=bq+r,0≤r<b,\displaystyle a = bq + r, \qquad 0 \le r < b,a=bq+r,0≤r<b,

and there is only one such pair.

Why is it true? Look at the multiples of bbb on the number line: …,−2b,−b,0,b,2b,…\dots, -2b, -b, 0, b, 2b, \dots…,−2b,−b,0,b,2b,…. They are bbb apart. The number aaa lies between two neighbours, so take bqbqbq to be the largest multiple of bbb that is not above aaa. Then r=a−bqr = a - bqr=a−bq is at least 000 and less than bbb.

Why only one pair? Suppose a=bq+r=bq′+r′a = bq + r = bq' + r'a=bq+r=bq′+r′, with both remainders in the range from 000 to b−1b - 1b−1. Then b(q−q′)=r′−rb(q - q') = r' - rb(q−q′)=r′−r. The right side lies strictly between −b-b−b and bbb. The only multiple of bbb there is 000. So r=r′r = r'r=r′ and q=q′q = q'q=q′.

Negative numbers

The rule 0≤r<b0 \le r < b0≤r<b holds for a negative aaa as well. Divide −17-17−17 by 555. The largest multiple of 555 that is not above −17-17−17 is −20-20−20. So

−17=5×(−4)+3.\displaystyle -17 = 5 \times (-4) + 3.−17=5×(−4)+3.

The remainder is 333, not −2-2−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-2−2 instead. In this chapter a remainder is never negative.

Divisibility

We say that bbb divides aaa, and write b∣ab \mid ab∣a, when a=bka = bka=bk for some integer kkk. Then bbb is a divisor (or factor) of aaa, and aaa is a multiple of bbb. For example 6∣426 \mid 426∣42 and 5∤425 \nmid 425∤42. Every integer divides 000.

These rules follow straight from the definition. Prove each one yourself by writing a=bka = bka=bk.

  1. If a∣ba \mid ba∣b and b∣cb \mid cb∣c, then a∣ca \mid ca∣c.
  2. If d∣ad \mid ad∣a and d∣bd \mid bd∣b, then d∣ax+byd \mid ax + byd∣ax+by for all integers xxx and yyy.
  3. If a∣ba \mid ba∣b and b≠0b \ne 0b=0, then ∣a∣≤∣b∣|a| \le |b|∣a∣≤∣b∣.
  4. If a∣ba \mid ba∣b and b∣ab \mid ab∣a, then a=ba = ba=b or a=−ba = -ba=−b.

Rule 2 is the workhorse of the chapter. If ddd divides two numbers, it divides their sum, their difference and any combination of them. Here is a quick use. If d∣7n+3d \mid 7n + 3d∣7n+3 and d∣5n+2d \mid 5n + 2d∣5n+2, then ddd divides 5(7n+3)−7(5n+2)=15(7n + 3) - 7(5n + 2) = 15(7n+3)−7(5n+2)=1. So d=±1d = \pm 1d=±1. The two numbers never share a factor bigger than 111.

Sorting by remainders

The division algorithm says that every integer leaves one of the remainders 0,1,…,b−10, 1, \dots, b - 10,1,…,b−1 on division by bbb. So every integer is of the form 2k2k2k or 2k+12k + 12k+1. Every integer is of the form 3k3k3k, 3k+13k + 13k+1 or 3k+23k + 23k+2. A proof about all integers can check these cases one at a time.

Squares on division by 4. If n=2kn = 2kn=2k, then n2=4k2n^2 = 4k^2n2=4k2, which leaves 000. If n=2k+1n = 2k + 1n=2k+1, then n2=4(k2+k)+1n^2 = 4(k^2 + k) + 1n2=4(k2+k)+1, which leaves 111. So a square never leaves 222 or 333 on division by 444. The same work shows that an odd square leaves 111 on division by 888, because k2+k=k(k+1)k^2 + k = k(k + 1)k2+k=k(k+1) is even.

A worked example

Prove that 6∣n3−n6 \mid n^3 - n6∣n3−n for every integer nnn.

  1. Factorise. n3−n=(n−1)n(n+1)n^3 - n = (n - 1)n(n + 1)n3−n=(n−1)n(n+1), a product of three consecutive integers.
  2. The factor 2. Of two consecutive integers, one is even. So 222 divides the product.
  3. The factor 3. Of three consecutive integers, one leaves remainder 000 on division by 333. So 333 divides the product.
  4. Combine. The number is a multiple of 222 and of 333. Since 222 and 333 share no factor, it is a multiple of 666.

The last step needs care. A number divisible by 444 and by 666 need not be divisible by 242424: think of 121212. We may multiply the two divisors only when they share no factor bigger than 111. Course 2 proves why.

In fact the product of any kkk consecutive integers is divisible by k!k!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+ra = bq + ra=bq+r. It tests the claim 6∣n3−n6 \mid n^3 - n6∣n3−n on two thousand numbers. Then it lists the remainders that squares leave on division by 333, 444 and 888.

Read it first. Then run it. Is the list of numbers that break the claim empty?

1. Change the claim to (n ** 5 - n) % 30. Does it still hold? Predict first.

2. Add 5 and 9 to the list of divisors in step 3. Which remainders can a square leave now?

Common mistakes

  • A negative remainder. The remainder of −17-17−17 on division by 555 is 333. It is never negative.
  • Multiplying divisors that share a factor. 4∣124 \mid 124∣12 and 6∣126 \mid 126∣12, but 24∤1224 \nmid 1224∤12.
  • Splitting a divisor of a product. 6∣4×96 \mid 4 \times 96∣4×9, yet 6∤46 \nmid 46∤4 and 6∤96 \nmid 96∤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+ra = bq + ra=bq+r with 0≤r<b0 \le r < b0≤r<b, and qqq, rrr are unique.
  • b∣ab \mid ab∣a means a=bka = bka=bk for an integer kkk.
  • If d∣ad \mid ad∣a and d∣bd \mid bd∣b, then d∣ax+byd \mid ax + byd∣ax+by.
  • A square leaves 000 or 111 on division by 333 and by 444. An odd square leaves 111 on division by 888.
  • The product of kkk consecutive integers is divisible by k!k!k!.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Divide −50-50−50 by 888. What are the quotient and the remainder?
  1. A number leaves remainder 555 when it is divided by 121212. What remainder does it leave when it is divided by 444?
  1. Show that no two of the numbers 4n+34n + 34n+3 and 3n+23n + 23n+2 share a factor bigger than 111, for any integer nnn.
  1. Can n2+2n^2 + 2n2+2 be a multiple of 444 for some integer nnn?
  1. Explain why the product of four consecutive integers is always divisible by 242424.

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.
No payment. You can leave at any time.

Problems (3)

A student notices that 2⁵ - 2 = 30, 3⁵ - 3 = 240 and 4⁵ - 4 = 1020 are all multiples of 30…Hard · High School (11–12) · by StemPy Lab
A locker code a is a whole number that leaves remainder 5 when it is divided by 9…Hard · High School (11–12) · by StemPy Lab
Multiply four consecutive whole numbers and add 1…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Divisibility rules and why they work
← Division, Divisibility Rules and Primes
← PreviousDivisibility rules and why they work →

Discussion (0)

Log in to join the discussion.

Loading…

there is exactly one way to write
a=bq+ra = bq + ra=bq+r
with
0≤r<b0 \le r < b0≤r<b
. This is the division algorithm. We say
b∣ab \mid ab∣a
when the remainder is
000
. A divisor of two numbers divides every combination
ax+byax + byax+by
. Sorting numbers by their remainders turns many proofs into a few short cases.
about 30 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Python Labs (1)

Division without the division keysPython Lab · by StemPy Lab