Решить линейные сравнения по модулю с помощью преобразований

Предмет: Математика
Раздел: Теория чисел — сравнения по модулю (конгруэнции)

Рассмотрим упражнение 72, пункты а и б. Задача — решить линейные сравнения по модулю с помощью преобразований.

а) Решить сравнение

12x \equiv 9 \pmod{17}

Шаг 1: Проверим, существует ли решение.
Для этого найдём \gcd(12, 17). Так как 17 — простое число, и не делит 12, то:

\gcd(12, 17) = 1 — решение существует и оно единственное по модулю 17.

Шаг 2: Умножим обе части на обратный элемент к 12 по модулю 17.
Найдём такое число 12^{-1}, что:

12 \cdot 12^{-1} \equiv 1 \pmod{17}

Найдём обратный элемент методом подбора или расширенным алгоритмом Евклида. Подбором:

12 \cdot 10 = 120 \equiv 1 \pmod{17}, так как 120 \mod 17 = 1

Значит, 12^{-1} \equiv 10 \pmod{17}

Шаг 3: Умножим обе части сравнения на 10:

10 \cdot 12x \equiv 10 \cdot 9 \pmod{17}

x \equiv 90 \pmod{17}

90 \mod 17 = 5, так как 17 \cdot 5 = 85, и 90 - 85 = 5

Ответ:
x \equiv 5 \pmod{17}

б) Решить сравнение

12x \equiv 6 \pmod{21}

Шаг 1: Найдём \gcd(12, 21) = 3

Проверим делимость правой части на НОД:

6 \div 3 = 2 — делится, значит, решение существует и их будет 3 (равно НОД).

Разделим всё сравнение на 3:

4x \equiv 2 \pmod{7}

Шаг 2: Найдём обратный элемент к 4 по модулю 7

Найдём 4^{-1} \pmod{7}, такое, что 4 \cdot y \equiv 1 \pmod{7}

Подбором:

4 \cdot 2 = 8 \equiv 1 \pmod{7}

Значит, 4^{-1} \equiv 2 \pmod{7}

Шаг 3: Умножим обе части на 2:

x \equiv 2 \cdot 2 \equiv 4 \pmod{7}

Теперь восстановим решение исходного сравнения. Так как мы делили на 3, то общее решение:

x \equiv 4 \pmod{7} → найдём 3 решения по модулю 21:

x = 4 + 7k, где k = 0, 1, 2

Тогда:

• x_1 = 4
• x_2 = 11
• x_3 = 18

Ответ:
x \equiv 4, 11, 18 \pmod{21}

Если нужно, могу продолжить с пунктами в и г.