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

Условие:

упражнение 72 только буквы а и б

Условие: упражнение 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_1 = 4
  • x_2 = 11
  • x_3 = 18

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


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

Не нашли нужного вам решения? Оставьте заявку и наши авторы быстро и качественно помогут вам с решением.
Оставить заявку
Работа вам нужна срочно. Не волнуйтесь, уложимся!
  • 22423 авторов готовы помочь тебе.
  • 2402 онлайн