Глава 5. Арифметика остатков

Большинство алгоритмов, описанных в предыдущих главах, проверяют делимость чисел непосредственным делением, убеждаясь, что в остатке действительно получается 0. Однако сейчас изобретены более эффективные методы, одним из которых (в главе 10) доказано, что множитель числа Так как эти числа слишком большие, мы полагаем, что даже проверка справедливости этого утверждения непосредственным делением займет очень много времени. Можно ли оценить насколько велико число Пользуясь логарифмами, легко показать, что в нем более, чем знаков! То есть количество знаков в F (23 471) больше числа элементарных частиц в видимой части вселенной. Не приходится и говорить о проверке непосредственным делением того факта, что множитель числа . Как же тогда это сделать?

Выход из этой дилеммы заключается в использовании арифметики остатков, являющейся темой данной главы. При решении вопросов делимости техника арифметики остатков играет основную роль и, как мы увидим в главе 8, она полезна также при вычислениях, имеющих отношение к феномену периодичности.

Основные идеи арифметики остатков были известны очень давно, но систематическую разработку ее аппарата впервые осуществил Гаусс в начале своих «Арифметических исследований» (см. [17]). В наше время к арифметике остатков обычно подходят с точки зрения отношения эквивалентности, которое мы подробно рассматриваем в первом параграфе.