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 7
The Russian people like the number 7... Folk songs and proverbs:
- Measure cloth seven times before you cut it
- Seven misfortunes, one reckoning
- ONe plows, seven come along with spoons
- A baby had seven nurses, but lost his eye
We know two kinds of tests of divisibility by 7, in conjunction with other numbers (3/7/19 and 7/11/13).
Test A
Here is another test:
Multiply the first digit on the left by 3 and add the second digit. Multiply by 3 and add the third digit, and so on, until you ad the last digit. If the last digit is divisible by 7, the entire number is divisible by 7.
To simplify your calculations, reduce each multiplication result modulo 7.
Example: 48,916
48,916 Multiply by 3: 4 * 3 = 12 mod 7 = 5 mod 7 Add next digit: 5 + 8 = 13 mod 7 = 6 mod 7 Multiply by 3: 6 * 3 = 18 mod 7 = 4 mod 7 Add next digit: 4 + 9 = 13 mod 7 = 6 mod 7 6 * 3 = 18 mod 7 = 4 mod 7 4 + 1 = 5 5 * 3 = 15 mod 7 = 1 mod 7 1 + 6 = 7
The last number is 7, therefore 48,916 is divisible by 7.
To prove the validity of the test, we can take a given number, N, and represent it as follows:
N = a + 10 b + (10^2) c + (10^3) d + ...
What we want to do is determine if this number is divisible by 7. If we can remove known factors of 7 from this representation, we can reduce the problem - this is similar in principle to the divisibility check with 2 and 4, where the 10s or 100s place can be removed because it is a known factor of 2 or 4.
Again, the principle of modular arithmetic is showing up; if we want to check whether 15 is divisible by 7, we can say, "break 15 into a portion that is known to be divisible by 7, that is, 14, and the remainder, that is, 1". Decomposing 15 = 14 + 1, we can then say that 14 = 0 mod 7, and drop the 14 portion, and the divisibility check becomes "does 7 divide 1 perfectly?" which it does not. Therefore 15 does not divide 7.
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 3, 7, and 19
The product of the prime numbers 3, 7, and 19 is 399. If a number 100a + b (where b is a two-digit number and a is any positive integer) is divisible by 399 or by any of its divisors, then a + 4b is divisible by this same number.
On your own, can you prove this? (Hint: use 400a + 4b as a link.) Can you formulate and prove its converse?
Devise a simple test of divisibility by 3, 7, and 19.
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).