теория - Представляя целое число в системе счисления, вывести признаки делимости

Пусть число $%n$% записано в системе счисления с основанием $%12$%. Обозначим его цифры, читаемые справа налево, через $%a_0$%, $%a_1$%, $%a_2$%, и так далее. Тогда, по определению позиционной записи числа в системах счисления, имеет место равенство $$n=a_0+12a_1+12^2a_2+12^3a_3+12^4a_4+\cdots\,.$$ Нас интересует значение $%n$% по модулю $%5$% (то есть его остаток от деления на $%5$%); в частности, случай, когда этот остаток равен нулю.

Для анализа этой ситуации заметим, что $%12\equiv2\pmod5$%. Из свойств сравнений следует, что это же верно для всех степеней, то есть $%12^k\equiv2^k\pmod5$% при всех целых неотрицательных $%k$%. Таким образом, $$n\equiv a_0+2a_1+2^2a_2+2^3a_3+2^4a_4+\cdots\pmod5.$$ Теперь надо понять, как ведут себя степени двойки по модулю $%5$%. Последовательность остатков является периодической, как это всегда бывает в таких случаях. Конкретно: $%2^0\equiv1\pmod5$%, $%2^1\equiv2\pmod5$%, $%2^2\equiv4\equiv-1\pmod5$%, $%2^3\equiv-2\pmod5$%, $%2^4\equiv1\pmod5$%, и далее всё периодически повторяется. Таким образом, степени двойки из предыдущего равенства можно заменить на числа $%1,2,-1,-2$% с последующим периодическим повторением: $$n\equiv (a_0+2a_1-a_2-2a_3)+(a_4+2a_5-a_6-2a_3)+\cdots\pmod5.$$ Фактически, это и есть требуемый признак делимости. Его можно применить, например, к тому числу, цифры которого у меня были выписаны в качестве случайно взятого примера: $%\overline{4aa9b7}$%. Понятно, каковы здесь цифры, и их для удобства можно сразу заменить их остатками от деления на $%5$%, то есть на $%4,0,0,4,1,2$% в том порядке, в котором они идут. Далее подставим их в формулу выше, беря их сумму с коэффициентами $%1,2,-1,-2,\ldots$%, читая их справа налево. Получится $$1\cdot2+2\cdot1-1\cdot4-2\cdot0+1\cdot0+2\cdot4\equiv3\pmod5.$$ Значит, наше число при делении на $%5$% даёт в остатке $%3$%.