Пусть p и q - простые числа.
Вы можете разбить модульное уравнение на отдельные уравнения, если факторы взаимно просты.
Это означает, что ?**2 = x (mod m) эквивалентнона ?**2 = x (mod p) и ?**2 = x (mod q).
Каждый из них может быть разложен на множители как x(x-1)=0 => x=0 or x=1.
Итак, вы знаете, что x равно 0 или 1 по модулю p, а x равно 0 или 1по модулю д.Каждый выбор имеет 1 решение по модулю m по китайской теореме об остатках, поэтому будет 4 решения.
2 легко (x = 0 и x = 1).Два других можно найти с помощью расширенного евклидова алгоритма следующим образом:
def egcd(a, b):
x,y = 0,1
lx,ly = 1,0
while b != 0:
q = a/b
(a, b) = (b, a%b)
(lx, x) = (x, lx-q*x)
(ly, y) = (y, ly-q*y)
return (lx, ly)
p=7
q=11
m=p*q
(lx, ly) = egcd(p,q)
print lx*p%m,ly*q%m