Азиатско-Тихоокеанская математическая олимпиада, 2008 год

Пусть $a$, $b$ и $c$ целые числа, такие, что $0 < a < c - 1$ и $1 < b < c$. Для каждого $k$ $(0 \leq k \leq a)$, обозначим через $r_k$ $(0 \leq r_k < c)$ остаток от деления $kb$ на $c$. Доказать, что два множества $\{r_0, r_1, r_2, \dots \, r_a \}$ и $\{ 0, 1, 2, \dots, a \}$ различны.

Комментарий/решение

Заметим, что из условия задачи следует: $x^0+x^b+...+x^{ab} \equiv x^0+x^1+...+x^a \pmod {x^c-1}.$ $(x^0+x^b+...+x^{ab})(x^b-1)(x-1) \equiv (x^0+...+x^a)(x^b-1)(x-1) \pmod {x^c-1}.$

$(x^{ab+b}-1)(x-1) \equiv (x^{a+1}-1)(x^b-1) \pmod {x^c-1}$

$x^{ab+b+1}-x^{ab+b}-x \equiv x^{a+1+b}-x^{a+1}-x^{b} \pmod {x^c-1}$

Теперь пусть $P, Q, R$ остатки при делении чисел $ab+b+1, a+1, b$ на $c$, и $p, q, r$ остатки при делении чисел $a+1+b, ab+b, 1$ на $c$.

Рассмотрим многочлен $x^{P}+x^{Q}+x^{R}-x^{p}-x^{q}-x^{r}$. Его степень меньше чем $c$. Поскольку он делиться многочлен степени $c$, то он равен нулю. Значит ${P, Q, R}$ совпадают ${p, q, r}$. Откуда легко вывести противоречие.

Пойдем от обратного:

$\{1,2,\dots,a\} \equiv \{r_1,r_2,\dots,r_a\} \pmod{c}$

$bi \equiv 1 \pmod{c} \rightarrow (b,c)=1$

Тогда:

$\{a+1,\dots,c-1\} \equiv \{r_{a+1},\dots,r_{c-1}\}$

$r_{c-1} \equiv c-b \pmod{c}$

$c-b \geq a+1 \rightarrow c>a+b$

$b<c \rightarrow b \leq a$

$a+b \geq 2b<c \rightarrow 2b \in \{1,2,\dots,a\} \rightarrow a\geq 2b$

$a+b \geq 3b, 3b \in \{1,2,\dots,a\}$

Аналогично:

$a\geq 4b,5b,\dots,ab \rightarrow 1\geq b \rightarrow \varnothing$

Ч.Т.Д.