Чтобы решить уравнение x2≡4mod 105 x^2 \equiv 4 \mod{10^5} x2≡4mod105, мы можем использовать разложение на простые множители. Мы знаем, что 105=25⋅55 10^5 = 2^5 \cdot 5^5 105=25⋅55.
Мы будем решать уравнение по модулю 25 2^5 25 и 55 5^5 55, а затем использовать теорему китайского остатка для получения общего решения.
Чтобы решить уравнение x2≡4mod 105 x^2 \equiv 4 \mod{10^5} x2≡4mod105, мы можем использовать разложение на простые множители. Мы знаем, что 105=25⋅55 10^5 = 2^5 \cdot 5^5 105=25⋅55.
Мы будем решать уравнение по модулю 25 2^5 25 и 55 5^5 55, а затем использовать теорему китайского остатка для получения общего решения.
Шаг 1: Решение по модулю 25 2^5 25Решаем уравнение x2≡4mod 32 x^2 \equiv 4 \mod{32} x2≡4mod32:
x2−4≡0mod 32 x^2 - 4 \equiv 0 \mod{32}
x2−4≡0mod32
или
(x−2)(x+2)≡0mod 32 (x - 2)(x + 2) \equiv 0 \mod{32}
(x−2)(x+2)≡0mod32
Это означает, что x≡2mod 32 x \equiv 2 \mod{32} x≡2mod32 или x≡−2≡30mod 32 x \equiv -2 \equiv 30 \mod{32} x≡−2≡30mod32.
Шаг 2: Решение по модулю 55 5^5 55Теперь решаем уравнение x2≡4mod 3125 x^2 \equiv 4 \mod{3125} x2≡4mod3125. Давайте запишем уравнение:
x2−4≡0mod 3125 x^2 - 4 \equiv 0 \mod{3125}
x2−4≡0mod3125
или
(x−2)(x+2)≡0mod 3125 (x - 2)(x + 2) \equiv 0 \mod{3125}
(x−2)(x+2)≡0mod3125
Это также дает нам два решения:
x≡2mod 3125илиx≡−2≡3123mod 3125 x \equiv 2 \mod{3125} \quad \text{или} \quad x \equiv -2 \equiv 3123 \mod{3125}
Шаг 3: Системы уравненийx≡2mod3125илиx≡−2≡3123mod3125
Теперь у нас есть четыре сочетания решений:
x≡2mod 32 x \equiv 2 \mod{32} x≡2mod32 и x≡2mod 3125 x \equiv 2 \mod{3125} x≡2mod3125x≡2mod 32 x \equiv 2 \mod{32} x≡2mod32 и x≡3123mod 3125 x \equiv 3123 \mod{3125} x≡3123mod3125x≡30mod 32 x \equiv 30 \mod{32} x≡30mod32 и x≡2mod 3125 x \equiv 2 \mod{3125} x≡2mod3125x≡30mod 32 x \equiv 30 \mod{32} x≡30mod32 и x≡3123mod 3125 x \equiv 3123 \mod{3125} x≡3123mod3125Шаг 4: Решаем каждую пару1. x≡2mod 32 x \equiv 2 \mod{32} x≡2mod32, x≡2mod 3125 x \equiv 2 \mod{3125} x≡2mod3125По теореме китайского остатка:
x≡2mod 105 x \equiv 2 \mod{10^5}
2. x≡2mod 32 x \equiv 2 \mod{32} x≡2mod32, x≡3123mod 3125 x \equiv 3123 \mod{3125} x≡3123mod3125x≡2mod105
Решаем систему:
x=3125k+3123 x = 3125k + 3123
x=3125k+3123
Подставляем в первое уравнение:
3125k+3123≡2mod 32 3125k + 3123 \equiv 2 \mod{32}
3125k+3123≡2mod32
Обозначаем 3125mod 32 3125 \mod{32} 3125mod32:
3125≡21mod 32,3123≡19mod 32 3125 \equiv 21 \mod{32}, \quad 3123 \equiv 19 \mod{32}
3125≡21mod32,3123≡19mod32
Таким образом:
21k+19≡2mod 32 ⟹ 21k≡−17≡15mod 32 21k + 19 \equiv 2 \mod{32} \implies 21k \equiv -17 \equiv 15 \mod{32}
21k+19≡2mod32⟹21k≡−17≡15mod32
Находим обратный элемент к 21mod 32 21 \mod{32} 21mod32, который равен 29 29 29:
k≡15⋅29mod 32 ⟹ k≡435mod 32 ⟹ k≡11mod 32 k \equiv 15 \cdot 29 \mod{32} \implies k \equiv 435 \mod{32} \implies k \equiv 11 \mod{32}
k≡15⋅29mod32⟹k≡435mod32⟹k≡11mod32
Таким образом:
x=3125(32m+11)+3123=100000m+34348 x = 3125(32m + 11) + 3123 = 100000m + 34348
3. x≡30mod 32 x \equiv 30 \mod{32} x≡30mod32, x≡2mod 3125 x \equiv 2 \mod{3125} x≡2mod3125x=3125(32m+11)+3123=100000m+34348
Записываем систему:
x=3125k+2 x = 3125k + 2
x=3125k+2
Подставляем в первое уравнение:
3125k+2≡30mod 32 ⟹ 21k+2≡30mod 32 ⟹ 21k≡28mod 32 3125k + 2 \equiv 30 \mod{32} \implies 21k + 2 \equiv 30 \mod{32} \implies 21k \equiv 28 \mod{32}
3125k+2≡30mod32⟹21k+2≡30mod32⟹21k≡28mod32
Находим:
k≡28⋅29mod 32≡812mod 32 ⟹ k≡28mod 32 k \equiv 28 \cdot 29 \mod{32} \equiv 812 \mod{32} \implies k \equiv 28 \mod{32}
k≡28⋅29mod32≡812mod32⟹k≡28mod32
Таким образом:
x=3125(32m+28)+2=100000m+87552 x = 3125(32m + 28) + 2 = 100000m + 87552
4. x≡30mod 32 x \equiv 30 \mod{32} x≡30mod32, x≡3123mod 3125 x \equiv 3123 \mod{3125} x≡3123mod3125x=3125(32m+28)+2=100000m+87552
x=3125k+3123 x = 3125k + 3123
x=3125k+3123
Подставляем в первое уравнение:
3125k+3123≡30mod 32 ⟹ 21k+19≡30mod 32 3125k + 3123 \equiv 30 \mod{32} \implies 21k + 19 \equiv 30 \mod{32}
3125k+3123≡30mod32⟹21k+19≡30mod32
21k≡11mod 32 21k \equiv 11 \mod{32}
21k≡11mod32
Итак, находим:
k≡11⋅29mod 32≡319mod 32 ⟹ k≡31mod 32 k \equiv 11 \cdot 29 \mod{32} \equiv 319 \mod{32} \implies k \equiv 31 \mod{32}
k≡11⋅29mod32≡319mod32⟹k≡31mod32
Получаем:
x=3125(32m+31)+3123=100000m+99948 x = 3125(32m + 31) + 3123 = 100000m + 99948
Ответx=3125(32m+31)+3123=100000m+99948
Теперь мы имеем четыре решения:
x≡2mod 100000 x \equiv 2 \mod{100000} x≡2mod100000x≡87552mod 100000 x \equiv 87552 \mod{100000} x≡87552mod100000x≡34348mod 100000 x \equiv 34348 \mod{100000} x≡34348mod100000x≡99948mod 100000 x \equiv 99948 \mod{100000} x≡99948mod100000Таким образом, все решения уравнения x2≡4mod 100000 x^2 \equiv 4 \mod{100000} x2≡4mod100000.