1. Pigeon Hole Help needed

Prove that the sequence 1967, 19671967, 196719671967,... contains an element that is divisible by 1969.

thanx

2. Originally Posted by dajaka
Prove that the sequence 1967, 19671967, 196719671967,... contains an element that is divisible by 1969.
thanx
let $\displaystyle x_n$ be the n-th term of this sequence, i.e. $\displaystyle x_1=1967, \ x_2=19671967, \ x_3=196719671967, \ \cdots .$ see that if $\displaystyle n > m,$ then: $\displaystyle x_n - x_m =10^{4m}x_{n-m}. \ \ \ \ \ \ (1)$

now the sequence is infinite and we know that modulo 1969 there are only 1969 distinct integers. therefore there exist $\displaystyle n > m$ such that $\displaystyle x_n \equiv x_m \mod 1969.$

hence by (1): $\displaystyle 10^{4m}x_{n-m}=x_n - x_m \equiv 0 \mod 1969,$ which gives us: $\displaystyle x_{n-m} \equiv 0 \mod 1969,$ because obviously: $\displaystyle \gcd(10^k, 1969)=1, \ \forall k \in \mathbb{N} \ \ \ \Box$

3. thanx
i think pigeonhole is used, right?

4. Originally Posted by dajaka
thanx
i think pigeonhole is used, right?
Yes man the pigeonhole is used! in term of remainders,

Try to look at this link A Walk Through Combinatorics: An ... - Google Ricerca Libri

The first chapter is about this principle and you can find a more detailed proof reletaed to this problem. It is the first of them. page 2.

Bye