No subject

[Max]

On 2/17/06, David Wilson <davidwwilson at comcast.net> wrote:> For n coprime to 10, empirical evidence suggests that any number of n digits or> more has a substring divisible by n.
That can be proved!
[...]
> - Is it indeed true that if gcd(n, b) = 1, a base-b n-digit number has a> substring divisible by n?
Let s_n s_{n-1} ... s_1 be any base-b digits.
For k=0,...,n, сompute S(k) = sum_{j=1}^k s_j * b^j.In particular, we have S(0)=0.
Since there are n possible values of S(k) mod n, the Pigeonholeprinciple implies that there exist two values equal modulo n, say,S(a)=S(b) (mod n) for some a,b, 0<=a<b<=n.Then the substring s_b s_{b-1} ... s_{a+1} is divisible by n.
Indeed, this substring corresponds to the numbersum_{j=a+1}^b s_j * b^{j-a-1} = (S(b)-S(a)) / b^(a+1)which is 0 modulo n.
Max