# Question regarding divisibility test of 13

In order to develop a divisible test for 13, we use $1000 \equiv -1 \pmod{1001}$.
I understand the idea; however, why do we use $1001$, can we use any smaller number? For example, to test for divisible by $11$, we need to use only $10 \equiv -1 \pmod{11}$?

Thanks,

-
We use base 10, so the appearance of 1000 means we can look at the numbers 3 digits by 3 digits. This makes computations easy. – Soarer Feb 28 '11 at 4:57
@Soarer: Thank you. – Chan Feb 28 '11 at 5:03

There are many divisibility tests for $13$. But tests like that for $3$, $9$ and $11$ (among others) are particularly good because they not only test the number for divisibility, but they actually tell you the remainder when the number is not divisible by what you are testing.

What the "test in development" is trying to do is use something similar to the tests for $3$ and $9$ (adding the digits) or for $11$ (alternating sums and differerences of digits). In order to do something like that, with groups of digits, you want to find the smallest power of $10$ for which $10^k \equiv 1$ or $10^k\equiv -1 \pmod{13}$. The smallest such power happens to be $10^3 = 1000$ (as $10\equiv -3 \pmod{13}$, and $100 \equiv 9\equiv -4\pmod{13}$). So $10^3$ is the smallest one that can be used to develop a test that follows the pattern of those for $3$, $9$, and $11$.

Added. There are other tests, of course. For example, you can develop a test similar to the one for $7$: take the last digit, multiply it by $2$, and subtract it from the rest of the digits; the original number is divisible by $7$ if and only if the result is divisible by $7$; but if the result is not divisible by $7$, the remainder need not be the same as that for the original number). A similar test for $13$ is: take last digit, multiply it by $4$, and add it to the rest; the original number is divisible by $13$ if and only if the result is divisible by $13$.

-
Many thanks for your clear explanation. By the way, can you give me some other test technique for 13? I just want to see how they are. Thanks in advance ;) – Chan Feb 28 '11 at 5:05
– Arturo Magidin Feb 28 '11 at 5:12
Thank you. – Chan Feb 28 '11 at 5:27

My course handout at http://www.math.uconn.edu/~kconrad/blurbs/ugradnumthy/universaldivtest.pdf discusses a general method to derive such divisibility tests (by 7, 13, etc.).

-

Unless you're dividing by the radix $\rm\pm 1$, i.e. $9$ or $11$ in decimal, such divisibitity tests aren't really any quicker than simply evaluating the radix polynomial in Horner form using modular arithmetic. Here's one of my old posts describing such (which, as a bonus, describes how repeated squaring arises from binary Horner form).

-
Great thanks ;) – Chan Feb 28 '11 at 6:33