-1
$\begingroup$

How to prove the following theorem. Could you explain.

Given the number $A = \langle a_n, a_{n-1}, \dots, a_0 \rangle_{10}$ and the modulus $m$ such that $(10, m) = 1$ from the sequence $b_1$,...,$b_n$ ($0 \leq b_i < m$ and $i = 1, \dots, n$) as follows D$a_0$ + $a_1$ is congruent to $b_1$ (mod m) D$b_0$ + $a_2$ is congruent to $b_2$ (mod m) and so on ...
D$b_(n-1)$ + $a_n$ is congruent to $b_n$ (mod m).

Thank you.

Here D is fixed in such a way, such that 10D is congruent to 1 (mod m)

  • 1
    The reason for the downvote is probably that the question is not very well stated, eeshan. Perhaps you should try to write it as close as possible to the way it was written at the place where you found it, or maybe you should just try to clarify yourself. I did not downvote but downvoters rarely explain, as they should... Welcome to MSE by the way =)2011-11-26

1 Answers 1

2

HINT $\ $ By induction, unwinding the recursive Horner evaluation scheme yields

$\rm b_n \equiv\: a_n + D\ b_{n-1}\equiv\: a_n + D\ (a_{n-1} + D\ b_{n-2})\equiv\:\cdots\:\equiv\: a_n + a_{n-1}\ D +\:\cdots\: + a_0\ D^n $ $\rm\:(D,m)=1\ \Rightarrow\: d = 1/D\:$ exists mod $\rm\:m\:$, so scaling by $\rm\:d^n\:$ yields

$\rm 0 \equiv b_n\iff\ 0\equiv b_n\ d^n\equiv\: a_n\ d^n + a_{n-1}\ d^{n-1} +\:\cdots\: + a_0 = A$

Therefore $\rm\: b_n\equiv 0 \iff A\equiv 0\pmod m\:.\:$ This is the idea behind various classical divisibility tests, e.g. division by $7$ in radix $10\:.\:$ For more on such see my prior posts on Horner schemes.

  • 0
    Bi$l$l, I am very thankful for your approach2011-11-27