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,
Answer
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$.
No comments:
Post a Comment