Решить квадратное сравнение 17x2 + 14x + 18 = 0 mod 19 21x2 + 12x + 13 = 0 mod 23 6x2 + 26x + 3 = 0 mod 29 34x2 + 13x + 23 = 0 mod 37

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

1. Уравнение: $17x^2 + 14x + 18 \equiv 0 \mod 19$

Шаг 1: Приведем уравнение к стандартному виду.
Поскольку 19 — простое число, мы можем работать с коэффициентами напрямую.

Шаг ... Дискриминант $D = b^2 - 4ac$: $ D = 14^2 - 4 \cdot 17 \cdot 18 \equiv 196 - 1224 \mod 19 $ Сначала вычислим $1224 \mod 19$: $ 1224 \div 19 \approx 64.42 \quad \Rightarrow \quad 64 \cdot 19 = 1216 \quad \Rightarrow \quad 1224 - 1216 = 8 $ Теперь подставим: $ D \equiv 196 - 8 \equiv 188 \mod 19 $ Теперь вычислим $188 \mod 19$: $ 188 \div 19 \approx 9.89 \quad \Rightarrow \quad 9 \cdot 19 = 171 \quad \Rightarrow \quad 188 - 171 = 17 $ Таким образом, $D \equiv 17 \mod 19$.

Проверим все квадраты от 0 до 18:

• $0^2 \equiv 0$
• $1^2 \equiv 1$
• $2^2 \equiv 4$
• $3^2 \equiv 9$
• $4^2 \equiv 16$
• $5^2 \equiv 6$
• $6^2 \equiv 7$
• $7^2 \equiv 7$
• $8^2 \equiv 6$
• $9^2 \equiv 16$
• $10^2 \equiv 9$
• $11^2 \equiv 4$
• $12^2 \equiv 1$
• $13^2 \equiv 0$

17 не является квадратом по модулю 19, следовательно, уравнение не имеет решений.

Коэффициенты уже в нужном виде.

$$D = 12^2 - 4 \cdot 21 \cdot 13 \equiv 144 - 1092 \mod 23$$

Сначала вычислим $1092 \mod 23$:

$$1092 \div 23 \approx 47.48 \quad \Rightarrow \quad 47 \cdot 23 = 1081 \quad \Rightarrow \quad 1092 - 1081 = 11$$

Теперь подставим:

$$D \equiv 144 - 11 \equiv 133 \mod 23$$

Теперь вычислим $133 \mod 23$:

$$133 \div 23 \approx 5.78 \quad \Rightarrow \quad 5 \cdot 23 = 115 \quad \Rightarrow \quad 133 - 115 = 18$$

Таким образом, $D \equiv 18 \mod 23$.

Проверим все квадраты от 0 до 22:

• $0^2 \equiv 0$
• $1^2 \equiv 1$
• $2^2 \equiv 4$
• $3^2 \equiv 9$
• $4^2 \equiv 16$
• $5^2 \equiv 2$
• $6^2 \equiv 13$
• $7^2 \equiv 3$
• $8^2 \equiv 18$

18 является квадратом (например, $8^2$), следовательно, уравнение имеет решения.

Корни находятся по формуле:

$$x \equiv \frac{-b \pm \sqrt{D}}{2a} \mod p$$

Где $\sqrt{D} \equiv 8 \mod 23$:

$$x \equiv \frac{-12 \pm 8}{2 \cdot 21} \mod 23$$

Сначала найдем $2 \cdot 21 \mod 23$:

$$42 \mod 23 \equiv 19$$

Теперь подставим:

$$x \equiv \frac{-12 \pm 8}{19} \mod 23$$

Решим два случая:

1. $x \equiv \frac{-4}{19} \mod 23$
2. $x \equiv \frac{-20}{19} \mod 23$

Для нахождения обратного элемента 19 по модулю 23, используем расширенный алгоритм Евклида. Обратный элемент $19^{-1} \equiv 17 \mod 23$.

Теперь подставим:

1. $x \equiv -4 \cdot 17 \mod 23 \equiv -68 \mod 23 \equiv 12$
2. $x \equiv -20 \cdot 17 \mod 23 \equiv -340 \mod 23 \equiv 6$

Таким образом, решения: $x \equiv 12$ и $x \equiv 6 \mod 23$.

Коэффициенты уже в нужном виде.

$$D = 26^2 - 4 \cdot 6 \cdot 3 \equiv 676 - 72 \mod 29$$

Сначала вычислим $72 \mod 29$:

