математика - Найдите остаток при делении числа

Ввиду того, что $%2145=3\cdot5\cdot11\cdot13$%, достаточно найти остатки от деления на каждый из сомножителей. Слагаемые здесь имеют вид $%a(a^{2014}-1)/(a^2-1)=a(a^{2012}+a^{2010}+\cdots+a^2+1)$% при $%a$% от $%2$% до $%65$%. При каждом натуральном $%k$% последовательность остатков от деления на 3 чисел вида $%a^k$% является периодической. Если $%a$% делится на 3, остаток равен нулю. В противном случае $%a^2-1$% делится на 3, и любая степень с чётным показателем даёт в остатке 1. Таким образом, если $%a$% делится на 3, то слагаемое, выписанное выше, даёт в остатке 0. Если не делится, то в скобках складывается 1007 единиц (по модулю 3), что эквивалентно 2, то есть получается $%2a$%. Остатки будут такие: 1, 0, 2, 1, 0, 2, ... и далее с указанным периодом. Слагаемых у нас 64, и можно учитывать только самое первое, для $%a=2$% (так как остальное разбивается на тройки, а 1+0+2 кратно трём). Приходим к тому, что сумма $%S$% из условия даёт в остатке 1 при делении на 3.

Рассмотрим остатки от деления на 5, где всё также периодично. Сами остатки здесь можно не находить. Достаточно заметить, что 65 кратно 5, и при суммировании от 1 до 65 всё делилось бы на 5. Значит, достаточно учесть только случай $%a=1$%, где слагаемое даёт в остатке 2 (складывается 1007 единиц). В сумме с $%S$% имеет место делимость на 5. Значит, $%S$% при делении на 5 даёт в остатке 3.

Остаток от деления на 11 удобно анализировать, беря 66 слагаемых -- от 0 до 65. Тогда в сумме будет 0, и остаётся посмотреть на случаи $%a=0$%, $%a=1$%. В первом случае остаток равен нулю, во втором -- такой же, как у 1007, а это 6. В сумме с $%S$% получается 0, то есть $%S$% даёт в остатке 5 от деления на 11.

Случай остатка от деления на 13 исследуем тем же методом, беря 65 слагаемых. Всё сводится к случаю $%a=1$%, где остаток такой же, как у 1007, то есть 6. Значит, $%S$% при делении на 13 даёт "дополнительный" остаток $%7$%.

Осталось найти число, для которого $%S\equiv1\pmod3$%, $%S\equiv3\pmod5$%, $%S\equiv5\pmod{11}$%, $%S\equiv7\pmod{13}$%. Этим свойством обладает число $%1138$%, что можно проверить непосредственно. Сам способ решения таких систем достаточно стандартен, но здесь можно сказать несколько слов о том, как этот ответ получить. Из первых двух условий ясно, что $%S+2$% делится на 3 и на 5, а потому и на 15. Из двух последних условий $%S+6$% делится на $%11\cdot13$%, то есть $%S=143k-6$%. При этом $%S+2=143k-4$% делится на 15. То же верно для $%-7k-4$%, для $%-14k-8$%, а потому и для $%k-8$%. Полагая $%k=8$% (нам нужно наименьшее $%S$%, ибо это остаток), имеем $%S=143\cdot8-6=1138$% по модулю $%2145$%.

Добавление. Я начал решать как бы в общем виде, и не сразу заметил, что 1138 -- это 2145-1007. Тут есть более простой пусть решения с меньшим количеством вычислений. Если мы положим $%f(a)=a(1+a^2+a^4+\cdots+a^{2012})$%, то надо найти остаток от деления $%f(2)+\cdots+f(65)$%. При этом $%f(0)=0$% и $%f(1)=1007$%. Ясно, что $%f(1)+f(2)+\cdots+f(65)$% делится на 5 и на 13 из-за периодичности, а $%f(0)+f(1)+f(2)+\cdots+f(65)$% делится на 3 и на 11. Это одна и та же сумма за счёт $%f(0)=0$%, и тогда $%S+1007$% делится на 2145, откуда сразу ясно, что ответом будет разность 2145-1007=1138.