Question

Решить сравнение 19х (тройное равно) 4 (мод 25)

Answer 1

19x ≡ 4 (mod 25)

(19; 25) = 1, поэтому

x ≡ 4 * 19^(Ф(25) - 1) (mod 25), где Ф(m) - функция Эйлера

Ф(25) = 25 - 5 = 20

x ≡ 4 * 19¹⁹ (mod 25) ≡ 4 * (24 - 5)¹⁹ (mod 25) ≡ 4 * (24¹⁹ - 19*24¹⁸*5 + 25A) (mod 25) ≡ 4 * ((-1)¹⁹ - 19*5 * (-1)¹⁸) (mod 25) ≡ 4 * (-1 - 95) (mod 25) ≡ 4 * 4 (mod 25) ≡ 16 (mod 25)

Ответ: x ≡ 16 (mod 25)

Answer 2

Чтобы решить данное сравнение 19х ≡ 4 (mod 25), нужно найти значение х, которое удовлетворяет данному условию.

Модульное сравнение решается с помощью обратного элемента (инверсии) числа по модулю. В данном случае, нам нужно найти такое число х, которое при умножении на 19 и взятии остатка от деления на 25 даст 4.

1. Найдем обратный элемент 19 по модулю 25: Обратный элемент существует, если число 19 и модуль 25 являются взаимно простыми (не имеют общих делителей, кроме 1). В данном случае это так, потому что 19 и 25 простые числа и не имеют общих делителей, кроме 1.

Для нахождения обратного элемента по модулю 25 можно воспользоваться расширенным алгоритмом Евклида. Однако, проще всего попробовать все возможные числа в качестве обратного элемента и проверить их по условию.

19 * 1 ≡ 19 (mod 25) 19 * 2 ≡ 38 ≡ 13 (mod 25) 19 * 3 ≡ 57 ≡ 7 (mod 25) 19 * 4 ≡ 76 ≡ 1 (mod 25)

Таким образом, обратным элементом числа 19 по модулю 25 является 4.

2. Теперь, чтобы найти значение х, умножим обратный элемент на правую часть сравнения:

х ≡ 4 * 4 ≡ 16 (mod 25)

Ответ: x ≡ 16 (mod 25)