Competition problem — Number theory

Library / /13 of 29

Number theory Difficulty 5.2 AIME, harder Prove it Ukraine

Numbers $a_1, a_2, a_3, a_4, a_5$ and $b_1, b_2, b_3, b_4, b_5$ are permutations of $1, 2, 3, 4, 5$ . Prove that among five numbers $a_1b_1, a_2b_2, a_3b_3, a_4b_4, a_5b_5$ at least two have the same remainders modulo $5$ .

Solution

WLOG, $a_5 = 5$ . If $b_5 \neq 5$ , then there will be two numbers that are divisible by $5$ . Let $b_5 \neq 5$ and suppose that the statement of the problem is false. Then the numbers $a_1b_1, a_2b_2, a_3b_3, a_4b_4$ have remainders $1, 2, 3$ and $4$ modulo $5$ (in some order). Then from one hand the product has remainder $4$ .

From the other, since the numbers $a_1, a_2, a_3, a_4$ and $b_1, b_2, b_3, b_4$ are permutations of $1, 2, 3$ and $4$ , the product is $a_1b_1 \cdot a_2b_2 \cdot a_3b_3 \cdot a_4b_4 = 24 \cdot 24 = 576$ has remainder $1$ modulo $5$ . This contradiction finishes the proof.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.