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.

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.

share|improve this question

1 Answer 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.

share|improve this answer

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.