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,
 A: 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$. 
A: 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.).
A: 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).

A: Here is an example of how to derive a division test.

Suppose $13 \mid 10a+n$ where $a \in \mathbb Z^+$ and $n$ is a base-$10$ digit.
Note $3 \cdot 13 = 39$.
So $13 \mid 39a \iff 13 \mid 40a - a$
and  $13 \mid 10a+n \iff 13 \mid 40a + 4n$
Hence $13 \mid 10a+ b \iff 13 \mid a+4n$
