Случай составного модуля

Двучленные сравнения второй степени по составному модулю исследуются и решаются согласно общим указаниям п. 5, гл. IV.

Сначала рассмотрим сравнение

x² ? a(mod p^α); α > 0, (a, p) = l, (1)

где p - простое нечетное.

Полагая f(x) = x² - а, будем иметь f'(x) = 2x, и если x ? x_l(mod p) есть решение сравнения

x² ? a(mod p), (2)

то ввиду (а, p) = 1 также (x_l, p) = 1, а так как p - нечетное, то (2x₁, p) = 1, т. е. f'(x₁) не делится на р. Поэтому к разысканию решений сравнения (1) можно применить рассуждения b, п. 5, гл. IV, причем каждое решение сравнения (2) даст одно решение сравнения (1). Из сказанного выводим, что

Сравнение (1) имеет два решения или же ни одного, в зависимости от того, будет ли число а квадратичным вычетом или же невычетом по модулю p.

Далее рассмотрим сравнение

x² ? a(mod 2^α); α > 0, (а, 2) = 1. (3)

Здесь f'(x₁) = 2x₁ делится на 2, и потому рассуждения b, п. 6, гл. IV неприменимы; они должны быть видоизменены следующим образом:

Если сравнение (3) разрешимо, то ввиду (а, 2) = 1 имеем (x, 2) = 1; следовательно (h, п. 2), x² - 1 делится на 8. Поэтому, приводя сравнение (3) к виду

(x² – 1) + 1 ? a(mod 2^α),

убеждаемся, что для разрешимости этого сравнения необходимо

a ? 1(mod 4) при α = 2; a ? 1(mod 8) при α ≥ 3. (4)

В случаях, когда условия (4) не нарушены, рассмотрим вопрос о разыскании решений и их числе.

Для случаев α ≤ 3 ввиду d сравнению удовлетворяют все нечетные числа. Поэтому сравнение х² ? а(mod 2) имеет одно решение: x ? 1(mod 2), сравнение х² ? а(mod 4) имеет два решения: x ? 1; 3(mod 4), сравнение х² ? а(mod 8) имеет четыре решения: x ? 1; 3; 5; 7(mod 8).

Для рассмотрения случаев α = 4, 5, ... все нечетные числа полезно объединить в две арифметические прогрессии:

x = ±(1 + 4t₃) (5)

(1 + 4t₃ ? 1(mod4); -1 – 4t₃ ? -1 ? 3(mod4)).

Посмотрим, какие из чисел (5) удовлетворяют сравнению x² ? a(mod 16). Находим

(1 + 4t₃)² ? a(mod 16), ,

t₃=t'₃ + 2t₄,

x = ±(1 + 4t'₃ + 8t₄) = ±(x₄ + 8t₄).

Посмотрим, какие из последних чисел удовлетворяют сравнению x² ? a(mod 32). Находим

(x₄ + 8t₄)² ? a(mod 32), t₄=t'₄ + 2t₅, x = ±(x₅ + 16t₅),

и т. д. Таким путем убедимся, что при любом α > 3 значения x, удовлетворяющие сравнению (3), представятся в виде

x = ±(x_α + 2^α-1t_α).

Эти значения x образуют четыре различных решения сравнения (3)

x ? x_α; x_α + 2^α-1; - x_α; - x_α - 2^α-1 (mod 2^α)

(по модулю 4 два первых сравнимы с 1, а два последних сравнимы с - 1).

Пример: Сравнение

x² = 57(mod 64) (6)

ввиду 57 ? 1(mod 8) имеет четыре решения. Представляя x в виде x = ±(1 + 4t₃), находим

(1 + 4t₃)² ? 57(mod 16), 8t₃ ? 56(mod 16),

t₃ ? 1(mod 2), t₃= 1 + 2t₄, x = ±(5 + 8t₄),

(5 + 8t₄)² ? 57(mod 32), 5∙16t₄ ? 32(mod 32),

t₄ ? 0(mod 2), t₄= 2t₅, x = ±(5 + 16t₅),

(5 + 61t₅)² ? 57(mod 64), 5∙32t₅ ? 32(mod 64),

t₅ ? 1(mod 2), t₅= 1 + 2t₆, x = ±(21 + 32t₆).

Поэтому решения сравнения (6) будут:

x ? ± 21; ± 53(mod 64).

Из с, d и e следует:

Для сравнения

x² ? a(mod 2^α); (а, 2) = 1

необходимыми условиями разрешимости будут: a ? 1(mod 4) при α = 2, a ? 1(mod 8 при α ≥ 3 Если эти условия не нарушены, число решений будет: 1 при α = 1 2 при α = 2; 4 при α ≥ 2.

Из b, f и из а, п. 5, гл. IV следует:

Для сравнения общего вида

х² ? а(mod m); ; (a, m) = 1

необходимыми условиями разрешимости будут:

a ? 1(mod 4) при α = 2, a ? 1(mod 8) при α ≥ 2,

.

Если ни одно из этих условий не нарушено, число решений будет: 2^k при α = 0 и при α = 1; 2^{k + 1} при α = 2; 2^{k + 2} при α ≥ 3.

Глава 6