Сравнение по модулю — Царство математики

Определение

$a$ сравнимо с $b$ по модулю $n$ , если при делении на $n$ они дают одинаковые остатки. Число $n$ называют модулем сравнения.

Обозначение: $a\equiv b\left ( \textit{mod n} \right )$ .

Пример 1. Верно ли сравнение $37\equiv 48 \left ( \textit{mod 11} \right )?$

Решение. 37 и 48 имеют одинаковый остаток при делении на 11. Следовательно, сравнение верно.

Ответ: Да.

Основная теорема

$a\equiv b\left ( \textit{mod n} \right ) \Leftrightarrow \left ( a-b\right ) \vdots n$

Пример 2.Верно ли сравнение $2038\equiv 753\left ( \textit{mod 5} \right )?$

Решение.

$2038-753 = 1285 \vdots 5.$ Следовательно, исходное сравнение верно.

Ответ: Да.

Основные свойства сравнений

$a\equiv a\left ( \textit{mod n} \right );$
$a\equiv b\left ( \textit{mod n} \right ) \rightarrow b\equiv a\left ( \textit{mod n} \right );$
$\left\{\begin{matrix}a\equiv b\left ( \textit{mod n} \right )\\ b\equiv c\left ( \textit{mod n} \right )\end{matrix}\right.\rightarrow a\equiv c\left ( \textit{mod n} \right );$
$\left\{\begin{matrix}a\equiv b\left ( \textit{mod n} \right )\\c\equiv d\left ( \textit{mod n} \right ) \end{matrix}\right.\rightarrow a+c\equiv b+d\left ( \textit{mod n} \right );$
$\left\{\begin{matrix}a\equiv b\left ( \textit{mod n} \right )\\c\equiv d\left ( \textit{mod n} \right ) \end{matrix}\right.\rightarrow a \cdot c\equiv b \cdot d\left ( \textit{mod n} \right );$
$\left\{\begin{matrix}a\equiv b\left ( \textit{mod n} \right )\\c\equiv d\left ( \textit{mod n} \right ) \end{matrix}\right.\rightarrow a-c\equiv b-d\left ( \textit{mod n} \right );$
$\left\{\begin{matrix}ac\equiv bc\left ( \textit{mod n} \right )\\\left ( \textit{c,n} \right )=1 \end{matrix}\right.\rightarrow a\equiv b\left ( \textit{mod n} \right );$
$a\equiv b\left ( \textit{mod n} \right ) \rightarrow a^k\equiv b^k\left ( \textit{mod n} \right ).$

Пример 3. Какие остатки по модулю 4 может иметь полный квадрат?

Решение.

Само число $n$ может давать при делении на 4 остатки: 0, 1, 2 или 3.

Если $n \equiv 0 \left ( \textit{mod 4} \right )$ , то $n^2 \equiv 0 \left ( \textit{mod 4} \right ).$

Если $n \equiv 1 \left ( \textit{mod 4} \right )$ , то $n^2 \equiv 1 \left ( \textit{mod 4} \right ).$

Если $n \equiv 2 \left ( \textit{mod 4} \right ))$ , то $n^2 \equiv 4 \equiv 0 \left ( \textit{mod 4} \right ).$

Если $n \equiv 3 \left ( \textit{mod 4} \right )$ , то $n^2 \equiv 9 \equiv 1 \left ( \textit{mod 4} \right ).$

Ответ: 0 и 1.

Пример 4. Может ли число $500 \ldots 09$ быть квадратом целого числа при каком-то количестве нулей?

Решение.

$500 \ldots 09 \equiv 2 \left ( \textit{mod 3} \right )$

Найдем остатки, которые может иметь полный квадрат при делении на 3.

Если $n \equiv 0 \left ( \textit{mod 3} \right )$ , то $n^2 \equiv 0 \left ( \textit{mod 3} \right ).$

Если $n \equiv 1 \left ( \textit{mod 3} \right )$ , то $n^2 \equiv 1 \left ( \textit{mod 3} \right ).$

Если $n \equiv 2 \left ( \textit{mod 3} \right )$ , то $n^2 \equiv 4 \equiv 1 \left ( \textit{mod 3} \right ).$

Следовательно, число $500 \ldots 09$ не может быть квадратом целого числа при каком-то количестве нулей.

Ответ: Нет.

3 Комментарий

Новые

Старые Популярные

Межтекстовые Отзывы

Посмотреть все комментарии

Akmat

2 месяцев назад

По поводу последнего примера: за модуль 3 взяли потому что нас спрашивают про количество нулей, и число 3 удобен за модуль, так как при квадрате может иметь остаток 1 или 0. Вспоминаем признак деления на 3. Сумма цифр должна делиться на 3. Но так как сумма цифр дает остаток 2 при делении на 2, значит и само число дает остаток при делении на 2. И если возводить в квадрат число, то и остаток должен возводиться, по свойству сравнения. Тогда в остатке получается 4, что не может быть при модуле 3

Анастасия

Автор

2 лет назад

Остаток при делении на 3 числа 500…09 равен 2.

Саня

люди, объясните последний пример, почему там мод 3 и тождественно равно 2?