Editing Divisibility rule (section)

=== Divisibility by 13 ===
Remainder Test
13 (1, −3, −4, −1, 3, 4, cycle goes on.)
If you are not comfortable with negative numbers, then use this sequence. (1, 10, 9, 12, 3, 4)

Multiply the right most digit of the number with the left most number in the sequence shown above and the second right most digit to the second left most digit of the number in the sequence. The cycle goes on.

Example: What is the remainder when 321 is divided by 13?<br/>
Using the first sequence, <br>
Ans: '''1''' × 1 + '''2''' × −3 + '''3''' × −4 = −17<br/>
Remainder = −17 mod 13 = 9

Example: What is the remainder when 1234567 is divided by 13?<br/>
Using the second sequence, <br>
Answer: '''7''' × 1 + '''6''' × 10 + '''5''' × 9 + '''4''' × 12 + '''3''' × 3 + '''2''' × 4 + '''1''' × 1 = 178 mod 13 = 9<br/>
Remainder = 9

A recursive method can be derived using the fact that <math>10 = -3\bmod 13</math> and that <math>10^{-1} = 4\bmod 13</math>. This implies that a number is divisible by 13 iff removing the first digit and subtracting 3 times that digit from the new first digit yields a number divisible by 13. We also have the rule that 10 x + y is divisible iff x + 4 y is divisible by 13. For example, to test the divisibility of 1761 by 13 we can reduce this to the divisibility of 461 by the first rule. Using the second rule, this reduces to the divisibility of 50, and doing that again yields 5. So, 1761 is not divisible by 13.

Testing 871 this way reduces it to the divisibility of 91 using the second rule, and then 13 using that rule again, so we see that 871 is divisible by 13.