Азиатско-Тихоокеанская математическая олимпиада, 2008 год
Комментарий/решение:
Заметим, что из условия задачи следует: $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$
Ч.Т.Д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.