Divisibility
From charlesreid1
Tricks
Tricks and shortcuts for testing divisibility:
Divisibility by 2
We know that if the last digit in a number is divisible by 2, the entire number is divisible by 2. This stems from the fact that 2 divides 10 perfectly. Thus, every number can be split into a two components: the first component is an integer multiple of 10, the second component is the last digit of the number.
Example: 416
416 = 41 * 10 + 6
We know 2 will divide 41 * 10 perfectly, because 2 divides 10. Thus, the only question remaining is whether 2 divides the last digit, 6, which it does. So, 2 divides 416.
Divisibility by 3
We know that if the digit sum of a number is divisible by 3, the number itself is divisible by 3. If the sum of the digits forms a large number, its digits can be added together in a like fashion.
Example: 15,230,127
15,230,127 => 1 + 5 + 2 + 3 + 0 + 1 + 2 + 7 = 21 21 => 2 + 1 => 3
The sum of the digits is 3, therefore 3 divides 15,230,127.
Divisibility by 4
If the last two digits of a number are divisible by 4, the entire number is divisible by 4. The mechanism for this is similar to the mechanism for the divisibility tests for 2 and for 5. Because 4 divides 100 perfectly, any number can be split into its hundreds and greater component, and its tens and ones digits. 4 will evenly divide the hundreds and greater component, since it perfectly divides 100. The only remaining thing to determine is whether 4 divides the last 2 digits.
Divisibility by 5
If a number ends in 0 or 5, it is divisible by 5. This is due to the fact that 5 divides 10 perfectly, like 2, so any number can be split into its ones value (which 5 may or may not divide) and everything else (which 5 will divide).
Divisibility by 9
We know that if the digit sum of a number is divisible by 9, the number itself is divisible by 9.
Divisibility by 11
To test for divisibility by 11:
- Add the numbers in the even positions (second, fourth, and so on).
- Add the digits in the odd positions (first, third, and so on)
- If the difference between the sums is 0 or a multiple of 11, the number is divisible by 11.
- Otherwise, it is not a multiple of 11.
Example: 181,182,375
181,182,375 => (1+1+8+3+5) - (8+1+2+7) = 18 - 18 = 0
Therefore, 181,182,375 is divisible by 11.
Proof/Explanation
This introduces the term modulus - similar to remainder. 18 has a remainder of 7 when divided by 11, and 18 = 7 mod 11.
The digits 0, 1, 2, 3, ..., 9 are, of course, 0, 1, 2, ..., 9 mod 11
0, 10, 20, ..., 90 are, by actual division, 0, 10, 9, ..., 2 mod 11 = 0, -1, -2, ..., -9 mod 11
0, 100, 200, ... 900 are again 0, 1, 2, ..., 9 mod 11 and so on
The sum of two given numbers has the same modulus as the sum of the moduli of the numbers. For a given number N:
N = a + 10 b + 100 c + 1000 d + ...
Now expressing that mod 11:
N mod 11 = a mod 11 + 10 b mod 11 + 100 c mod 11 + 1000 d mod 11 + ... = a mod 11 - b mod 11 + c mod 11 - d mod 11 + ... = a mod 11 + c mod 11 + ... - ( b mod 11 + d mod 11 + ... )
Since a, b, c, d, are the digits of N, starting from right to left, the test must be correct.
Divisibility by 7, 11, 13
7, 11, and 13 are 3 consecutive prime numbers. Their product is 1001, and when a product is that close to a power oof 10, a test of divisibility is not far away.
The test is: separate the number from right to left in groups of 3 digits (the commas conventionally printed in a number do this for you.) Add teh groups in even positions and the groups in odd positions. If the difference between the sums is divisible by 7, 11, or 13, the entire number is divisible by 7, 11, or 13, respectively. If the difference is 0, the number is divisible by 7, 11, and 13.
Example: 42,623,295
42,623,295 => ( 623 ) - ( 42 + 295 ) = 286
Now, 286 is divisible by 11 and 13 both, but is not divisible by 7.
Thus, 42,623,295 is divisible by 11 and 13, but not by 7.
Note: 1,000 = 10^3 + 1, and this is a factor of 10^6-1 and 10^9+1. Using these facts, can you demonstrate that the test works on numbers which separate into four groups?
Can you demonstrate the test in general, on your own, two different ways? One can be based on the solution to the problem just shown. The other can be based on the division by 11 trick (mod 11, except use mod 1001 instead of mod 11).