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

Братан, ща разберём аккуратно шаг за шагом. Уравнение:

x2+1≡0(mod3125)x^2 + 1 \equiv 0 \pmod{3125}x2+1≡0(mod3125)

то есть

x2≡−1≡3124(mod3125).x^2 \equiv -1 \equiv 3124 \pmod{3125}.x2≡−1≡3124(mod3125).

1. Разложим модуль на степень простого числа

3125 = 555^555. Значит, решаем:

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

2. Сначала проверим по модулю 5

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

Квадраты по модулю 5:

• 02≡00^2 \equiv 002≡0

• 12≡11^2 \equiv 112≡1

• 22≡42^2 \equiv 422≡4 ✅

• 32≡43^2 \equiv 432≡4 ✅

• 42≡14^2 \equiv 142≡1

То есть по модулю 5 есть решения:

x≡2 или x≡3(mod5).x \equiv 2 \text{ или } x \equiv 3 \pmod{5}.x≡2 или x≡3(mod5).

3. Поднимаем решение до 52=255^2 = 2552=25 (метод Гуа)

Ищем x≡a+5b(mod25)x \equiv a + 5b \pmod{25}x≡a+5b(mod25) с a=2a = 2a=2 или 333.
Уравнение:

(a+5b)2≡−1(mod25)  ⟹  a2+10ab+25b2≡a2+10ab≡−1(mod25).(a + 5b)^2 \equiv -1 \pmod{25} \implies a^2 + 10ab + 25b^2 \equiv a^2 + 10ab \equiv -1 \pmod{25}.(a+5b)2≡−1(mod25)⟹a2+10ab+25b2≡a2+10ab≡−1(mod25).

Случай a = 2

22+10b⋅2≡4+20b≡−1≡24(mod25)2^2 + 10b \cdot 2 \equiv 4 + 20b \equiv -1 \equiv 24 \pmod{25} 22+10b⋅2≡4+20b≡−1≡24(mod25)20b≡20(mod25)  ⟹  20b≡20(mod25)20b \equiv 20 \pmod{25} \implies 20b \equiv 20 \pmod{25}20b≡20(mod25)⟹20b≡20(mod25)

Разделим на 5:

4b≡4(mod5)  ⟹  b≡1(mod5).4b \equiv 4 \pmod{5} \implies b \equiv 1 \pmod{5}.4b≡4(mod5)⟹b≡1(mod5).

То есть b=1b = 1b=1, получаем x≡2+5⋅1=7(mod25)x \equiv 2 + 5 \cdot 1 = 7 \pmod{25}x≡2+5⋅1=7(mod25).

Случай a = 3

32+10⋅3b≡9+30b≡9+5b(mod25)(30b ≡ 5b mod 25)3^2 + 10 \cdot 3 b \equiv 9 + 30b \equiv 9 + 5b \pmod{25} \quad (\text{30b ≡ 5b mod 25})32+10⋅3b≡9+30b≡9+5b(mod25)(30b ≡ 5b mod 25)9+5b≡24  ⟹  5b≡15  ⟹  b≡3(mod5)9 + 5b \equiv 24 \implies 5b \equiv 15 \implies b \equiv 3 \pmod{5}9+5b≡24⟹5b≡15⟹b≡3(mod5)

Тогда x≡3+5⋅3=18(mod25)x \equiv 3 + 5 \cdot 3 = 18 \pmod{25}x≡3+5⋅3=18(mod25).

✅ Итак, решения по модулю 25:

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

4. Поднимаем решение до 53=1255^3 = 12553=125

Ищем x=x0+25kx = x_0 + 25kx=x0​+25k где x0=7x_0 = 7x0​=7 или 181818:

(7+25k)2≡−1(mod125)(7 + 25k)^2 \equiv -1 \pmod{125}(7+25k)2≡−1(mod125)

49+350k+625k2≡49+350k≡124(mod125)(таккак−1≡124mod125)49 + 350k + 625 k^2 \equiv 49 + 350k \equiv 124 \pmod{125} \quad (так как -1 ≡ 124 mod 125)49+350k+625k2≡49+350k≡124(mod125)(таккак−1≡124mod125)350k≡75(mod125)  ⟹  350k≡75(mod125)350k \equiv 75 \pmod{125} \implies 350k ≡ 75 \pmod{125}350k≡75(mod125)⟹350k≡75(mod125)

350 ≡ 100 ≡ -25 mod 125

−25k≡75  ⟹  25k≡−75≡50  ⟹  k≡2(mod5)-25k \equiv 75 \implies 25k \equiv -75 ≡ 50 \implies k \equiv 2 \pmod{5}−25k≡75⟹25k≡−75≡50⟹k≡2(mod5)

⇒x≡7+25⋅2=57(mod125)\Rightarrow x \equiv 7 + 25 \cdot 2 = 57 \pmod{125}⇒x≡7+25⋅2=57(mod125)

Случай x₀ = 18:

(18+25k)2≡−1(mod125)  ⟹  324+900k≡124  ⟹  900k≡−200≡50(mod125)(18 + 25k)^2 \equiv -1 \pmod{125} \implies 324 + 900k \equiv 124 \implies 900k \equiv -200 \equiv 50 \pmod{125}(18+25k)2≡−1(mod125)⟹324+900k≡124⟹900k≡−200≡50(mod125)

900 ≡ 25 mod 125 → 25k ≡ 50 → k ≡ 2
⇒x≡18+50=68(mod125)\Rightarrow x \equiv 18 + 50 = 68 \pmod{125}⇒x≡18+50=68(mod125)

✅ Решения по модулю 125:

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

5. Поднимаем до 54=6255^4 = 62554=625

x = 57 + 125t:

(57+125t)2≡−1(mod625)  ⟹  3249+14250t≡624(mod625)(57 + 125 t)^2 \equiv -1 \pmod{625} \implies 3249 + 14250 t \equiv 624 \pmod{625}(57+125t)2≡−1(mod625)⟹3249+14250t≡624(mod625)

3249 mod 625 = 3249 - 5*625 = 3249 - 3125 = 124 →
14250 t ≡ 624 - 124 = 500 mod 625

14250 ≡ 14250 - 22625 = 14250 - 13750 = 500 → 500 t ≡ 500 mod 625 → t ≡ 1 mod 5
x = 57 + 1251 = 182 mod 625

x = 68 + 125t:
(68 + 125t)^2 → 4624 + 17000 t
4624 mod 625: 4624 - 7625 = 4624 - 4375 = 249
17000 ≡ 17000 - 27625 = 17000 - 16875 = 125

Уравнение: 249 + 125 t ≡ 624 → 125 t ≡ 375 → t ≡ 3
x = 68 + 125*3 = 68 + 375 = 443 mod 625

✅ Решения по модулю 625:

x≡182,443(mod625)x \equiv 182, 443 \pmod{625}x≡182,443(mod625)

6. Поднимаем до 55=31255^5 = 312555=3125

x = 182 + 625 s → (182 + 625 s)^2 ≡ -1 mod 3125
182² = 33124 mod 3125 → 182² = 33124 - 10*3125=33124-31250=1874?

Проверим: 182² = 33124
33124 mod 3125: 3125*10=31250 → 33124-31250=1874 ✅

2182625 s = 227500 s ≡ ? 227500 mod 3125
312572 = 225000 → 227500-225000=2500
x² = 182² + 2182625s ≡ 1874 + 2500 s ≡ -1 ≡ 3124 mod 3125

Уравнение: 1874 + 2500 s ≡ 3124 → 2500 s ≡ 1250 → 2500 ≡ -625 → -625 s ≡ 1250 → 625 s ≡ -1250 ≡ 1875 → s ≡ 3
x = 182 + 625*3 = 182 + 1875 = 2057 mod 3125

x = 443 + 625 s → 443² = 196249
196249 mod 3125 → 312562=193750 → 196249-193750=2499
2443625s= 553750s → mod 3125: 3125177=553125 → 553750-553125=625 s
x² ≡ 2499 + 625 s ≡ 3124 → 625 s ≡ 625 → s ≡ 1
x = 443 + 625*1 = 1068 mod 3125

✅ Ответ

x≡2057,1068(mod3125)\boxed{x \equiv 2057, 1068 \pmod{3125}}x≡2057,1068(mod3125)​