# Algorithms for Divisibility

Lesson

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 Algorithm for testing the divisibility of 10

How do you know if a number is divisible by $10$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$10 and for those that are not. It's a type of "search and sort" algorithm.

##### Example

Examine the following list of number and use the divisibility test for $10$10 to determine which numbers are divisible by $10$10

$24$24  $350$350 $752$752 $1060$1060  $2001$2001  $10$10 $50$50 $30021$30021  $52700$52700

Using our simple algorithm, we search each number for a zero on the end and then we sort those that do have a zero on the end from those that don't. So we get the following numbers as being divisible by 10.

$350$350 $1060$1060  $10$10  $50$50 $52700$52700

## Divisibility Algorithms for 2 and 5

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

Divisibility Tests for 2 and 5

Divisibility Test for $5$5

"If a number is divisible by $5$5 then the number ends in a $0$0 or a $5$5"

Divisibility Test for $2$2

"If a number is divisible by $2$2, then the number ends with an even number"

Try those two tests for the following list of numbers.

$35$35 $42$42 $150$150 $47$47 $681$681 $768$768 $1025$1025 $251$251 $10058$10058 $12435$12435

What did you notice about $150$150?

## Divisibility Algorithm for 4

To test whether a number is divisible by $4$4 requires a little more work. The algorithm is as follows:

“If the last two digits are divisible by $4$4, then the whole number is divisible by $4$4.”

##### example

Show the use of the divisibility by $4$4 algorithm to test whether $52636$52636 is divisible by $4$4.

To use the algorithm, we take the last two digits and determine whether they are a multiple of $4$4 (can be divided evenly by $4$4).

$\frac{36}{4}=9$364=9

So this tells us that $52636$52636 can be divided by $4$4.

## Divisibility Algorithm for 8

To test whether a number is divisible by $8$8 we use the following algorithm:

“If the last three digits are divisible by $8$8, then the whole number is divisible by $8$8.”

Try this algorithm for yourself with the number $12360$12360

You might like to use short division to see whether $360$360 can be divided evenly by $8$8. You can do a final check by dividing $12360$12360 by $8$8 on your calculator.

## Divisibility Algorithm for 3

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

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

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

##### example

Show the use of the divisibility by $3$3 algorithm to test whether $40356$40356 is divisible by $3$3.

Step 1: $4+0+3+5+6=18$4+0+3+5+6=18

Step 2: $\frac{18}{3}=6$183=6

So yes, the number $40356$40356 is divisible by $3$3.

If that sum, $18$18, had been too large and we still weren't sure whether it was divisible by $3$3, we could add the digits again, giving us $9$9, and look at whether that was divisible by $3$3, which of course it is!

## Divisibility Algorithm for 9

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

Step 1: Add all the digits together

Step 2: If the sum is divisible by $9$9 then the number is also divisible by $9$9.

This is very similar to the algorithm for $3$3, so it's your turn to have a go.

Use the algorithm for the divisibility by $9$9 to determine whether $1111707$1111707 is divisible by $9$9. Check to see if you were writing by using your calculator.

## Divisibility Algorithm for 6

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

Step 1: Test whether the number is divisible by$2$2

Step 2: Test whether the number is divisible by $3$3

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

Again, since we've been through what's required for Step 1 and Step 2, you can have a go and test whether the following two numbers are divisible by 6. You can then check your answer on your calculator.

Is $271926$271926 divisible by $6$6?

Is $487421$487421 divisible by $6$6?

## Divisibility Algorithm for 7

To test whether a number is divisible by $7$7, we apply the following algorithm:

Step 1: Remove the units digit from the number to form two separate numbers.

Step 2: Subtract the units value from the remaining digits twice.

Step 3 (Optional): Repeat steps 1 and 2 until the number is small enough.

Step 4: It the final answer is divisible by $7$7, then the whole number is divisible by $7$7.

##### example

Show the use of the divisibility by $7$7 algorithm to determine whether $38003$38003 is divisible by $7$7.

Let's set out the required steps below.

$3800-2\times3=3794$38002×3=3794

$379-2\times4=371$3792×4=371

$37-2\times1=35$372×1=35

$35$35 is divisible by $7$7 so $38003$38003 is also divisible by $7$7

We could continue on with many other similar algorithms, but you now get a good feel for what these algorithms are like and how you use them. In the question set you'll see a few others that we haven't seen here, so just follow the steps to use them.

#### Worked Examples

##### question 1

Consider the following numbers.

$940,257,8535,486,1923,11705,21735,92872,98941,77990,2327,6644,985,605,8470$940,257,8535,486,1923,11705,21735,92872,98941,77990,2327,6644,985,605,8470

1. List all the numbers that are divisible by $10$10.

Write all the numbers on the same line, separated by commas.

2. List all the numbers that are divisible by $5$5.

Write all the numbers on the same line, separated by commas.

3. List all the numbers that are divisible by $2$2.

Write all the numbers on the same line, separated by commas.

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

Write all the numbers on the same line, separated by commas.

##### Question 2

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

 Step 1: Test whether the number is divisible by $2$2. Step 2: Test whether the number is divisible by $3$3. Step 3: If the number is divisible by both $2$2 and $3$3, then the number is divisible by $6$6.

Consider the number $42765$42765.

1. Is $42765$42765 divisible by $2$2?

Yes

A

No

B

Yes

A

No

B
2. Is $42765$42765 divisible by $3$3?

Yes

A

No

B

Yes

A

No

B
3. Hence, is $42765$42765 divisible by $6$6?

Yes

A

No

B

Yes

A

No

B

##### Question 3

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

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

Step 2: If the sum is a multiple of $9$9, then the number itself is divisible by $9$9.

Use the algorithm to determine whether $354427126389$354427126389 is divisible by $9$9.

1. First find the sum of the digits of $354427126389$354427126389.

2. Hence, is $354427126389$354427126389 divisible by $9$9?

Yes

A

No

B

Yes

A

No

B
3. Does that mean that $354427126389$354427126389 is also divisible by $3$3?

Yes

A

No

B

Yes

A

No

B