More Stuff That is “Easier Than You Think”

A couple of days ago, I mentioned that I had been shown how to test divisibility by seven, and by using the same method, I could develop a similar approach for any of the small (but difficult primes).. So today I want to show you how that works, and if you read carefully, you will be able to mentally determine if any number is prime up to 9000 ....go ahead, impress yourself.

first, how the seven rule works…. I’m going to talk about what big people call modular congruence, but don’t let that scare you. It just means that two numbers have the same remainder when divided by some specific quantity (in the first case, seven). So 9, 16, 23, etc are all congruent mod seven because they all have a remainder of 2 when we divide them by seven… see…easy..and if they are congruent to zero mod seven, that means they have no remainder…they are divisible by seven

Now a rule that should make sense if you think about it; is that any two numbers that have a congruence of zero, when added together will have a sum that is congruent to zero… In mod seven we could think of 14 and 21. Both are divisible by seven, so if we add then together we get another number divisible by seven. I know it is hard to believe you can come up with much from such a simple rule, but watch.

Lets think of some number n, and for a moment let us break it into two parts, the number made up of all the digits except the units digit, call that one A, and the units digit, call it B. Then N = 10A + B… As an example with 324 we would say A is 32 and B is 4 so 324 = 10( A) + B…. got it?

Now we don’t know if N is divisible by seven, but we notice that if we take 2 times N it will equal 20 A + 2B…. yeah, I hear you saying “So, what?”… patience. Now 20 A is equal to 21 A – A…. you know that… so we can write 2N =20 A + 2B = 21 A – A + 2B. NOW, we have something, because 21 A is divisible by 7, and so if –A+2B is divisible by seven, then N must be also by the rule above in italics. Now it doesn’t matter if –A+2B is positive or negative, so since A may be a multi-digit number it would be easier to do A-2B. So we want to know if 2947 is divisible by seven (it is). We take 294 (A) and subtract 2 x 7 and get 280. Still a big number so we can do it again. 28 – 2x0= 28…and HEY, I know that is divisible by 7, so the original number, 2947 must be.

Ok, can we make that trick work for other primes. We can skip 11 because it already has an easy divisibility rule… (see casting out nines and elevens). What about 13? Well 3x13 is 39, which is almost 40. That is the secret of these prime tests; we want a multiple that is one more or one less than an even multiple of ten (one less is easier as we will see, no subtraction). So we go back to N=10A + B, and we want to know if it is divisible by 13… Well, set 4N = 40 A + 4B and that is the same as 39A + A + 4B. Now the 39A is a multiple of 13, so if the A+4B is a multiple of 13, then 4N, and hence N is a multiple of 13. So we just use the rule A+4B to test a number…. Like 403. 40 + 4x3 = 52… and if you didn’t recognize that as a multiple of 13, you could do 52 as 5 + 4(2) = 13..hey, we ALL recognize that is divisible by 13.

Here are some tests for other primes I worked out by the same approach, and they are pretty easy to remember by just two rules of thumb. Find a multiple of the prime that is one more or one less than a multiple of ten. If it is one more then you have to subtract some multiple of B from A, and if it is one less, then you add some multiple of B to A. And the multiple of B, it is just the number of tens that we are one more or one less than (don’t get confused, it is NOT how many times we multiply the prime to get there). Try making sense of how these were done, then you can make your own for even higher primes (although they start to have some big multiples, but 39 should be an easy one)…

Test 7 by using A- 2B
Test 13 by using A + 4B
Test 17 by using A- 5B
Test 19 by using A+2B (see, it is already just one less than twenty)
Test 23 by using A+ 7B (OK, that is the hardest one in the group, sorry)
and test 29 (one less than 30) by using A+3B.

Any number less than 9000 must have a prime factor less than 30 if it is not prime, since 30² = 9000, so if you come across some big number like 8531 and wonder if it is prime, just try the rules one at a time.

3 sevens is 21 one more than two tens so the rule is A-2B… 853-2=851… 85-2 = 83 and 7 won’t go into that evenly so it is NOT divisible by 7.

Not divisible by 11 so we try 13, 3x13 = 39 which is one less than 40, so we add A + 4B… 853+4 = 857… 85+4(7)= 109… 10 + 4(9) = 46…nope, 13 won’t go into that… on to 17

3 x 17 is 51 so we need to subtract A – 5B…… 853-5(1) = 848… 84-5(8)= 44, nope 17 won’t go into 44 evenly… let’s try 19.

19 is already one less than 20 so we test with A + 2B… 8531.... 853+2(1)= 855 .... 85+2(5)= 95 ... 9+2(5) = 19…hey, it is divisible 19, and in fact, 8531 = 19 x 449. ….”easy peasy” as the British folk say.