Пример. Символ Лежандра сообщает нам, является ли a полным квадратом по модулю простого числа p

Символ Лежандра сообщает нам, является ли a полным квадратом по модулю простого числа p. Символ Якоби ничего не утверждает о возможности извлечения квадратного корня из a по модулю составного числа n. Если a в действительности квадрат по модулю n, то символ Якоби будет равен +1. Однако из равенства нельзя сделать вывод о том, что a – полный квадрат. Не смотря на благоприятное равенство, квадратный корень из a может не извлекаться.

Извлечение корня из числа по модулю составного n = p · q в предположении, что разложение n на простые множители известно и a – полный квадрат по модулю n, то есть

Сначала извлекается корень из a по модулю p и обозначается через s_p (таких корней два, как будет показано позже). Затем извлекается квадратный корень из a по модулю q и обозначается s_q (таких корней также два). Наконец, для вычисления искомого корня применяем китайскую теорему об остатках к системе

Пример. Вычислим корень из a = 217 по модулю n = 221 = 13 · 17.

Квадратные корни из a по модулям 13 и 17 соответственно равны s ₁₃ = 3 и s ₁₇ = 8. Опираясь на китайскую теорему об остатках, получаем s = 42. Проверим правильность данного решения: s² = 42² ≡ 217 (mod 221).

Существуют еще три квадратных корня из a = 217 по модулю n = 221, поскольку n имеет два простых делителя. Для их отыскания применим КТО к трем системам с коэффициентами:

s ₁₃ = 10, s ₁₇ = 8;

s ₁₃ = 3, s ₁₇ = 9;

s ₁₃ = 10, s ₁₇ = 9

и получить полный ответ: 42, 94, 127, 179.