# Math Help - Pigeon Hole Help needed

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 $x_n$ be the n-th term of this sequence, i.e. $x_1=1967, \ x_2=19671967, \ x_3=196719671967, \ \cdots .$ see that if $n > m,$ then: $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 $n > m$ such that $x_n \equiv x_m \mod 1969.$

hence by (1): $10^{4m}x_{n-m}=x_n - x_m \equiv 0 \mod 1969,$ which gives us: $x_{n-m} \equiv 0 \mod 1969,$ because obviously: $\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