topic badge

12.12 Algorithms for divisibility

Lesson

Introduction

In mathematics, we use and follow  algorithms  all the time. We follow steps and processes to calculate and solve problems. A great example to look at is using algorithms to determine whether a number is divisible by other numbers. We call these divisibility tests.

Let's begin with a simple divisibility test.

Divisibility algorithms

How do you know if a number is divisible by 10? That's easy, right? You just check to see if it ends in a zero. That's an algorithm right there. You just specified a test and a check to sort numbers for those that are divisible by 10 and for those that are not. It's a type of search and sort algorithm.

To test whether numbers are divisible by 2, 4, 5, or 8, we have similar very simple algorithms to follow:

  • If a number is divisible by 2, then the number ends with an even numbe

  • If the last two digits are divisible by 4, then the whole number is divisible by 4.

  • If a number is divisible by 5, then the number ends in a 0 or a 5

  • If the last three digits are divisible by 8, then the whole number is divisible by 8.

To test whether a number is divisible by 3, we use the following algorithm:

  1. Find the sum of the digits of the number.

  2. If the sum is a multiple of 3, then the number itself is a multiple of 3.

To test whether a number is divisible by 9, we use the following algorithm:

  1. Find the sum of the digits of the number.

  2. If the sum is divisible by 9, then the number is also divisible by 9.

To test whether a number is divisible by 6, we use the following algorithm:

  1. Test whether the number is divisible by 2.

  2. Test whether the number is divisible by 3.

In the question set you'll see a few others that we haven't seen here, so just follow the steps to use them.

Examples

Example 1

Consider the following numbers: 940, \, 257, \, 8535,\, 486,\, 1923,\,11\,705,\, 21\,735,\, 92\,872,\, 98\,941,\, 77\,990,\, 2327, \, 6644, \, 985, \, 605, \, 8470

a

List all the numbers that are divisible by 10.

Worked Solution
Create a strategy

Choose all the numbers that end in a 0.

Apply the idea

940, \, 77\,990, \, 8470

b

List all the numbers that are divisible by 5.

Worked Solution
Create a strategy

Choose all the numbers that end in a 0 or a 5.

Apply the idea

940, \, 8535, \, 11\,705, \, 21\,735, \, 77\,990, \, 985, \, 605, \, 8470

c

List all the numbers that are divisible by 2.

Worked Solution
Create a strategy

Choose all the even numbers, or the numbers that end in a 0,2,4,6, or 8.

Apply the idea

940, \, 486, \, 92\,872, \, 77\,990, \, 6644,\, 8470

d

List all the numbers that are divisible by 10, 5 and 2.

Worked Solution
Create a strategy

Choose the numbers that appear in all of the three lists from parts (a), (b) and (c).

Apply the idea

940, \, 77\,990, \, 8470

Example 2

To test whether a number is divisible by 6, we use the following algorithm:

  • Step 1: Test whether the number is divisible by 2.

  • Step 2: Test whether the number is divisible by 3.

  • Step 3: If the number is divisible by both 2 and 3, then the number is divisible by 6.

Consider the number 42\,765.

a

Is 42\,765 divisible by 2?

Worked Solution
Create a strategy

Check if the last digit is even.

Apply the idea

The digit in the ones column, 5, is not even. So 42\,765 is not divisible by 2.

b

Is 42\,765 divisible by 3?

Worked Solution
Create a strategy

Find the sum of the digits and check if the sum is divisible by 3.

Apply the idea
\displaystyle \text{Sum of digits}\displaystyle =\displaystyle 4 + 2 + 7 + 6 + 5Add the digits together
\displaystyle =\displaystyle 24

24 is a multiple of 3 since 3\times 8 =24.

So 42\,765 is divisible by 3.

c

Is 42\,765 divisible by 6?

Worked Solution
Create a strategy

Refer to answers in parts (a) and (b) to see if the number is divisible by 2 and 3.

Apply the idea

The number is not divisible by 2 but is divisible by 3. Since it is not divisible by both numbers, it is not divisible by 6.

Idea summary

Divisibility tests are types of algorithms.

What is Mathspace

About Mathspace