3
$\begingroup$

Prove, that no matter how we give $8$ three-digit numbers, we can always choose $2$ of them, which we write next to each other, that six-digit number will be divisible with $7$. Example: I have $123$, and $456$ and I can make $123456$ or $456123$ as a $6$-digit number.

Edit: I think it has to do something with 8. From 8 numbers you can always choose 2 which are congruent to each other(mod7), and these 2 numbers, wrote down as 6 digit number are good.

$\endgroup$
8
$\begingroup$

Hints:

  1. $1000\equiv -1\mod 7$
  2. $8>7$
  3. Pigeon Hole Principle
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Using Julian Aguirre’s hints, in case this is helpful to others...

There are 7 possible remainders upon division by 7. If we have 8 numbers then by the pigeonhole principle and the fact that $8 > 7$, at least two of these numbers must share their remainder. Call these two numbers $a$ and $b$. Since they are three digit numbers, writing them next to each other forms the number $1000a + b$. Since $1000 \equiv -1 \pmod 7$, the remainder of $1000a$ is ‘minus one times’ the remainder of $a$. The remainder of $1000a + b$ is the sum of the remainders of $1000a$ and $b$ which now clearly is zero. So this number is divisible by 7.

The final two steps follow from the elementary facts that if $a \equiv p \pmod n$ and $b \equiv q \pmod n$ then $a + b \equiv p + q \pmod n$ and $ab \equiv pq \pmod n$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.