Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
1  
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
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
    
    
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.).

share|improve this answer

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

enter image description here

share|improve this answer
    
Great thanks ;) –  Chan Feb 28 '11 at 6:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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