Easy explanations for divisibility rules of 2, 3 & 9 with examples in Python.
Table of Contents:
- Divisibility rule of 2
- Divisibility rule of 3
- Divisibility rule of 9
- How is this useful in real life?
Divisibility rule of 2
If the last digit of a number is divisible by 2 (2,4,6,8) or is 0, then the number is divisible by 2.
Proof:
To prove this we have to prove 2 statements: ..0 is divisible by 2 and anything that ends with 2,4,6,8 is divisible by 2.
1..0 is divisible by 2 because any number (10, 100, 1..0) can be rewritten as a multiple of 5 * 2 * 1...0, therefore the only digit that has to be divisible by 2 for the whole number to be divisible by 2 is the last one.
....2 ....4 ....6 ....8 are divisible by 2 because they can be rewritten as:
10 * ..... 2
10 * ..... 4 or 2 * 5 * ..... 2 * 2 or 2 * (5 ..... 2)
10 * ..... 6 or 2 * 5 * ..... 2 * 3 or 2 * (5 ..... 3)
10 * ..... 8 or 2 * 5 * ..... 2 * 4 or 2 * (5 ..... 4)
Divisibility rule of 3
The rule: a number can be divided by 3 if the sum of its digits can be divided by 3. (note that for very large numbers we can apply this rule to the sum, and the sum of the digits in the resulting sum etc. to make things easier for us until we hit a sum less than 10 like in the following funciton:
A function which returns True if a number is divisible by 3 without division
def is_divisible_by_three(n):
while n > 9:
n = sum([int(x) for x in str(n)])
if n in [3,6,9]:
return True
if n in [0,1,2,4,5,7,8]: # Just for explicity, can be a simple "else:"
return FalseProof of divisibility rule of 3 using an example - Is 6634924455946276495517515014 divisible by 3?
Let's find out if 6634924455946276495517515014 is divisible by 3 The number 6634924455946276495517515014 is a sum of the following: 4 * 1 1 * 10 0 * 100 5 * 1000 1 * 10000 5 * 100000 7 * 1000000 1 * 10000000 5 * 100000000 5 * 1000000000 9 * 10000000000 4 * 100000000000 6 * 1000000000000 7 * 10000000000000 2 * 100000000000000 6 * 1000000000000000 4 * 10000000000000000 9 * 100000000000000000 5 * 1000000000000000000 5 * 10000000000000000000 4 * 100000000000000000000 4 * 1000000000000000000000 2 * 10000000000000000000000 9 * 100000000000000000000000 4 * 1000000000000000000000000 3 * 10000000000000000000000000 6 * 100000000000000000000000000 6 * 1000000000000000000000000000 Now using this pattern: 10 = 3 * 3 + 1 100 = 33 * 3 + 1 1000 = 333 * 3 + 1 etc. (Every 10..0 is equal to 3..3 * 3 + 1) We can rewrite our initial number 6634924455946276495517515014 as a sum of the following: 4 * (1 + 0 * 3) 1 * (1 + 3 * 3) 0 * (1 + 33 * 3) 5 * (1 + 333 * 3) 1 * (1 + 3333 * 3) 5 * (1 + 33333 * 3) 7 * (1 + 333333 * 3) 1 * (1 + 3333333 * 3) 5 * (1 + 33333333 * 3) 5 * (1 + 333333333 * 3) 9 * (1 + 3333333333 * 3) 4 * (1 + 33333333333 * 3) 6 * (1 + 333333333333 * 3) 7 * (1 + 3333333333333 * 3) 2 * (1 + 33333333333333 * 3) 6 * (1 + 333333333333333 * 3) 4 * (1 + 3333333333333333 * 3) 9 * (1 + 33333333333333333 * 3) 5 * (1 + 333333333333333333 * 3) 5 * (1 + 3333333333333333333 * 3) 4 * (1 + 33333333333333333333 * 3) 4 * (1 + 333333333333333333333 * 3) 2 * (1 + 3333333333333333333333 * 3) 9 * (1 + 33333333333333333333333 * 3) 4 * (1 + 333333333333333333333333 * 3) 3 * (1 + 3333333333333333333333333 * 3) 6 * (1 + 33333333333333333333333333 * 3) 6 * (1 + 333333333333333333333333333 * 3) Let's open the brackets ( a * (b + c) = a*b + a*c ): 4 + 4 * 0 * 3 1 + 1 * 3 * 3 0 + 0 * 33 * 3 5 + 5 * 333 * 3 1 + 1 * 3333 * 3 5 + 5 * 33333 * 3 7 + 7 * 333333 * 3 1 + 1 * 3333333 * 3 5 + 5 * 33333333 * 3 5 + 5 * 333333333 * 3 9 + 9 * 3333333333 * 3 4 + 4 * 33333333333 * 3 6 + 6 * 333333333333 * 3 7 + 7 * 3333333333333 * 3 2 + 2 * 33333333333333 * 3 6 + 6 * 333333333333333 * 3 4 + 4 * 3333333333333333 * 3 9 + 9 * 33333333333333333 * 3 5 + 5 * 333333333333333333 * 3 5 + 5 * 3333333333333333333 * 3 4 + 4 * 33333333333333333333 * 3 4 + 4 * 333333333333333333333 * 3 2 + 2 * 3333333333333333333333 * 3 9 + 9 * 33333333333333333333333 * 3 4 + 4 * 333333333333333333333333 * 3 3 + 3 * 3333333333333333333333333 * 3 6 + 6 * 33333333333333333333333333 * 3 6 + 6 * 333333333333333333333333333 * 3 Everything after the + sign is divisible by 3 So the task boils down to checking whether the sum of numbers to the left of the + sign is divisible by 3 Which is sum of the digits of our initial number: 6 6 3 4 9 2 4 4 5 5 9 4 6 2 7 6 4 9 5 5 1 7 5 1 5 0 1 4 So we find it: 6 + 6 + 3 + 4 + 9 + 2 + 4 + 4 + 5 + 5 + 9 + 4 + 6 + 2 + 7 + 6 + 4 + 9 + 5 + 5 + 1 + 7 + 5 + 1 + 5 + 0 + 1 + 4 = 129 If the sum seems big we can repeat the process for it as many times as we want We can recursively ask the same question whether the number is divisible by 3: So, is 129 divisible by 3? Yes if the sum of its digits is divisible by 3 as we figured out earlier The sum of digits of 129 is 12 So, is 12 divisible by 3? Yes if the sum of its digits is divisible by 3 as we figured out earlier The sum of digits of 12 is 3 3 is divisible by 3, so 6634924455946276495517515014 is divisible by 3
And this proof can be generated using this code:
import random
# A number is divisible by 3 if sum of the digits is divisible by 3
a, b = 100000000000000000, 10000000000000000000000000000
n = random.randint(a,b)
print("Let's find out if", str(n), "is divisible by 3\n")
print("The number", str(n),"is a sum of the following:")
for i, d in enumerate(map(str, reversed(str(n)))):
print(d + " * 1" + i * "0")
print("\nNow using this:\n10 = 3 * 3 + 1\n100 = 33 * 3 + 1\n1000 = 333 * 3 + 1 etc.\n(Every 10..0 is equal to 3..3 * 3 + 1)")
print("\nWe can rewrite our initial number "+str(n)+" as a sum of the following:")
for i, d in enumerate(reversed(str(n))):
z = "0" if i == 0 else ""
print(d + " * (1 + " + "3" * i + z + " * 3)")
print("\nLet's open the brackets ( a * (b + c) = a*b + a*c ):")
for i, d in enumerate(map(str, reversed(str(n)))):
z = "0" if i == 0 else ""
print(d + " + " + d + " * " + "3" * i + z + " * 3")
print("\nEverything after the + sign is divisible by 3")
print("\nSo the task boils down to checking whether the sum of numbers to the left of the + sign is divisible by 3")
print("\nWhich is sum of the digits of our initial number:", " ".join(list(str(n))))
digits = [int(x) for x in str(n)]
s = sum(digits)
print("\nSo we find it:", " + ".join(list(str(n))), "=", str(s))
print("\nIf the sum seems big we can repeat the process for it as many times as we want\n\nWe can recursively ask the same question whether the number is divisible by 3):")
print("\n")
while s > 9:
print("So, is ",s, " divisible by 3?\nYes if the sum of its digits is divisible by 3 as we figured out earlier")
digits = [int(x) for x in str(s)]
prev_s = s
s = sum(digits)
print("\nThe sum of digits of ", prev_s, "is", s, "\n" )
if s % 3 == 0:
print(s, "is divisible by 3, so ",n,"is divisible by 3")
else:
print(s, "is not divisible by 3")Divisibility rule of 9
The proof of the divisibility rule of 9 is exactly the same as for the 3, except for one thing:
We use this pattern to substitute 10...0s:
10 = 9 + 1 100 = 11 * 9 + 1 1000 = 111 * 9 + 1 etc. (Every 10..0 is equal to 1..1 * 9 + 1)
Everything else is exactly the same as in the divisibility rule of 3:
Proof of divisibility rule of 9 using an example - Is 6241920510332348610799520496 divisible by 9?
Let's find out if 6241920510332348610799520496 is divisible by 9 The number 6241920510332348610799520496 is a sum of the following: 6 * 1 9 * 10 4 * 100 0 * 1000 2 * 10000 5 * 100000 9 * 1000000 9 * 10000000 7 * 100000000 0 * 1000000000 1 * 10000000000 6 * 100000000000 8 * 1000000000000 4 * 10000000000000 3 * 100000000000000 2 * 1000000000000000 3 * 10000000000000000 3 * 100000000000000000 0 * 1000000000000000000 1 * 10000000000000000000 5 * 100000000000000000000 0 * 1000000000000000000000 2 * 10000000000000000000000 9 * 100000000000000000000000 1 * 1000000000000000000000000 4 * 10000000000000000000000000 2 * 100000000000000000000000000 6 * 1000000000000000000000000000 Now using this: 10 = 9 + 1 100 = 11 * 9 + 1 1000 = 111 * 9 + 1 etc. (Every 10..0 is equal to 1..1 * 9 + 1) We can rewrite our initial number 6241920510332348610799520496 as a sum of the following: 6 * (1 + 0 * 9) 9 * (1 + 1 * 9) 4 * (1 + 11 * 9) 0 * (1 + 111 * 9) 2 * (1 + 1111 * 9) 5 * (1 + 11111 * 9) 9 * (1 + 111111 * 9) 9 * (1 + 1111111 * 9) 7 * (1 + 11111111 * 9) 0 * (1 + 111111111 * 9) 1 * (1 + 1111111111 * 9) 6 * (1 + 11111111111 * 9) 8 * (1 + 111111111111 * 9) 4 * (1 + 1111111111111 * 9) 3 * (1 + 11111111111111 * 9) 2 * (1 + 111111111111111 * 9) 3 * (1 + 1111111111111111 * 9) 3 * (1 + 11111111111111111 * 9) 0 * (1 + 111111111111111111 * 9) 1 * (1 + 1111111111111111111 * 9) 5 * (1 + 11111111111111111111 * 9) 0 * (1 + 111111111111111111111 * 9) 2 * (1 + 1111111111111111111111 * 9) 9 * (1 + 11111111111111111111111 * 9) 1 * (1 + 111111111111111111111111 * 9) 4 * (1 + 1111111111111111111111111 * 9) 2 * (1 + 11111111111111111111111111 * 9) 6 * (1 + 111111111111111111111111111 * 9) Let's open the brackets ( a * (b + c) = a*b + a*c ): 6 + 6 * 0 * 9 9 + 9 * 1 * 9 4 + 4 * 11 * 9 0 + 0 * 111 * 9 2 + 2 * 1111 * 9 5 + 5 * 11111 * 9 9 + 9 * 111111 * 9 9 + 9 * 1111111 * 9 7 + 7 * 11111111 * 9 0 + 0 * 111111111 * 9 1 + 1 * 1111111111 * 9 6 + 6 * 11111111111 * 9 8 + 8 * 111111111111 * 9 4 + 4 * 1111111111111 * 9 3 + 3 * 11111111111111 * 9 2 + 2 * 111111111111111 * 9 3 + 3 * 1111111111111111 * 9 3 + 3 * 11111111111111111 * 9 0 + 0 * 111111111111111111 * 9 1 + 1 * 1111111111111111111 * 9 5 + 5 * 11111111111111111111 * 9 0 + 0 * 111111111111111111111 * 9 2 + 2 * 1111111111111111111111 * 9 9 + 9 * 11111111111111111111111 * 9 1 + 1 * 111111111111111111111111 * 9 4 + 4 * 1111111111111111111111111 * 9 2 + 2 * 11111111111111111111111111 * 9 6 + 6 * 111111111111111111111111111 * 9 Everything after the + sign is divisible by 9 So the task boils down to checking whether the sum of numbers to the left of the + sign is divisible by 9 Which is sum of the digits of our initial number: 6 2 4 1 9 2 0 5 1 0 3 3 2 3 4 8 6 1 0 7 9 9 5 2 0 4 9 6 So we find it: 6 + 2 + 4 + 1 + 9 + 2 + 0 + 5 + 1 + 0 + 3 + 3 + 2 + 3 + 4 + 8 + 6 + 1 + 0 + 7 + 9 + 9 + 5 + 2 + 0 + 4 + 9 + 6 = 111 If the sum seems big we can repeat the process for it as many times as we want We can recursively ask the same question whether the number is divisible by 9): So, is 111 divisible by 9? Yes if the sum of its digits is divisible by 9 as we figured out earlier The sum of digits of 111 is 3 3 is not divisible by 9, so 6241920510332348610799520496 is not divisible by 9
The code for this:
import random
a, b = 100000000000000000, 10000000000000000000000000000
n = random.randint(a,b)
print("Let's find out if", str(n), "is divisible by 9\n")
print("The number", str(n),"is a sum of the following:")
for i, d in enumerate(reversed(str(n))):
print(d + " * 1" + i * "0")
print("\nNow using this:\n10 = 9 + 1\n100 = 11 * 9 + 1\n1000 = 111 * 9 + 1 etc.\n(Every 10..0 is equal to 1..1 * 9 + 1)")
print("\nWe can rewrite our initial number "+str(n)+" as a sum of the following:")
for i, d in enumerate(reversed(str(n))):
z = "0" if i == 0 else ""
print(d + " * (1 + " + "1" * i + z + " * 9)")
print("\nLet's open the brackets ( a * (b + c) = a*b + a*c ):")
for i, d in enumerate(map(str, reversed(str(n)))):
z = "0" if i == 0 else ""
print(d + " + " + d + " * " + "1" * i + z + " * 9")
print("\nEverything after the + sign is divisible by 9")
print("\nSo the task boils down to checking whether the sum of numbers to the left of the + sign is divisible by 9")
print("\nWhich is sum of the digits of our initial number:", " ".join(list(str(n))))
digits = [int(x) for x in str(n)]
s = sum(digits)
print("\nSo we find it:", " + ".join(list(str(n))), "=", str(s))
print("\nIf the sum seems big we can repeat the process for it as many times as we want\n\nWe can recursively ask the same question whether the number is divisible by 9):")
print("\n")
while s > 9:
print("So, is ",s, " divisible by 9?\nYes if the sum of its digits is divisible by 9 as we figured out earlier")
digits = [int(x) for x in str(s)]
prev_s = s
s = sum(digits)
print("\nThe sum of digits of ", prev_s, "is", s, "\n" )
if s % 9 == 0:
print(s, "is divisible by 9, so ",n,"is divisible by 9")
else:
print(s, "is not divisible by 9, so ",n,"is not divisible by 9")
A short function which returns True if a number is divisible by 9
def divisible_by_nine(n):
while n > 9:
n = sum([int(x) for x in str(n)])
return True if n == 9 else FalseHow is this useful in real life?
Hardware does not like the division operation. It is much heavier on the processor and memory than addition/subtraction and multiplication. This algorithm uses basic math logic and allows to find out if we can divide any number by 3 without actual division using several simple addition operations instead.
On servers which have to run billions of operations per second knowing this rule can save energy required for the computations and lower the usage of server resources (memory, network etc.) by using this algorithm for checking whether a number is a multiple of 3 instead of straightforward division by 3 and checking if the result has a remainder.
# Other ways to do this in Python:
n % 3 == 0 # returns True if the remainder of n / 3 is 0
# Exotic way using division :) (DO NOT DO THIS)
d = n / 3
float(d) == int(d)