Waste less time on Facebook — follow Brilliant.
×

Divisibility Rules

When learning about multiples and divisors, there are several rules of divisibility that a student may encounter. Below, we list some famous rules of divisibility:

When dividing by...

2: The last digit is even.

3: The sum of digits is a multiple of 3.

4: The last 2 numbers are a multiple of 4.

5: The last digit is either 0 or 5.

6: Multiple of 2 and 3

8: The last 3 digits are a multiple of 8.

9: The sum of digits is a multiple of 9.

10: The last digit is 0.

11: The alternating sum of digits is a multiple of 11.

We will show the proofs of rules of 8 and 11. The rest follow in a similar manner.

Proof: When a number is divisible by 8, the last 3 digits are a multiple of 8.

Let the number be \( N= 1000M + 100a + 10b + c\), where \( a, b, c\) are digits and \( M\) is a non-negative integer.

Clearly, \( 1000M\) is a multiple of 8, since \( 8 \mid 2^3 \cdot 5^3\). Hence, \( N\) is a multiple of 8 if and only if \( 100a + 10b + c\) is a multiple of 8.

Proof: When a number is divisible by 11, the alternating sum of digits is a multiple of 11.

From Factorization , we know that

\( 10^n - (-1)^n = (10 - (-1) ) ( 10^{n-1} + 10^{n-2}(-1) + \ldots + (-1)^{n-1} )\)

is always a multiple of 11.

Hence, if \( N = 10^k a_k + 10^{k-1} a_{k-1} + \ldots + 10 a_1 + a_0\), then

\( \begin{aligned}
N & = [ (10^k - (-1)^k) a_k + ( 10^{k-1} - (-1)^{k-1}) a_{k-1} + \ldots + (10+1)a_1 + (1-1)a_0 ]\\
& \quad + (-1)^k a_k + (-1)^{k-1}a_{k-1} + \ldots + (-1)^1 a_1 + (-1)^0 a_0
\end{aligned} \)

Since the terms in the square brackets consist of multiples of 11, it follows that \( N\) is a multiple of 11 if and only if the alternating sum is a multiple of 11.

Application and Extentions

Find all possible values of \( a\) such that the number \( \overline{98a6}\) is a multiple of 3.

From the rules of divisibility, the number \( \overline{98a6}\) is a multiple of 3 if and only if the sum of the digits \( 9 + 8 + a + 6 = 23+a\) is a multiple of 3. Since \( 0 \leq a \leq 9\), this implies that \( a = 1, 4, 7\) are all the possible values.

 

Show that if the last 3 digits of a number \( N\) are \( \overline{abc}\), then \( N\) is a multiple of 8 if and only if \( 4a + 2b + c\) is a multiple of 8.

This follows because \( 100a + 10 b + c = 8 (12a + b) + 4a + 2b + c\). Hence, by the divisibility rule of 8, \( N\) is a multiple of 8 if and only if \( \overline{abc} \) is a multiple of 8 if and only if \( 4a+2b+c\) is a multiple of 8.

 

Divisibility rule of 7: Break up the number into blocks of 6, starting from the right. Add up all these blocks, and the resultant number has to be a multiple of 7.

This follows because \( 10^6 -1 = 999999 = 142857 \times 7\), so \( 10^{6k}M_k + 10^{6(k-1)}M_{k-1} + \ldots + 10^6 M_1 + M_0\) is a multiple of 7 if and only if \( M_k + M_{k-1} + \ldots + M_0\) is a multiple of 7. If we use \( 0 \leq M_i \leq 999999\), we get the result as stated.

Show that the 6 digit number \( \overline{abcdef}\) is a multiple of 7 if and only if \( 5a + 4b + 6c + 2d + 3b + f\) is a multiple of 7.

Solution: This follows because \( \begin{aligned} &1 & = &0 \times 7 & + 1\\ &10 & = &1 \times 7 & + 3\\\ & 100 & =& 14 \times 7 & + 2\\ &1000 & = &142 \times 7 &+ 6\\ &10000 & = &1428 \times 7 &+ 4 \\ &100000& = &14285 \times 7 &+ 5.\\ \end{aligned} \)

Hence \( \overline{abcdef}\) is a multiple of 7 if and only if \( 5a + 4b + 6c + 2s + 3e + f\) is a multiple of 7.

Note by Arron Kau
3 years, 6 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Divisibility by 3: given a number in base 10 can be rewritten as:

\((a_n10^n)+(a_{n-1}10^{n-1})+(a_{n-2}10^{n-2})+...+a_1\)

We know that \(10\equiv{1(\mod{3})}\) So if we want to see if the above integer is divisible by 3, we can rewrite the integer reduced by modulo 3:

\((a_n10^n)+(a_{n-1}10^{n-1})+(a_{n-2}10^{n-2})+...+a_1\equiv{((a_n)+(a_{n-1})+(a_{n-2})+...+a_1)(\mod{3})}\)

So we will have to find the sum of the digits. QED William Isoroku · 1 year, 7 months ago

Log in to reply

For eight, I just like to use the fact that a number \(\overline {...abc} \) is a multiple of eight if

(1) \(a\) is odd, and \(\overline {bc} \) is a multiple of four, but NOT eight, (\(\overline{bc} \equiv 4 \pmod{8}\)

OR

(2) when \(a\) is even, and \(\overline {bc}\) is a multiple of eight.

This can be proved relatively simply using mod math. I find it very useful, because you need only to remember 2-digit multiples of 8 instead of 3-digit ones! Nicolas Bryenton · 3 years, 1 month ago

Log in to reply

@Nicolas Bryenton No!not at all.You have to only look at the last 3 digits. I don't know how did you found that you have to only look at the last 2 digits. Anuj Shikarkhane · 3 years, 1 month ago

Log in to reply

@Anuj Shikarkhane I'm sorry but did you even read what I wrote 0_0

My method tells you if the last three digits are a multiple of eight, but without having to memorize all three digit multiples of 8. If you read it more carefully, it should make sense, because it indeed does make sense. Nicolas Bryenton · 3 years, 1 month ago

Log in to reply

@Nicolas Bryenton I don't think so. Anuj Shikarkhane · 3 years, 1 month ago

Log in to reply

@Anuj Shikarkhane Here is a proof I wrote. Nicolas Bryenton · 3 years, 1 month ago

Log in to reply

Also, I would like to add that if a number is divisible by 11 then the alternating sum of its digits is itself divisible by 11. E.g 92818..... 9-2+8-1+8 = 22 and 11|22. Also, for 7 you take off the last digit of a number and subtract twice that number from the original. If the result is divisible by 7 then the original number is also divisible by 7 E.g. 259... 25 - 2(9) = 7 & 7|7 Curtis Clement · 2 years, 10 months ago

Log in to reply

Thanks for this Anuj Shikarkhane · 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...