7. Решение сравнений

Если число х₀удовлетворяет сравнению

a₀xⁿ+ a₁x^n-1+ … +a_n0 (modm), (1)

то этому сравнению удовлетворяют все числа, сравнимые с х₀ по модулю m. Поэтому решением сравнения считается класс вычетов по модулю m, содержащий х₀.

Так как классов вычетов конечное число, то сравнение (1) всегда можно решить полным перебором, проверив какую-нибудь полную систему вычетов по модулю m.

Сравнение первой степени

ax  b (mod m) (2)

при (a, m) = 1 имеет единственное решение. При небольших а его можно решить преобразованием коэффициентов: число b заменяется на сравнимое с ним по модулю m, прибавлением или вычитанием кратного m. Цель этого – получить число, делящееся на а. Затем производится сокращение.

Пример 7.1. Решить сравнение 3х7 (mod17).

Решение. Так как (3, 17) = 1, то сравнение имеет единственное решение. Преобразуем сравнение и получаем решение:

3х  24 (mod 17);

х  8 (mod 17).

При больших аэтот метод оказывается неэффективным. В этом случае для решения сравнения (2) разлагаем числов цепную дробь. Находим числители подходящих дробей к этому числу. ПустьP_k-1– предпоследний числитель. Тогда решение сравнения находится по формуле

x(-1)^k P_k-1b(modm).(3)

Пример 7.2. Решить сравнение 31х17 (mod42).

Решение. Так как (31, 42) = 1, то сравнение имеет единственное решение. Разлагая числов цепную дробь как показано в разделе 3, получаем= [1; 2, 1, 4, 2]. Находим числители подходящих дробей:

i	0	1	2	3	4
ai	1	2	1	4	2
Pi	1	3	4	19	42

Подставляя в формулу (3), получаем

x  (-1)⁴1917  323  29 (mod 42).

Если (a, m) =d >1, то сравнение (2) не имеет решений приdне делящемb. Еслиb  d, то сравнение имеетdрешений. Для их нахождения сокращаем обе части и модуль сравнения наdи приходим к сравнениюa₁xb₁(modm₁), которое согласно предыдущему имеет единственное решениеxx₀(modm₁). Тогда решения исходного сравнения находим по формулам

xx₀,x₀ +m₁,x₀ + 2m₁, … ,x₀ + (d– 1)m₁ (modm).

Пример 7.3. Решить сравнение 12х15 (mod33).

Решение. Имеем (12, 33) = 3. Так как 153, то сравнение имеет 3 решения. Сократив на 3, получаем сравнение 4х5 (mod11), которое решим методом преобразования коэффициентов:

4х16 (mod11);

х4 (mod11).

Следовательно, сравнение имеет решения х4, 15, 26 (mod33).

Упражнение7.1. Решите сравнения:

а) 4х  11 (mod 23);

б) 5х  3 (mod 14);

в) 8х  19 (mod 15);

г) 41х  21 (mod 53);

д) 34х  19 (mod 39);

е) 10х  13 (mod 24);

ж) 15х  24 (mod 36);

з) 12х  22 (mod 40);

и) 16х  20 (mod 36).

8. Первообразные корни и индексы

Порядком числа апо модулюmназывается наименьший натуральный показательkтакой, чтоa^k1(modm). Порядок числаапо модулюmсуществует, если (a, m) = 1, и обозначаетсяO(amodm).

Теорема 8.1.ПустьO(amodm) =d. Тогда

1. a^k1(modm)kd;

2. (m)d;

3. a^ka^l(modm)kl(modd);

4. Числа a, a², … , a^d попарно несравнимы по модулю m.

Число а называется первообразным корнем по модулю m, если O(amodm) =(m). Первообразный корень существует не для всякого модуля. Для любого простого модуля первообразный корень существует.

Пусть а– первообразный корень по модулюm. Тогда (a, m) = 1 и числаa, a², … , a^(m)образуют приведенную систему вычетов по модулюm. Если (b, m) = 1, то индексом числаbпо модулюmс основаниеманазывается показательkтакой, чтоa^kb(modm). Индекс обозначаетсяind_abилиindb. Любые два индекса данного числа сравнимы по модулю(m).

Пример 8.1. Найти первообразный корень по модулю 11 и построить таблицу индексов по этому модулю.

Решение. Имеем(11) = 10. Значит, порядок любого числа по модулю 11 делит 10. Для числа 2 имеем 2²= 4≢1(mod11); 2⁵= 32-1≢1(mod11); 2¹⁰1(mod11). Следовательно,O(2mod11) = 10 и 2 – первообразный корень по модулю 11. Если бы порядок числа 2 оказался меньше 10, то мы проверяли бы следующие числа.

Для построения таблицы индексов рассматриваем все степени числа 2 и определяем остаток от деления их на 10.

k	1	2	3	4	5	6	7	8	9	10
2k	2	4	8	5	10	9	7	3	6	1

Отсюда получаем таблицу индексов. Для числа, расположенного во второй строке, индекс находится в первой строке того же столбца:

b	1	2	3	4	5	6	7	8	9	10
ind b	10	1	8	2	4	9	7	3	6	5

Теорема 8.2.Свойства индексов:

1. ind ab= ind a+ ind b;

2. ind aⁿ=n ind a.

Свойства индексов позволяют решать двучленные сравнения с помощью таблицы индексов.

Пример 8.2. Решить сравнения: а) 7х6 (mod 11); б) 5х⁸3 (mod 11).

Решение.

а) 7х  6 (mod 11);

ind (7х)  ind 6 (mod 10);

ind 7 + ind х  ind 6 (mod 10);

7 + ind х9 (mod 10);

ind х2 (mod 10);

х  4 (mod 11).

б) 5х⁸  3 (mod 11);

ind 5 + 8 ind хind 3 (mod 10);

4 + 8 ind х8 (mod 10);

8 ind х4 (mod 10);

(8, 10) = 2, 42, следовательно, сравнение имеет два решения;

4 ind х2 (mod 5);

2 ind х1 (mod 5);

2 ind х6 (mod 5);

ind х3 (mod 5);

ind х3 (mod 10), indх8 (mod 10);

х  8 (mod 11), х  3 (mod 11).

Упражнение8.1. Решите сравнения с помощью таблицы индексов:

а) 5х  9 (mod 11);

б) 4х  7 (mod 11);

в) 6х⁶  5 (mod 11);

г) 6х⁶  7 (mod 11);

д) 3х⁷  8 (mod 11);

е) 8х⁸  7 (mod 11).