# How am I supposed to tell if a number is divisible by $13$ (I need a shortcut)?

I've been trying to figure out if a number is divisible by $13$. As I'm saying this in first person, I think I'm supposed to take the rightmost digit of the number, for example, $39$, multiply it by 9, and finally subtract the digit from the rest of the digits put in order to the left of that rightmost digit. The final result has to be divisible by $13$. So, in $39$, $9*9=81-3=78$, and $78$ is divisible by $13$. I think this is it. Am I on the right digit track? I just want some answers with words that will satisfy me.

• One way is presented here and another one here – k1next Nov 8 '14 at 20:07
• Your method works, but the second link provided by @sonystarmap works similarly, but perhaps slightly better. Your method relies on the fact that $9\cdot10=90=91-1$, and $91$ is divisible by $13$. And that other method relies on $4\cdot10=10=39+1$, and $39$ is divisible by $13$. – Harald Hanche-Olsen Nov 8 '14 at 20:15

Here is an explanation of why your method works: $13$ is a prime number, and thus has no factors in common with $9$. So $n$ is divisible by $13$ if and only if $9n$ is divisible by $13$.

Now write $n=10a+b$, where $b$ is the final digit of $n$ and $a$ is the number composed of the remaining digits. Then $$9n=90a+9b=91a+(9b-a),$$ and this is divisible by $13$ if and only if $9b-a$ is divisible by $13$ – because $91a=13\cdot7a$ is clearly divisible by $13$.

I find that with the possible exceptions of the rules for $9$ and $11$, the digit-based divisibility rules are annoyingly slow to actually use, e.g. in your head. If you've ever passed the time by looking at random numbers around you and trying to find their prime factors (and who hasn't?), you would never used a digit-based divisibility rule for testing for divisibility by even $7$, let alone $13$.

Here is what I do: I start with a number $n$ and a prime $p$ I want to test divisibility for, and then I transform the number in various ways such that the transformed number is divisible by $p$ if and only if $n$ is. The most common transformation is subtracting powers of $10$ times small multiples of $p$ (which ideally should be memorized). Eventually I try to get a number where it's either obviously divisible by $p$ or obviously not divisible by $p$, e.g. because it has a lot of trailing zeroes or is small.

For example, let's take the current year, $2014$. Is it divisible by...

• $7$? Well, $2014 - 14 = 2000$, so no. (See how fast that was?)
• $13$? Well, $2014 - 1300 = 714$, and $780 - 714 = 66$, so no. (Here I'm taking advantage of my freedom to subtract a number slightly larger than my current number, then take its negative.)
• $17$? Well, $2014 - 1700 = 314$, and $340 - 314 = 26$, so no.
• $19$? Well, $2014 - 1900 = 114$, and $114 - 95 = 19$, so yes! But let's pretend we didn't notice that so I can demonstrate the method for larger primes.
• $23$? Well, $2300 - 2014 = 286$, and $286 - 230 = 56$, so no.
• $29$? Well, $2900 - 2014 = 886$, and $886 - 870 = 16$, so no.
• $31$? Well, $3100 - 2014 = 1086$, and $1086 - 930 = 156$, so no.

These kinds of arguments are relatively easy to perform in your head because, rather than keep track of two pieces of information (the digits you have left to use, and the digit sum or whatever that you're in the process of computing), you only keep track of one piece of information (a number which is divisible by $p$ if and only if your original number was).

Because you're only testing for divisibility and not trying to find either the remainder or the quotient, you can ignore information and there are more moves available to you: for example, you can at any step in this process multiply or divide by other primes. I didn't use this freedom above, but I did refrain from dividing by $2$; that happened to make some of the arguments more convenient.

For numbers up to $1000$ do what you can. For somewhat larger, subtract off multiples of $$1001 = 7 \cdot 11 \cdot 13$$ until you get somethng no larger than $1000.$ This way you get $7$ and $13$ at the same time, also $11,$ although $11$ has its own.

It looks like my own method is pretty much right. For example, $156$: $6*9=54-15=39$, and $39$ is divisible by $13$. It looks like this can work any time. I think this works out perfectly.