Азия-тынық мұхит математикалық олимпиадасы, 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, \ldots \,, r_a\}$ және $\{0, 1, 2, \ldots, 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$

Ч.Т.Д.