1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by colormegone, Jyrki Lahtonen May 25 '16 at 5:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ Easier to remember rule: divide the number by 13, and see if the remainder is zero. $\endgroup$ – vadim123 May 25 '16 at 4:33
  • $\begingroup$ There will not always be a simple rule (there won't be for most primes). That's because "rules" tend to manipulate the digits of the number, which is arbitrary since we decide to use base $10$. Thus, the rules will be "simple" if there is some lucky thing going on with the relation between the prime in question and $10$. e.g. Divisibility by 10 is very easy (does it end in 0?) and similarly for 3 since $3 \mid 10^n - 1$ for each $n$. $\endgroup$ – MCT May 25 '16 at 4:43
  • $\begingroup$ See also: math.stackexchange.com/questions/328562/… $\endgroup$ – lab bhattacharjee May 25 '16 at 4:44
  • 1
    $\begingroup$ I just cast out 13s. Example 4725 is div by 13 iff 3412 is iff 2112 is iff 2099 is iff 786 is iff 656 is iff 426 is iff 400 is iff 270 iff 10 is. It isn't. $\endgroup$ – fleablood May 25 '16 at 4:48
  • $\begingroup$ An advantage to casting out is it works for all numbers, and the final number will be the remainder of the original number. The remainder remains in tact. And you can cast out in any pattern of digits that is convenient. Oh, and for 13 you can cast out 91s or 104s if they are convenient. $\endgroup$ – fleablood May 25 '16 at 4:57
3
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ This proves that the rule works, but it doesn't answer the OP's question. ("What is the best way to judge whether a number is divisible by 13?") $\endgroup$ – Théophile May 25 '16 at 5:05
  • $\begingroup$ @Théophile Thanks for telling me that I skipped that part of the question. I have updated my answer. Please check. $\endgroup$ – SchrodingersCat May 25 '16 at 5:14
  • $\begingroup$ Looks good! That's helpful. $\endgroup$ – Théophile May 25 '16 at 12:29
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can I break 123,456,789 into 1234, 567, 89? $\endgroup$ – learning May 25 '16 at 12:49
  • 1
    $\begingroup$ @learning: no, you want three digits in each piece. If they don't break evenly, consider leading zeros, so from 12,345,876 you would do 12-345+876. As SchrodingersCat says, this works because $13$ divides into $1001$. In that way it is similar to the usual rule for $11$, but in blocks of three digits. $\endgroup$ – Ross Millikan May 25 '16 at 14:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.