Арифметические приложения теории сравнений

Нахождение остатков при делении на данное число
Из теории сравнений известно, что целое число a и остаток r от деления a на число m принадлежат одному и тому же классу вычетов по модулю m, т.е.
Остаток r является наименьшим неотрицательным вычетом класса по модулю m

Нахождение остатков при делении на данное число
Пусть – остатки от деления
чисел на m. Тогда:
а) Складывая почленно сравнения (1), получим:
Следовательно, нахождение остатка от деления числа
на m можно заменить более легкой задачей – нахождением остатка от деления числа на m.
Если , то и будет искомым остатком

Нахождение остатков при делении на данное число
Пусть – остатки от деления
чисел на m. Тогда:
б) Умножая почленно сравнения (1), получим сравнение
в) Если , то получим:

Нахождение остатков при делении на данное число
Примеры
Найдем остаток от деления числа
на 135

Признаки делимости
Очень часто возникает потребность, не производя самого деления, ответить на вопрос о делимости одного числа на другое
Критерий, устанавливающий необходимое и достаточное условие делимости произвольного натурального числа a на данное натуральное число m, называется признаком делимости на m

Признаки делимости
Французский математик Блез Паскаль (1623-1662) открыл общий признак делимости, который в терминах сравнений может быть сформулирован следующим образом:
Т е о р е м а 1 (общий признак делимости Паскаля)
Для того чтобы число a, записанное в произвольной
g-ичной системе счисления в виде:
делилось на число m, необходимо и достаточно, чтобы число
делилось на m
(здесь – цифры числа a, а – абсолютно наименьшие вычеты соответствующих степеней
по модулю )