-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)

  • 3
    Do you mean $A=10$, what are the $a_i$, and what is $D$?2011-11-26
  • 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.

  • 1
    Bill, I've always wondered why you set all of the math in your answers in roman type. Any particular reason, or just whimsy?2011-11-26
  • 0
    @Chris Because, otherwise, MathJax leaves much to be desired aesthetically.2011-11-26
  • 0
    Bill, I am very thankful for your approach2011-11-27