Question

Решить сравнение первой степени. 45x=56(mod29)Распишите пожалуйста пошаговое решение

Answer 1

Ответ:

Пошаговое объяснение:

1) Нет решений ((16; 12) не делит 10).

2) 34x ≡ 70 (mod 29); 5x ≡ 12 ( mod 29); x ≡ 12·5²⁷ ≡ 12·9⁹ ≡ 12·4³ ≡ 12·6 ≡ 14 (mod 29);

3) 15x ≡ 18 (mod 24); 5x ≡ 6 (mod 8); x ≡ 6·5³ ≡ 6 (mod 8) → три решения по модулю 24:

x ≡ 6 (mod 24), x ≡ 14 (mod 24), x ≡ 20 (mod 24).

Answer 2

Чтобы решить линейное сравнение первой степени вида $45x \equiv 56 \pmod{29}$, мы можем использовать расширенный алгоритм Евклида для нахождения обратного элемента $45^{-1} \pmod{29}$, а затем умножить обе стороны сравнения на этот обратный элемент.

Шаг 1: Находим обратный элемент $45^{-1} \pmod{29}$.

Для нахождения обратного элемента $a^{-1} \pmod{m}$, мы можем использовать расширенный алгоритм Евклида. Этот алгоритм позволяет нам найти целые числа $x$ и $y$, такие что $ax + my = 1$, если $\text{gcd}(a, m) = 1$. В нашем случае, $a = 45$ и $m = 29$. Давайте найдем обратное число:

Применяем расширенный алгоритм Евклида:

$$\begin{align*} a &= 45, \quad m = 29 \\ r_0 &= 45, \quad r_1 = 29 \\ s_0 &= 1, \quad s_1 = 0 \\ t_0 &= 0, \quad t_1 = 1 \end{align*}$$

Теперь выполняем итерации:

$$\begin{align*} r_2 &= r_0 \bmod r_1 = 45 \bmod 29 = 16 \\ s_2 &= s_0 - \left(\frac{r_0}{r_1}\right) s_1 = 1 - \left(\frac{45}{29}\right) \cdot 0 = 1 \\ t_2 &= t_0 - \left(\frac{r_0}{r_1}\right) t_1 = 0 - \left(\frac{45}{29}\right) \cdot 1 = -1 \end{align*}$$

Теперь обновляем значения:

$$\begin{align*} r_0 &= r_1, \quad r_1 &= r_2 \\ s_0 &= s_1, \quad s_1 &= s_2 \\ t_0 &= t_1, \quad t_1 &= t_2 \end{align*}$$

И продолжаем итерации:

$$\begin{align*} r_2 &= r_0 - \left(\frac{r_0}{r_1}\right) r_1 = 29 - \left(\frac{29}{16}\right) \cdot 16 = 0 \\ s_2 &= s_0 - \left(\frac{r_0}{r_1}\right) s_1 = 0 - \left(\frac{29}{16}\right) \cdot 1 = -2 \\ t_2 &= t_0 - \left(\frac{r_0}{r_1}\right) t_1 = 1 - \left(\frac{29}{16}\right) \cdot (-1) = 2 \end{align*}$$