Простыми преобразованиями эту задачу не решить, будем использовать арифметику остатков.
1-ое свойство, которое понадобится
)
То есть мы спокойно можем заменить каждое слагаемое сравнимым с ним по модулю m. То есть каждое слагаемое в нашей сумме будем рассматривать отдельно.
2-ое свойство, которое нам понадобится:
)
То есть довольно аналогичная вещь в произведении
На нашем примере все увидим
Находим остатки по модулю 31
Рассматриваем первое слагаемое. Просто двойка не годится, нам нужно найти ближайшее к 31 число, превосходящее его (иногда там в отрицательные числа залезаем, например, %20%5C%20(mod%20%5C%2017))
, но сейчас это не нужно), нам повезло, это 32
Учитываем, что )
, получаем
%5E%7B10%7D%3D%2010%5Ccdot%2032%5E%7B10%7D%20%5Cequiv%2010%20%5Ccdot%201%5E%7B10%7D%20%5C%20(mod%20%5C%2031))
То есть остаток от деления первого слагаемое на 31 получился равным 10. Прекрасно, аналогично со вторым
%20%5Cequiv%2021%20%5C%20(mod%20%5C%2031))
Остаток 21, чудесно. Выполняем последний шаг.
%20%5Cequiv%2031%20%5C%20(mod%20%5C%2031)%20%5Cequiv%200%20%5C%20(mod%20%5C%2031))
То есть остаток от деления исходного числа на 31 равен 0, следовательно, исходное число делится на 31, что и требовалось доказать.