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.

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)

share|improve this question
3  
Do you mean $A=10$, what are the $a_i$, and what is $D$? –  Dimitrije Kostic Nov 26 '11 at 18:37
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 =) –  Patrick Da Silva Nov 26 '11 at 18:49

1 Answer 1

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.

share|improve this answer
    
To the downvoter: if something is not clear then please feel free to ask questions and I am happy to elaborate. If you downvoted simply because you think it is wrong to answer fuzzy questions then please refrain from doing so in the future. –  Bill Dubuque Nov 26 '11 at 19:13
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? –  Chris Taylor Nov 26 '11 at 19:17
    
@Chris Because, otherwise, MathJax leaves much to be desired aesthetically. –  Bill Dubuque Nov 26 '11 at 19:21
    
Bill, I am very thankful for your approach –  eeshan Nov 27 '11 at 15:44

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.