Теперь найдем 444mod 125 444 \mod 125 444mod125: 444÷125=3(остаток 69)
444 \div 125 = 3 \quad \text{(остаток 69)} 444÷125=3(остаток 69)
Таким образом: 444≡69mod 125
444 \equiv 69 \mod 125 444≡69mod125
Теперь решим x2≡69mod 125 x^2 \equiv 69 \mod 125 x2≡69mod125.
Для этого определим, является ли 69 квадратным числом по модулю 125. Убедимся, что 69 69 69 является квадратом, проверив все числа от 0 0 0 до 124 124 124.
При проверке чисел, можно также использовать алгоритм Ханнинга или искать корни шаг за шагом.
При вычислениях найдём, что: 182≡324≡69mod 125
18^2 \equiv 324 \equiv 69 \mod 125 182≡324≡69mod125
А также, так как (125−18)=107 (125 - 18) = 107 (125−18)=107: 1072≡69mod 125
107^2 \equiv 69 \mod 125 1072≡69mod125
Таким образом, решения по модулю 125: x≡18mod 125илиx≡107mod 125
x \equiv 18 \mod 125 \quad \text{или} \quad x \equiv 107 \mod 125 x≡18mod125илиx≡107mod125
Шаг 3: Комбинирование решений с помощью китайской теоремы об остатках
Итак, у нас есть 4 случая по модулю 1000 1000 1000:
x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡18mod 125 x \equiv 18 \mod 125 x≡18mod125x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡107mod 125 x \equiv 107 \mod 125 x≡107mod125x≡6mod 8 x \equiv 6 \mod 8 x≡6mod8 и x≡18mod 125 x \equiv 18 \mod 125 x≡18mod125x≡6mod 8 x \equiv 6 \mod 8 x≡6mod8 и x≡107mod 125 x \equiv 107 \mod 125 x≡107mod125
Решим каждый из этих случаев.
Случай 1:
x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡18mod 125 x \equiv 18 \mod 125 x≡18mod125.
Для этого будем искать x=125k+18 x = 125k + 18 x=125k+18: 125k+18≡2mod 8 ⟹ 5k+2≡2mod 8 ⟹ 5k≡0mod 8
125k + 18 \equiv 2 \mod 8 \implies 5k + 2 \equiv 2 \mod 8 \implies 5k \equiv 0 \mod 8 125k+18≡2mod8⟹5k+2≡2mod8⟹5k≡0mod8
Решение k≡0mod 8 k \equiv 0 \mod 8k≡0mod8 даёт k=8m k = 8m k=8m: x=125(8m)+18=1000m+18
x = 125(8m) + 18 = 1000m + 18 x=125(8m)+18=1000m+18
Следовательно, одно из решений: x≡18mod 1000
x \equiv 18 \mod 1000 x≡18mod1000
Случай 2:
x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡107mod 125 x \equiv 107 \mod 125 x≡107mod125:
Чтобы решить уравнение x2≡444mod 1000 x^2 \equiv 444 \mod 1000 x2≡444mod1000, первым делом нужно найти все квадратные корни из 444 по модулю 1000.
Разложим 1000 на простые множители:
1000=23⋅53 1000 = 2^3 \cdot 5^3
1000=23⋅53
Используя теорему о китайской теореме об остатках, сначала найдем корни x2≡444 x^2 \equiv 444 x2≡444 по модулю 8 8 8 и 125 125 125.
Шаг 1: Решение по модулю 8Сначала упростим 444mod 8 444 \mod 8 444mod8:
Шаг 2: Решение по модулю 125444÷8=55(остаток 4) 444 \div 8 = 55 \quad \text{(остаток 4)}
444÷8=55(остаток 4) Следовательно:
444≡4mod 8 444 \equiv 4 \mod 8
444≡4mod8 Теперь решим x2≡4mod 8 x^2 \equiv 4 \mod 8 x2≡4mod8. Возможные решения:
x≡2mod 8илиx≡6mod 8 x \equiv 2 \mod 8 \quad \text{или} \quad x \equiv 6 \mod 8
x≡2mod8илиx≡6mod8
Теперь найдем 444mod 125 444 \mod 125 444mod125:
444÷125=3(остаток 69) 444 \div 125 = 3 \quad \text{(остаток 69)}
444÷125=3(остаток 69) Таким образом:
444≡69mod 125 444 \equiv 69 \mod 125
444≡69mod125 Теперь решим x2≡69mod 125 x^2 \equiv 69 \mod 125 x2≡69mod125.
Для этого определим, является ли 69 квадратным числом по модулю 125. Убедимся, что 69 69 69 является квадратом, проверив все числа от 0 0 0 до 124 124 124.
При проверке чисел, можно также использовать алгоритм Ханнинга или искать корни шаг за шагом.
02≡0 0^2 \equiv 0 02≡012≡1 1^2 \equiv 1 12≡122≡4 2^2 \equiv 4 22≡432≡9 3^2 \equiv 9 32≡9и так далее...При вычислениях найдём, что:
182≡324≡69mod 125 18^2 \equiv 324 \equiv 69 \mod 125
182≡324≡69mod125 А также, так как (125−18)=107 (125 - 18) = 107 (125−18)=107:
1072≡69mod 125 107^2 \equiv 69 \mod 125
1072≡69mod125
Таким образом, решения по модулю 125:
Шаг 3: Комбинирование решений с помощью китайской теоремы об остаткахx≡18mod 125илиx≡107mod 125 x \equiv 18 \mod 125 \quad \text{или} \quad x \equiv 107 \mod 125
x≡18mod125илиx≡107mod125
Итак, у нас есть 4 случая по модулю 1000 1000 1000:
x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡18mod 125 x \equiv 18 \mod 125 x≡18mod125x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡107mod 125 x \equiv 107 \mod 125 x≡107mod125x≡6mod 8 x \equiv 6 \mod 8 x≡6mod8 и x≡18mod 125 x \equiv 18 \mod 125 x≡18mod125x≡6mod 8 x \equiv 6 \mod 8 x≡6mod8 и x≡107mod 125 x \equiv 107 \mod 125 x≡107mod125Решим каждый из этих случаев.
Случай 1:x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡18mod 125 x \equiv 18 \mod 125 x≡18mod125.
Для этого будем искать x=125k+18 x = 125k + 18 x=125k+18:
Случай 2:125k+18≡2mod 8 ⟹ 5k+2≡2mod 8 ⟹ 5k≡0mod 8 125k + 18 \equiv 2 \mod 8 \implies 5k + 2 \equiv 2 \mod 8 \implies 5k \equiv 0 \mod 8
125k+18≡2mod8⟹5k+2≡2mod8⟹5k≡0mod8 Решение k≡0mod 8 k \equiv 0 \mod 8k≡0mod8 даёт k=8m k = 8m k=8m:
x=125(8m)+18=1000m+18 x = 125(8m) + 18 = 1000m + 18
x=125(8m)+18=1000m+18 Следовательно, одно из решений:
x≡18mod 1000 x \equiv 18 \mod 1000
x≡18mod1000
x≡2mod 8 x \equiv 2 \mod 8 x≡2mod8 и x≡107mod 125 x \equiv 107 \mod 125 x≡107mod125:
Аналогично:
x=125k+107 ⟹ 125k+107≡2mod 8 ⟹ 5k+3≡2mod 8 ⟹ 5k≡5mod 8 x = 125k + 107 \implies 125k + 107 \equiv 2 \mod 8 \implies 5k + 3 \equiv 2 \mod 8 \implies 5k \equiv 5 \mod 8
x=125k+107⟹125k+107≡2mod8⟹5k+3≡2mod8⟹5k≡5mod8 Следовательно, k≡5mod 8 k \equiv 5 \mod 8 k≡5mod8 прибавим8,чтобынаходимрешенияприбавим 8, чтобы находим решенияприбавим8,чтобынаходимрешения:
Таким образом, k=8m+5 k = 8m + 5 k=8m+5:
Случай 3 и 4:x=125(8m+5)+107=1000m+632 x = 125(8m + 5) + 107 = 1000m + 632
x=125(8m+5)+107=1000m+632 Решение:
x≡632mod 1000 x \equiv 632 \mod 1000
x≡632mod1000
Аналогичным образом решаем оставшиеся случаи. Обратите внимание, что каждое решение можно будет подставить в систему.
Итак, окончательные решения:
Преобразование в пятиричную системуx≡18mod 1000иx≡632mod 1000 x \equiv 18 \mod 1000 \quad \text{и} \quad x \equiv 632 \mod 1000
x≡18mod1000иx≡632mod1000
Теперь преобразуем решения в пятиричную систему счисления:
1810=3⋅51+3⋅50=335 18_{10} = 3 \cdot 5^1 + 3 \cdot 5^0 = 33_5 1810 =3⋅51+3⋅50=335 63210 632_{10} 63210 :632÷5=126остаток 2 126÷5=25остаток 1 25÷5=5остаток 0 5÷5=1остаток 0 1÷5=0остаток 1 632 \div 5 = 126 \quad \text{остаток 2} \
126 \div 5 = 25 \quad \text{остаток 1} \
25 \div 5 = 5 \quad \text{остаток 0} \
5 \div 5 = 1 \quad \text{остаток 0} \
1 \div 5 = 0 \quad \text{остаток 1}
632÷5=126остаток 2 126÷5=25остаток 1 25÷5=5остаток 0 5÷5=1остаток 0 1÷5=0остаток 1 Собирая остатки, получаем: 110215 11021_5 110215 .Ответ
Итак, окончательные решения уравнения x2≡444mod 1000 x^2 \equiv 444 \mod 1000 x2≡444mod1000 в пятиричной системе счисления:
x≡335иx≡110215 x \equiv 33_5 \quad \text{и} \quad x \equiv 11021_5
x≡335 иx≡110215