Задача
Даны целые числа $a_{1}, ..., a_{1000}$. По кругу записаны их квадраты $a_{1}^2, ..., a_{1000}^2$. Сумма каждых 41 подряд идущих квадратов на круге делится на $41^2$.
Верно ли, что каждое из чисел $a_{1}, ..., a_{1000}$ делится на 41?
Решение
Из условия следует, что $a_{k+41}^2\equiv a_k^2$ (mod 41²) (индексы считаем зацикленными, то есть за 1000 следует 1). Значит, $a_{k+41n}^2\equiv a_k^2$ (mod 41²) при любом $n$. Так как числа 41 и 1000 взаимно просты, то квадраты всех чисел на круге дают при делении на $41^2$ один и тот же остаток. Следовательно, $41a_k^2$ делится на $41^2$, поэтому $a_k^2$ делится на 41, а поскольку 41 – простое число, то и $a_k$ делится на 41.
Ответ
Верно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет