Решите уравнение x²+1=0 mod 625.

Брат, давай по шагам для mod 625 = 5⁴, чтобы было чисто и без лишнего треша.

Уравнение:

x2+1≡0(mod625)  ⟹  x2≡−1≡624(mod625).x^2 + 1 \equiv 0 \pmod{625} \implies x^2 \equiv -1 \equiv 624 \pmod{625}.x2+1≡0(mod625)⟹x2≡−1≡624(mod625).

1. Начнем с мод 5

x2≡−1≡4(mod5).x^2 \equiv -1 \equiv 4 \pmod{5}.x2≡−1≡4(mod5).

Квадраты по мод 5:
0² ≡ 0, 1² ≡ 1, 2² ≡ 4 ✅, 3² ≡ 4 ✅, 4² ≡ 1

→ решения:

x≡2,3(mod5).x \equiv 2, 3 \pmod{5}.x≡2,3(mod5).

2. Поднимаем решение до 25 (5²)

Ищем x≡a+5b(mod25)x \equiv a + 5b \pmod{25}x≡a+5b(mod25)

a = 2:

(2+5b)2=4+20b≡24(mod25)(2 + 5b)^2 = 4 + 20b \equiv 24 \pmod{25}(2+5b)2=4+20b≡24(mod25)
20b ≡ 20 → b ≡ 1 → x ≡ 2 + 5*1 = 7

a = 3:

(3+5b)2=9+30b≡9+5b(mod25)(3 + 5b)^2 = 9 + 30b ≡ 9 + 5b \pmod{25}(3+5b)2=9+30b≡9+5b(mod25)
9 + 5b ≡ 24 → 5b ≡ 15 → b ≡ 3 → x ≡ 3 + 5*3 = 18

✅ Решения mod 25:

x≡7,18(mod25)x \equiv 7, 18 \pmod{25}x≡7,18(mod25)

3. Поднимаем решение до 125 (5³)

x = x₀ + 25k

x₀ = 7:

(7+25k)2≡49+350k≡?(mod125)(7 + 25k)^2 \equiv 49 + 350k \equiv ? \pmod{125}(7+25k)2≡49+350k≡?(mod125)
49 + 350k ≡ 49 + 100k ≡ ?

-49 + 100k ≡ 124 → 100k ≡ 75 → 20k ≡ 15 → k ≡ 4 mod 5? Давай проверим аккуратно:

100k ≡ 75 mod 125 → делим на 25: 4k ≡ 3 → k ≡ 4 mod 5 ✅
x ≡ 7 + 25*4 = 107 mod 125

x₀ = 18:

(18 + 25k)^2 ≡ 324 + 900k ≡ 324 + 25k mod 125?
900 ≡ 25 → 324 + 25k ≡ 124 → 25k ≡ -200 ≡ 50 → k ≡ 2 mod 5
x ≡ 18 + 25*2 = 68 mod 125

✅ Решения mod 125:

x≡107,68(mod125)x \equiv 107, 68 \pmod{125}x≡107,68(mod125)

4. Поднимаем до 625 (5⁴)

x = x₀ + 125 s

x₀ = 107:

(107 + 125 s)^2 ≡ 11449 + 26750 s mod 625
11449 mod 625 = 11449 - 62518=11449-11250=199
26750 ≡ 26750-62542=26750-26250=500 →
199 + 500 s ≡ 624 → 500 s ≡ 425 → 500 ≡ -125 → -125 s ≡ 425 → 125 s ≡ 200 → s ≡ 200/125 ≡ 1.6 ???

Брат, делаем аккуратнее: 125 s ≡ 200 mod 625 → 125*? ≡ 200 → 125*? ≡ 200 → 1251 = 125, 1252 = 250 → 200 между ними → решение не целое?

Да, точно — мы должны использовать метод подъема решений по степеням 5 аккуратно:

• Берём x = x₀ + 125 s

• Уравнение: (x₀ + 125s)² ≡ x₀² + 2125x₀*s ≡ x₀² + 250 x₀ s mod 625

x₀ = 107: x₀² = 11449 → 11449 mod 625: 62518=11250 → 11449-11250=199 ✅
2125107=2125107=26750 → mod 625: 62542=26250 → 26750-26250=500 ✅

Уравнение: 199 + 500 s ≡ 624 → 500 s ≡ 425 mod 625

• 500 ≡ -125 → -125 s ≡ 425 → 125 s ≡ 200 → 125 s ≡ 200 mod 625

125*? ≡ 200 → 1251=125, 1252=250 → решения нет целого?

Да, братан, вот тут важно заметить: уравнение x² ≡ -1 mod 5⁴ = 625 не имеет решения!

✅ Вывод

• x² ≡ -1 mod 5 → есть решение

• x² ≡ -1 mod 25 → есть решение

• x² ≡ -1 mod 125 → есть решение

• x² ≡ -1 mod 625 → решений нет

То есть уравнение x² + 1 ≡ 0 mod 625 не имеет целых решений.