A number is divisible by 13

Question

I am studying divisibility and come across this rule. I think the rule is too complicated and hard to understand and remember. What is the best way to judge whether a number is divisible by 13 without having to remember this rule?

Delete the last digit from the number, and then subtract 9 times the deleted digit from the remaining number. If what is left is divisible by 13, then so is the original number. Repeat the rule if necessary.

Answer 1

Answer to the OP's Question:

The best way to judge this divisibility by $13$ would be to use the congruence relation $$1000 \equiv -1\pmod {13}$$ Using this relation, it will be very easy to check for divisibility by $13$ for large-digited numbers (greater than $3$ digits). However, this method does not work for numbers with $1,2,3$ digited numbers. Hence for numbers with less than $4$ digits, it is better to divide and check what happens.

Justification of the Rule:

Say $N=a_0+10a_1+10^2a_2+\ldots +10^na_n$ is any number and $a_0$ is the digit in its units' place.

On deleting the last digit, the number becomes $a_1+10a_2+\ldots +10^{n-1}a_n$

And on subtracting $9$ times the deleted digit, the number becomes $a_1+10a_2+\ldots +10^{n-1}a_n-9a_0$

Then according to the given algorithm, you have to check if $$a_1+10a_2+\ldots +10^{n-1}a_n-9a_0 \equiv 0 \pmod{13}$$

If the above holds, then it means $$a_1+10a_2+\ldots +10^{n-1}a_n-9a_0 \equiv 0 \pmod{13}$$ Or $$10a_1+10^2a_2+\ldots +10^na_n-90a_0 \equiv 0 \pmod{13}$$ Or $$a_0+10a_1+10^2a_2+\ldots +10^na_n-91a_0 \equiv 0 \pmod{13}$$ Or $$a_0+10a_1+10^2a_2+\ldots +10^na_n \equiv 91a_0 \pmod{13}$$

And irrespective of $a_0$, $13$ divides $91$. So we get $$a_0+10a_1+10^2a_2+\ldots +10^na_n \equiv 91a_0 \equiv 0\pmod{13}$$ that is, $$N \equiv 0\pmod{13}$$ that is, $$13|N$$

Answer 2

Another rule is to break the digits into groups of three, add the odd ones and subtract the even ones, and check if the result is divisible by $13$. For example, if you want to see if $123,456,789$ is divisible by $13$ you can do $123-456+789=456$ and check by trial division whether $456$ is divisible by $13$. When you find $456/13$ has remainder $1$, so does $123,456,789$. This works because $13$ divides into $1001$. Whether this is more or less complicated than trial division is in the eye of the beholder. Unlike the rule you quote, it gives you the remainder on division by $13$.