$$72 \div 29 \approx 2.48 \quad \Rightarrow \quad 2 \cdot 29 = 58 \quad \Rightarrow \quad 72 - 58 = 14$$

Теперь подставим:

$$D \equiv 676 - 14 \equiv 662 \mod 29$$

Теперь вычислим $662 \mod 29$:

$$662 \div 29 \approx 22.83 \quad \Rightarrow \quad 22 \cdot 29 = 638 \quad \Rightarrow \quad 662 - 638 = 24$$

Таким образом, $D \equiv 24 \mod 29$.

Проверим все квадраты от 0 до 28:

• $0^2 \equiv 0$
• $1^2 \equiv 1$
• $2^2 \equiv 4$
• $3^2 \equiv 9$
• $4^2 \equiv 16$
• $5^2 \equiv 25$
• $6^2 \equiv 7$
• $7^2 \equiv 25$
• $8^2 \equiv 24$

24 является квадратом (например, $8^2$), следовательно, уравнение имеет решения.

Корни находятся по формуле:

$$x \equiv \frac{-b \pm \sqrt{D}}{2a} \mod p$$

Где $\sqrt{D} \equiv 8 \mod 29$:

$$x \equiv \frac{-26 \pm 8}{2 \cdot 6} \mod 29$$

Сначала найдем $2 \cdot 6 \mod 29$:

$$12 \mod 29 \equiv 12$$

Теперь подставим:

$$x \equiv \frac{-26 \pm 8}{12} \mod 29$$

Решим два случая:

1. $x \equiv \frac{-18}{12} \mod 29$
2. $x \equiv \frac{-34}{12} \mod 29$

Для нахождения обратного элемента 12 по модулю 29, используем расширенный алгоритм Евклида. Обратный элемент $12^{-1} \equiv 17 \mod 29$.

Теперь подставим:

1. $x \equiv -18 \cdot 17 \mod 29 \equiv -306 \mod 29 \equiv 11$
2. $x \equiv -34 \cdot 17 \mod 29 \equiv -578 \mod 29 \equiv 4$

Таким образом, решения: $x \equiv 11$ и $x \equiv 4 \mod 29$.

Коэффициенты уже в нужном виде.

$$D = 13^2 - 4 \cdot 34 \cdot 23 \equiv 169 - 3128 \mod 37$$

Сначала вычислим $3128 \mod 37$:

$$3128 \div 37 \approx 84.62 \quad \Rightarrow \quad 84 \cdot 37 = 3108 \quad \Rightarrow \quad 3128 - 3108 = 20$$

Теперь подставим:

$$D \equiv 169 - 20 \equiv 149 \mod 37$$

Теперь вычислим $149 \mod 37$:

$$149 \div 37 \approx 4.02 \quad \Rightarrow \quad 4 \cdot 37 = 148 \quad \Rightarrow \quad 149 - 148 = 1$$

Таким образом, $D \equiv 1 \mod 37$.

1 является квадратом, следовательно, уравнение имеет решения.

Корни находятся по формуле:

$$x \equiv \frac{-b \pm \sqrt{D}}{2a} \mod p$$

Где $\sqrt{D} \equiv 1 \mod 37$:

$$x \equiv \frac{-13 \pm 1}{2 \cdot 34} \mod 37$$

Сначала найдем $2 \cdot 34 \mod 37$:

$$68 \mod 37 \equiv 31$$

Теперь подставим:

$$x \equiv \frac{-13 \pm 1}{31} \mod 37$$

Решим два случая:

1. $x \equiv \frac{-12}{31} \mod 37$
2. $x \equiv \frac{-14}{31} \mod 37$

Для нахождения обратного элемента 31 по модулю 37, используем расширенный алгоритм Евклида. Обратный элемент $31^{-1} \equiv 6 \mod 37$.

Теперь подставим:

1. $x \equiv -12 \cdot 6 \mod 37 \equiv -72 \mod 37 \equiv 2$
2. $x \equiv -14 \cdot 6 \mod 37 \equiv -84 \mod 37 \equiv 10$

Таким образом, решения: $x \equiv 2$ и $x \equiv 10 \mod 37$.

1. $17x^2 + 14x + 18 \equiv 0 \mod 19$ — нет решений.
2. $21x^2 + 12x + 13 \equiv 0 \mod 23$ — решения: $x \equiv 12, 6 \mod 23$.
3. $6x^2 + 26x + 3 \equiv 0 \mod 29$ — решения: $x \equiv 11, 4 \mod 29$.
4. $34x^2 + 13x + 23 \equiv 0 \mod 37$ — решения: $x \equiv 2, 10 \mod 37$.