Show that, given a 7-digit number, you can cross out somerst 3 and the last 2 digits of 1294961 to get 49.
digits at the beginning and at the end such that the remaining
number is divisible by 7. For example, you can cross out the
i know this problem uses the pigeonhole principle but i can't get to a point where i can use it. i would like to be able to remove a digit and somehow prove that each resulting number mod 7 is different. this is what i can't get to happen. at that point we could use the pigeonhole principle and say that one of the resulting numbers has to equal 0 mod 7.
Suppose:
If some of the numbers is already multiple of 7 we are done. Then assume that none of them is multiple of 7.
Remember now that if then that is we have 6 possible remainders, but we have 7 numbers, thus 2 of them are congruent mod 7.
That is for some natural numbers j and k such that
Thus, substracting:
Thus: but (10, 7)=1 thus: which proves the assertion