математика - Арифметика остатков

Рассматриваемое число равно $%\dfrac{10^{69}-1}9$%. В пункте а) применяем малую теорему Ферма, согласно которой $%10^{70}\equiv1\pmod{71}$%. Пусть $%r$% -- искомый остаток. Тогда $%90r\equiv10^{70}-10\equiv-9\pmod{71}$%. Сокращаем на 9, и далее решаем линейное сравнение $%10r\equiv-1\pmod{71}$%. После домножения на 7 оно даёт $%70r\equiv-7\pmod{71}$%, откуда $%r\equiv7\pmod{71}$%. То есть остаток равен $%7$%.

Нахождение остатка по модулю 70 сводится к нахождению остатков по модулю 2, 5, 7. Здесь можно вместо этого рассмотреть остатки от деления на 10 и на 7. Для первого случая остаток равен 1 (последняя десятичная цифра). По модулю 7 всё также просто: если $%r$% -- искомый остаток, то $%9r\equiv10^{69}-1\equiv3^{69}-1\equiv3^3-1\equiv26\equiv-2\pmod7$%. Здесь также была использована малая теорема Ферма, согласно которой $%3^6\equiv1\pmod7$%, и тогда $%3^{69}=(3^6)^{11}3^3\equiv3^3\pmod7$%.

Теперь $%2r\equiv9r\equiv-2\pmod7$%, то есть $%r\equiv-1\equiv6\pmod7$%. То число, которое мы ищем, даёт остаток 1 при делении на 10 и остаток 6 при делении на 7. Можно решить систему линейных сравнений, но проще найти его подбором: согласно китайской теореме об остатках, число с таким свойством по модулю 70 существует и единственно. И тогда ясно, что если прибавить к числу 1, то оно будет оканчиваться на 2 и делиться на 7. Из таблицы умножения мы видим, что это 42. Значит, остаток в пункте б) равен $%41$%.