So while I was taking a lecture on Primes and discussing Number Theory, we took a different route and ended up discussing divisibility rules,
and jokingly told the students that the divisibility rule of 59 is, you take the last digit multiply it by 6 and add it to remaining part, if you repeat this until
you get a small or a trivial multiple of 59, then the number we started with is also divisible by 59. I told them divisibility rules of 61, 489, and 509.
However a question remained. Where did these rules come from? How do we stumble upon them in the first place, and how did I figure out the rules so quickly?
So, I tried to figure out a way to find these rules, and surprisingly the way was too easy to notice!
Let us first try to derive a divisibility rule for 59, note that this number is ending with 9, this would help us later in our conquest.
Say we start by saying that, let \(N = a_1a_2...a_{n+1}\) be any arbitrary natural number which happens to be a multiple of 59, and \(a_1, a_2, ..., a_{n+1}\) are \(n+1\) digits of \(N\)
So, \(N \equiv 0 \mod 59\)
\(\implies N + 59*a_{n+1} \equiv 0 \mod 59\)
\(\implies 10^{n}a_1 + 10^{n-1}a_2 + ... + 10a_n + a_{n+1} + 59a_{n+1} \equiv 0 \mod 59\)
\(\implies 10^{n}a_1 + 10^{n-1}a_2 + ... + 10a_n + 60a_{n+1} \equiv 0 \mod 59\)
\(\implies 10^{n-1}a_1 + 10^{n-2}a_2 + ... + a_n + 6a_{n+1} \equiv 0 \mod 59\)
Or in other words, if \(N\) is divisible by 59, then so is the number obtained, when the last digit of \(N\) is multiplied by 6
and then adding it to the remaining part.
Similar method would help with finding divisibility rule of say 509, and basically any number ending with 9.
But why were we able to do this? One thing is, while finding the rule for 59, the number, 59 actually ends with 9, so when we
add 59*{last digit of N} to \(N\), then we basically obtain a factor of 10 throughout, and since \(10, 59\) are coprime, we can cancel the factor and say
the resulting number is still a multiple of 59.
Let us now try the number 61,
So let \(N = a_1a_2...a_{n+1}\) be any arbitrary natural number which again happens to be a multiple of 61, and \(a_1, a_2, ..., a_{n+1}\) are \(n+1\) digits of \(N\)
So, \(N \equiv 0 \mod 61\)
\(\implies N - 61*a_{n+1} \equiv 0 \mod 61\)
\(\implies 10^{n}a_1 + 10^{n-1}a_2 + ... + 10a_n - 60a_{n+1} \equiv 0 \mod 61\)
\(\implies 10^{n-1}a_1 + 10^{n-2}a_2 + ... + a_n - 6a_{n+1} \equiv 0 \mod 61\)
Or basically, if you subtract six times the last digit of N from the remaining part of N, the resulting number will again be a multiple of 61,
do this enough times to reach a trivial multiple of 61, to conclude that N, the starting number, was in fact, a multiple of 61.
Okay, great! But what about numbers that end with 3, 7? I mean for finding divisibility rule of a number \(X\) say, ending with 1, we subtract the {last digit} times \(X\) and when \(X\) ends with 9
we add the {last digit} times \(X\), so that in either cases, we obtain a factor of 10 from each term, and then we cancel it to finally obtain the divisibility rule of \(X\).
Let us now try to find divisibility rule for 67,
Now this time, what we will do is, we know that 201 is actually a multiple of 67 ending with 1, this would come handy later.
Let \(N = a_1a_2...a_{n+1}\) be any arbitrary natural number which happens to be a multiple of 67, and \(a_1, a_2, ..., a_{n+1}\) are \(n+1\) digits of \(N\)
So, \(N \equiv 0 \mod 67\)
\(\implies N - 201 * a_{n+1} \equiv 0 \mod 67\)
\(\implies 10^{n}a_1 + 10^{n-1}a_2 + ... + 10a_n - 200a_{n+1} \equiv 0 \mod 67\)
\(\implies 10^{n-1}a_1 + 10^{n-2}a_2 + ... + a_n - 20a_{n+1} \equiv 0 \mod 67\)
Or in other words, a number if it is divisible by 67, then take out the last digit and multiply it by 20, and subtract it from the remaining part of the number,
the number so obtained again happens to divisible by 67, and so you do it enough times and make the result more smaller, until a trivial multiple of 67 is reached.
However, we can also obtain another rule of divisbility by 67, note that, \(67*7 = 469\).
\(\implies N + 469 * a_{n+1} \equiv 0 \mod 67\)
\(\implies 10^{n}a_1 + 10^{n-1}a_2 + ... + 10a_n + 470a_{n+1} \equiv 0 \mod 67\)
\(\implies 10^{n-1}a_1 + 10^{n-2}a_2 + ... + a_n + 47a_{n+1} \equiv 0 \mod 67\)
Or we can establish the following rule that, a number is divisible by 67, when the last digit when multiplied by 47
and added to the remaining part, make the new result a multiple of 67.
Great so we can figure out divisibility rules of basically any prime number, and we also now know how to find the divisibility rules
when the numbers end with 3, or 7, just try to find a multiple that ends with 1 or 9, and rest is easy!
I will now present the divisibility rules of all primes above \(6\) and below \(100\):
Since all the rules involve multiplying the last digit by a number, and then either adding or subtracting that from remaining part, I will just mention the multiplying number
and the operation to perform, either addition or subtraction.
Taha
This seems complicated ngl. I tried to understand the Mathematics described here but got brain fog instead.... :/