Track / Stage 6 / 285 of 400 #1925 of 2604

Problem 1925

National Olympiad, first round

Number theory Difficulty 6.5 Prove it Russia — Final Round · Russia

Given $n \ge 3$ pairwise coprime positive integers. It is known that while dividing the product of any $n-1$ of them by the remaining number, a remainder equals to $r$ (the remainder $r$ is the same for all $(n-1)$ -tuples). Prove that $r \le n-2$ .

Даны $n \ge 3$ попарно взаимно простых чисел. Известно, что при делении произведения любых $n-1$ из них на оставшееся число получается один и тот же остаток $r$ . Докажите, что $r \le n-2$ . (В. Сендеров)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Если $r = 0$ , то утверждение задачи, очевидно, истинно. Пусть $r > 0$ . Пусть $a_1, \dots, a_n$ — данные числа; положим $P = a_1a_2 \dots a_n$ , $P_i = P/a_i$ при $i = 1, 2, \dots, n$ . Заметим, что $a_i > r$ , ибо число $P_i$ даёт остаток $r$ при делении на $a_i$ .

Рассмотрим число $S = P_1 + P_2 + \dots + P_n - r$ . Заметим, что $S = (P_1-r) + (P_2+P_3+\dots+P_n) = a_1$ , поскольку оба слагаемых делятся на $a_1$ . Аналогично, $S : a_i$ при всех $i = 1, \dots, n$ ; поскольку $a_i$ попарно взаимно просты, получаем $S : a_1 \dots a_n = P$ . Поскольку $S > a_1 - r > 0$ , получаем, что $S \ge P$ , а тогда $P_1 + \dots + P_n = S + r > P$ . Значит, при некотором $i$ верно неравенство $P_i > P/n$ , откуда $a_i < n$ , или $a_i \le n - 1$ . Но тогда $r < a_i \le n - 1$ , то есть $r \le n - 2$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.