Coding and Algorithms

Ontario 09 Academic (MPM1D)

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.

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.

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

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?

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.”

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.

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.

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.

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!

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.

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?

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.

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$3800−2×3=3794

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

$37-2\times1=35$37−2×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.

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

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

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

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

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

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

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

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.

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.

Is $42765$42765 divisible by $2$2?

Yes

ANo

BYes

ANo

BIs $42765$42765 divisible by $3$3?

Yes

ANo

BYes

ANo

BHence, is $42765$42765 divisible by $6$6?

Yes

ANo

BYes

ANo

B

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.

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

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

Yes

ANo

BYes

ANo

BDoes that mean that $354427126389$354427126389 is also divisible by $3$3?

Yes

ANo

BYes

ANo

B