Будем писать $a\equiv b$, если числа $a$ и $b$ дают одинаковые остатки при делении на $p$ (как известно, в этом случае говорят, что $a$ сравнимо с $b$ по модулю $p$ — см. статью «Сравнения и классы вычетов» в «Кванте» № 10). Тогда очевидно, что если $p$ — нечётное простое число, то существует такое целое число $s$, $0\le2s\lt p-1$, что $2s\equiv a_1+\ldots+a_{p-1}$ (продумайте это!).
Для доказательства нам понадобится лемма, которая однажды уже публиковалась в «Кванте» («Квант», 1971, № 8, с. 43):
Лемма. Пусть даны $r$ целых чисел $b_1$, $b_2$, $\ldots$, $b_r$, не делящихся на $p$; $0\lt r\lt p$, $p$ — простое. Тогда из этих чисел можно составить по крайней мере $r+1$ сумм, дающих различные остатки при делении на $p$ (при этом разрешается брать сумму «пустого множества слагаемых», которая считается равной нулю, суммы «из одного слагаемого», из двух, $\ldots$, из всех $r$ слагаемых).
Доказательство этой леммы мы приведём несколько ниже, а сейчас покажем, как с её помощью решается наша задача.
В силу леммы из чисел $a_1$, $\ldots$, $a_{p-1}$ можно составить по крайней мере $p$ сумм, дающих при делении на $p$ различные остатки. Поскольку всего различных остатков при делении на $p$ ровно $p$ штук: 0, 1, $\ldots$, $p-1$, среди этих сумм найдётся сумма, дающая при делении на $p$ остаток $s$. Пусть эта сумма $a_{i_1}+\ldots+a_{i_k}$; тогда $a_{i_1}+\ldots+a_{i_k}\equiv s$. Возьмём теперь все остальные числа, не вошедшие слагаемыми в сумму $a_{i_1}+\ldots+a_{i_k}$; пусть это числа $a_{j_1}$, $\ldots$, $a_{j_l}$. Поскольку $a_1+\ldots+a_{p-1} \equiv 2s$ и $a_{i_1}+\ldots+a_{i_k} \equiv s$, получаем, что $a_{j_1}+\ldots+a_{j_l} \equiv s$. Поменяв числа $a_{j_1}$, $\ldots$, $a_{j_l}$ на противоположные, получим число $a_{i_1}+\ldots+a_{i_k}-a_{j_1}-\ldots-a_{j_l}$, сравнимое с нулём по модулю $p$, т. е. делящееся на $p$.
Для завершения решения задачи нам осталось доказать лемму. Сделаем это по индукции.
При $r=1$ утверждение леммы очевидно. Предположим, что оно верно для $r=k\lt p-1$ и неверно для $r=k+1$, и придём к противоречию. Итак, пусть суммы из $k$ слагаемых $b_1$, $b_2$, $\ldots$, $b_k$ дают при делении на $p$ $k+1$ различных остатков 0, $s_1$, $\ldots$, $s_k$. Тогда, поскольку после присоединения $b_{k+1}$ количество различных сумм не должно увеличиваться, все суммы $0+b_{k+1}$, $s_1+b_{k+1}$, $\ldots$, $s_k+b_{k+1}$ по модулю $p$ содержатся в множестве $\{0,s_1,\ldots,s_k\}$. Другими словами, если к любому элементу этого множества прибавить $b_{k+1}$, то снова получится элемент того же множества. Таким образом, это множество заведомо содержит элементы 0, $b_{k+1}$, $2b_{k+1}$, $\ldots$, $(p-1)b_{k+1}$. Но ясно, что все эти элементы различны (по модулю $p$): разность $ib_{k+1}-jb_{k+1}=(i-j)b_{k+1}$, где $0\lt i-j\lt p$, не может делиться на $p$, поскольку $p$ — простое. Значит, множество $\{0,s_1,\ldots,s_k\}$ содержит все $p$ различных элементов, хотя мы предполагали, что $k+1\lt p$. Лемма доказана.
