Решить линейное сравнение по модулю 17

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

Рассмотрим упр. 72, части а и б.

а) 12x \equiv 9 \pmod{17}

Нам нужно решить линейное сравнение по модулю 17.
Сначала проверим, существует ли решение. Для этого найдём НОД (наибольший общий делитель) чисел 12 и 17:

\gcd(12, 17) = 1

Так как НОД равен 1, решение существует и единственно по модулю 17.

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

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

Подбором или расширенным алгоритмом Евклида находим, что:

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

Теперь умножим обе части сравнения на 10:

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

x \equiv 90 \pmod{17}

Вычислим 90 \mod 17:

90 \div 17 = 5 \text{ (остаток } 5)

Значит:

x \equiv 5 \pmod{17}

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

б) 12x \equiv 6 \pmod{21}

Сначала найдём НОД чисел 12 и 21:

\gcd(12, 21) = 3

Так как НОД делит правую часть (6), уравнение имеет именно 3 решения по модулю 21.

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

\frac{12}{3}x \equiv \frac{6}{3} \pmod{\frac{21}{3}}

Получим:

4x \equiv 2 \pmod{7}

Теперь найдём обратный элемент к 4 по модулю 7. Нужно найти 4^{-1} \pmod{7}.

Подбором:
4 \cdot 2 = 8 \equiv 1 \pmod{7}, значит:

4^{-1} \equiv 2 \pmod{7}

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

x \equiv 4 \pmod{7}

Теперь восстановим решения по модулю 21. Так как мы делили модуль на 3, общее число решений — 3, и они отличаются на \frac{21}{3} = 7.

Значит, все решения:

x \equiv 4, 11, 18 \pmod{21}

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

Если нужно, могу также объяснить, как найти обратный элемент с помощью расширенного алгоритма Евклида.