0
$\begingroup$

Could someone for me try to transform algorithm that is in next pdf into equation(s): http://arxiv.org/pdf/math/0507011?

For instance take example from page 6 for divisibility of number 16762 and try to find number 29(take 29 as x and 3 as (x+1)/10 (as from algorithm). The equation can also be tested in http://www.wolframalpha.com/ or by hand. Thanks.

1 Answers 1

1

The basic idea is that if $N=10a+b$ is divisible by $29$ (we are thinking of $b$ as the ones digit and $10a$ as all the rest), so is $10(a+3b)$ because we have added $29b$ to it, and then so is $a+3b$ because $10$ has no factors in common with $29$. You can then continue this reduction until the number is obviously divisible by $29$ or not.

The test for $7$ that I learned was to double the ones digit and subtract from the rest of the number. This relies on the fact that $7$ divides $21$ and we have the same chain: if $10a+b$ is divisible by $7$, so is $10(a-2b)$ because we have subtracted $21b$ and so is $a-2b$. The opening test in the article uses $49$.

This can be done for any prime except $2$ and $5$. Find some multiple that ends in $1$ or $9$. Add or subtract that multiple times the ones digit, which will leave a multiple of $10$. Then divide by $10$ and the number is smaller. Repeat until the answer is obvious.

The divide by $10$ step does not maintain the remainder, so you only learn whether the number is divisible. The usual test for $9$ of adding all the digits does give you the remainder.