Работа вам нужна срочно. Не волнуйтесь, уложимся!
- 22423 авторов готовы помочь тебе.
- 2402 онлайн
упражнение 72 только буквы а и б
Предмет: Математика
Раздел: Теория чисел — сравнения по модулю (конгруэнции)
Рассмотрим упражнение 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 \equiv 4, 11, 18 \pmod{21}
Если нужно, могу продолжить с пунктами в и г.