Сравнение по модулю и их приложения

Последние сравнения выполняются в том и только том случае, если x-x0 нацело делится на mi, i=1, k. Учитывая попарную взаимную простоту модулей mi, можно сделать вывод, что последнее свойство выполняется для тех и только тех чисел x, для которых x-x0 нацело делится на M, то есть x≡x0 mod M. Теорема доказана.
Следствие 1. Если числа a1, a2, …, ak независимо друг от друга пробегают полные системы вычетов по модулям m1, m2, …, mk соответственно, то числа x0 ,определенные для каждого набора a1, a2, …, ak с помощью равенств (11), пробегают полную систему вычетов по модулю M=m1⋅…⋅mk.
Доказательство. Для доказательства следствия достаточно показать, что числа x0 из условия теоремы принадлежат разным классам вычетов по модулю M.
Предположим, что a1, a2, …, ak и a1′, a2′, …, ak’ – два набора вычетов по модулям m1, m2, …, mk, причем такие, что хотя бы для одного индекса i выполняется условие, что mi не делит нацело ai-ai’. Пусть также числа bi, bi’ удовлетворяют сравнениям
Mibi≡ai mod mi, M-i bi’≡ai’ mod mi
и
x0=i=1kMibi, x0’=i=1kMibi’.
Если x≡x0′ mod M, то при любом i=1, k выполняются сравнения x0≡x0′ mod mi’. Учитывая, что Mj нацело делятся на mi при j≠i, можно сделать вывод, что Mibi≡Mibi’ mod mi. Но тогда ai≡ai’ mod mi, то есть aiи ai’ принадлежат одному классу вычетов по модулю mi. Так как это доказано для любого индекса i, то получили противоречие с предположением. Следовательно, оно не верно, что и доказывает теорему.
Следствие 2. Если все числа a1, a2, …, ak независимо друг от друга пробегают приведенные системы вычетов по модулям m1, m2, …, mk соответственно, то числа x0, определенные для каждого набора a1, a2, …, ak с помощью равенств (11), пробегают приведенную систему вычетов по модулю M=m1⋅…⋅mk.
Доказательство. Все числа x0, полученные согласно условию, принадлежат различным классам вычетов по модулю M. Это доказано в следствии 1.
Так как
M, x0=m1, x0⋅…⋅mk, x0=m1, a1⋅…⋅mk, ak,
то равенство x0, M=1 выполняетсятогда и только тогда, когда ai, mi=1, i=1, k. Что и доказывает следствие.
Сравнения любой степени по составному модулю
Сначала рассмотрим случай, когда модуль сравнения есть степень простого числа, то есть m=pk, k≥2. Если fx – многочлен с целыми коэффициентами и целое число a удовлетворяет сравнению fx≡0 mod pk, то pk нацело делит fa. Но в этом случае и p нацело делит fa, то есть a удовлетворяет сравнению fx≡0 mod p. Тогда можно сделать два вывода.