Сравнения по модулю. Основные свойства.

Определение

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

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

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

Решение. 37 и 45 имеют одинаковый остаток при делении на 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. Следовательно, исходное сравнение верно.

Ответ: Да.

Основные свойства сравнений
  1. a\equiv a\left ( \textit{mod n} \right );
  2. a\equiv b\left ( \textit{mod n} \right ) \rightarrow b\equiv a\left ( \textit{mod n} \right );
  3. \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 );
  4. \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 );
  5. \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 );

  6. \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 );

  7. \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 );

  8. 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 не может быть квадратом целого числа при каком-то количестве нулей.

Ответ: Нет.

Подписаться
Уведомить о
guest
0 Комментарий
Межтекстовые Отзывы
Посмотреть все комментарии