Квадратичные сравнения по составному модулю

Рассмотрим сравнение вида x²≡a(mod p^α), где p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение x²≡a(mod p). Причем сравнение x²≡a(mod p^α) будет иметь два решения, если a является квадратичным вычетом по модулю p.

Пример:

Решить квадратичное сравнение x²≡86(mod 125).

125 = 5³, 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.

. Исходное сравнение имеет 2 решения.

Найдем решение сравнения x²≡86(mod 5).

x²≡1(mod 5).

Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть

x≡±1(mod 5) или, иначе, x=±(1+5t₁).

Подставим получившееся решение в сравнение по модулю 5²=25:

x²≡86(mod 25)

x²≡11(mod 25)

(1+5t₁)²≡11(mod 25)

1+10 t₁+25 t₁²≡11(mod 25)

10 t₁≡10(mod 25)

2 t₁≡2(mod 5)

t₁≡1(mod 5), или, что то же самое, t₁=1+5t₂.

Тогда решение сравнения по модулю 25 есть x=±(1+5(1+5t₂))=±(6+25t₂). Подставим получившееся решение в сравнение по модулю 5³=125:

x²≡86(mod 125)

(6+25t₂)²≡86(mod 125)

36+12·25t₂+625t₂²≡86(mod 125)

12·25t₂≡50(mod 125)

12t₂≡2(mod 5)

2t₂≡2(mod 5)

t₂≡1(mod 5), или t₂=1+5t₃.

Тогда решение сравнения по модулю 125 есть x=±(6+25(1+5t₃))=±(31+125t₃).

Ответ: x≡±31(mod 125).

Рассмотрим теперь сравнение вида x²≡a(mod 2^α). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:

1) α=1. Тогда сравнение имеет решение только тогда, когда a≡1(mod 2), и решением будет x≡1(mod 2) (одно решение).

2) α=2. Сравнение имеет решения только тогда, когда a≡1(mod 4), и решением будет x≡±1(mod 4) (два решения).

3) α≥3. Сравнение имеет решения только тогда, когда a≡1(mod 8), и таких решений будет четыре. Сравнение x²≡a(mod 2^α) при α≥3 решается так же, как сравнения вида x²≡a(mod p^α), только в качестве начального решения выступают решения по модулю 8: x≡±1(mod 8) и x≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2^α.

Пример:

Решить сравнение x²≡33(mod 64)

64=2⁶. Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.

По модулю 8 эти решения будут: x≡±1(mod 8) и x≡±3(mod 8), что можно представить как x=±(1+4t₁). Подставим это выражение в сравнение по модулю 16

x²≡33(mod 16)

(1+4t₁)²≡1(mod 16)

1+8t₁+16t₁²≡1(mod 16)

8t₁≡0 (mod 16)

t₁≡0 (mod 2)

Тогда решение примет вид x=±(1+4t₁)=±(1+4(0+2t₂))=±(1+8t₂). Подставим получившееся решение в сравнение по модулю 32:

x²≡33(mod 32)

(1+8t₂)²≡1(mod 32)

1+16t₂+64t₂²≡1(mod 32)

16t₂≡0 (mod 32)

t₂≡0 (mod 2)

Тогда решение примет вид x=±(1+8t₂) =±(1+8(0+2t₃)) =±(1+16t₃). Подставим получившееся решение в сравнение по модулю 64:

x²≡33(mod 64)

(1+16t₃)²≡33(mod 64)

1+32t₃+256t₃²≡33(mod 64)

32t₃≡32 (mod 64)

t₃≡1 (mod 2)

Тогда решение примет вид x=±(1+16t₃) =±(1+16(1+2t₄)) =±(17+32t₄). Итак, по модулю 64 исходное сравнение имеет четыре решения: x≡±17(mod 64)и x≡±49(mod 64).

Теперь рассмотрим сравнение общего вида: x²≡a(mod m), (a,m)=1, - каноническое разложение модуля m. Согласно Теореме из п.4 §4, данному сравнению равносильна система

Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2^k, если α=1, 2^k+1, если α=2, 2^k+2, если α≥3.

Пример:

Решить сравнение x²≡4(mod 21).

21 – составное число. Факторизуем его: 21=3·7. Проверим разрешимость исходного сравнения:

, . Сравнение разрешимо и имеет 2²=4 решения.

Составим систему: . Решим каждое из уравнений этой системы. Получим . Итак, имеем 4 системы:

1) 2) 3) 4)

Решая каждую из этих систем по китайской теореме об остатках, получим четыре решения: x≡±2(mod 21), x≡±5(mod 21).