Чтобы решить уравнение ( x^2 \equiv 4 \mod{10^5} ), мы можем использовать разложение на простые множители. Мы знаем, что ( 10^5 = 2^5 \cdot 5^5 ).

Мы будем решать уравнение по модулю ( 2^5 ) и ( 5^5 ), а затем использовать теорему китайского остатка для получения общего решения.

Шаг 1: Решение по модулю ( 2^5 )

Решаем уравнение ( x^2 \equiv 4 \mod{32} ):

[
x^2 - 4 \equiv 0 \mod{32}
]

или

[
(x - 2)(x + 2) \equiv 0 \mod{32}
]

Это означает, что ( x \equiv 2 \mod{32} ) или ( x \equiv -2 \equiv 30 \mod{32} ).

Шаг 2: Решение по модулю ( 5^5 )

Теперь решаем уравнение ( x^2 \equiv 4 \mod{3125} ). Давайте запишем уравнение:

[
x^2 - 4 \equiv 0 \mod{3125}
]

или

[
(x - 2)(x + 2) \equiv 0 \mod{3125}
]

Это также дает нам два решения:

[
x \equiv 2 \mod{3125} \quad \text{или} \quad x \equiv -2 \equiv 3123 \mod{3125}
]

Шаг 3: Системы уравнений

Теперь у нас есть четыре сочетания решений:

( x \equiv 2 \mod{32} ) и ( x \equiv 2 \mod{3125} )( x \equiv 2 \mod{32} ) и ( x \equiv 3123 \mod{3125} )( x \equiv 30 \mod{32} ) и ( x \equiv 2 \mod{3125} )( x \equiv 30 \mod{32} ) и ( x \equiv 3123 \mod{3125} )Шаг 4: Решаем каждую пару1. ( x \equiv 2 \mod{32} ), ( x \equiv 2 \mod{3125} )

По теореме китайского остатка:

[
x \equiv 2 \mod{10^5}
]

2. ( x \equiv 2 \mod{32} ), ( x \equiv 3123 \mod{3125} )

Решаем систему:

[
x = 3125k + 3123
]

Подставляем в первое уравнение:

[
3125k + 3123 \equiv 2 \mod{32}
]

Обозначаем ( 3125 \mod{32} ):

[
3125 \equiv 21 \mod{32}, \quad 3123 \equiv 19 \mod{32}
]

Таким образом:

[
21k + 19 \equiv 2 \mod{32} \implies 21k \equiv -17 \equiv 15 \mod{32}
]

Находим обратный элемент к ( 21 \mod{32} ), который равен ( 29 ):

[
k \equiv 15 \cdot 29 \mod{32} \implies k \equiv 435 \mod{32} \implies k \equiv 11 \mod{32}
]

Таким образом:

[
x = 3125(32m + 11) + 3123 = 100000m + 34348
]

3. ( x \equiv 30 \mod{32} ), ( x \equiv 2 \mod{3125} )

Записываем систему:

[
x = 3125k + 2
]

Подставляем в первое уравнение:

[
3125k + 2 \equiv 30 \mod{32} \implies 21k + 2 \equiv 30 \mod{32} \implies 21k \equiv 28 \mod{32}
]

Находим:

[
k \equiv 28 \cdot 29 \mod{32} \equiv 812 \mod{32} \implies k \equiv 28 \mod{32}
]

Таким образом:

[
x = 3125(32m + 28) + 2 = 100000m + 87552
]

4. ( x \equiv 30 \mod{32} ), ( x \equiv 3123 \mod{3125} )

[
x = 3125k + 3123
]

Подставляем в первое уравнение:

[
3125k + 3123 \equiv 30 \mod{32} \implies 21k + 19 \equiv 30 \mod{32}
]

[
21k \equiv 11 \mod{32}
]

Итак, находим:

[
k \equiv 11 \cdot 29 \mod{32} \equiv 319 \mod{32} \implies k \equiv 31 \mod{32}
]

Получаем:

[
x = 3125(32m + 31) + 3123 = 100000m + 99948
]

Ответ

Теперь мы имеем четыре решения:

( x \equiv 2 \mod{100000} )( x \equiv 87552 \mod{100000} )( x \equiv 34348 \mod{100000} )( x \equiv 99948 \mod{100000} )

Таким образом, все решения уравнения ( x^2 \equiv 4 \mod{100000} ).