Показательные и полиномиальные сравнения. 1 страница

Рассмотрим показательное сравнение (5.1), где . Условие является необходимым для разрешимости сравнения (5.1). Пусть - каноническое разложение модуля , где может быть нулем. Сравнение (5.1) равносильно системе сравнений: , , (5.2). Пусть , - системы индексов соответственно чисел и по модулю , то есть ,

(–1) ^d , где - первообразный корень по модулю (). Тогда система (5.2) эквивалентна системе сравнений первого порядка: , , (5.3) где , . Решение системы (5.3), если оно существует, может быть найдено с помощью китайской теоремы об остатках.

Пример 1. Решите показательное сравнение .

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

по модулю 64, находим, что . Так как , , то число 2 является первообразным корнем по модулю 9. Учитывая, что , , делаем вывод о том, что , - системы индексов соответственно чисел и по модулю . Следовательно, сравнение равносильно системе сравнений

Разрешая эту систему, находим, что .

Другой подход к решению показательного сравнения (5.1) заключается в использовании свойств показателей и применении китайской теоремы об остатках. Проиллюстрируем этот приём на следующем примере.

Пример 2. Решите показательное сравнение .

Решение. Так как , то сравнение равносильно системе сравнений:

Показатель , которому принадлежит число 5 по модулю делит . Отсюда находим, что , , . Так как , , имеем:

Применяя к последней системе китайскую теорему об остатках, получаем .

Укажем способ решения степенного сравнения (5.4), где . Пусть - каноническое разложение модуля , где , тогда сравнение (5.4) эквивалентно системе сравнений: , , . Пусть , - системы индексов соответственно чисел и по модулю , то есть , , где - первообразный корень по модулю . Тогда система индексов числа по модулю может быть найдена из следующих сравнений: . Решение сравнения (5.4) можно найти из системы: , .

Пример 3. Решите степенное сравнение .

Решение. Найдем системы индексов чисел , по модулю . Имеем , ; , ; , . Следовательно, и (2,1,8,12) – системы индексов чисел 7 и 157 по модулю . Для нахождения системы индексов неизвестного числа получаем систему сравнений:

Решая систему, находим, что - система индексов числа . Получаем систему сравнений для нахождения :

Используя китайскую теорему об остатках, получаем, что .

Перейдем к рассмотрению полиномиальных сравнений (5.5), где , для любого . Сравнение (5.5) равносильно системе сравнений , , где - каноническое разложение модуля . Таким образом, для решения сравнения (5.5) следует решить каждое из сравнений , а затем применить китайскую теорему об остатках.

Приведем способ нахождения решения полиномиального сравнения по примарному модулю.

1) Применяя теорему Ферму, сравнение сводим к полиномиальному сравнению , где - многочлен с целыми коэффициентами степени не выше, чем . Находим решения сравнения : .

2) Для каждого фиксированного полагаем , где . Левую часть сравнения раскладываем по формуле Тейлора (принимая во внимание, что число является целым, и отбрасывая члены, кратные ): . Сокращая обе части сравнения и модуль на , получаем: . Находим решения этого сравнения: ,…, . Таким образом, x ≡ x_i + t_i,jp = x_{i, j}(mod p ²), , .

3) Для каждых фиксированных , полагаем , где . Аналогично левую часть сравнения раскладываем по формуле Тейлора и отбрасываем члены, кратные : . Сокращая сравнение на , получим: . Решая сравнение, находим, что , . Подставляя в , получим: .

4) Проделывая последовательно для модулей описанную процедуру, найдем решения сравнения .

Отметим, что в случае решение сравнения даст одно решение сравнения .

Пример 4. Решите полиномиальное сравнение 16x⁸–8x⁷+9x⁴–1≡ ≡0(mod196).

Решение. Исходное сравнение эквивалентно системе сравнений:

Из первого сравнения системы получаем: . Обозначим . Найдем решение сравнения . Имеем:

. Отсюда получаем, что . Пусть , .

Далее . Следовательно, . Таким образом, - решение второго сравнения системы.

Применяя китайскую теорему об остатках к системам

заключаем, что , .

Рассмотрим двучленное сравнение второй степени (5.6), где . Если сравнение (5.6) имеет решение, то число называется квадратичным вычетом по модулю , в противном случае называется квадратичным невычетом по модулю .

Пусть , где - нечетное простое число. Приведенная система вычетов по модулю состоит из квадратичных вычетов и квадратичных невычетов. Символ Лежандра определяется равенством , если является квадратичным вычетомпо модулю , и равенством , если является квадратичным невычетомпо модулю . Для любых , и любого нечётного простого числа , , имеют место следующие свойства:

1) ;

2) (критерий Эйлера);

3) ;

4) ;

5) (квадратичный закон взаимности).

Пусть теперь - нечётное натуральное число, большее 1, и - разложение числа на простые множители. Для всякого целого числа , взаимно простого с , символ Якоби определяется через символы Лежандра по формуле: . Для любых целых , взаимно простых с , и любого нечётного натурального , большего 1 и взаимно простого с , имеют место следующие свойства символа Якоби:

6) ;

7) ;

8) ;

9) ;

10) ;

11) .

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

Пример 5. Исследовать на разрешимость сравнение .

Решение. Вычислим символ Лежандра , рассматривая его как символ Якоби и используя свойства символа Якоби:

.

Откуда следует, что сравнение разрешимо.

5.1. Используя свойства показателей, решите следующие показательные сравнения по простому модулю:

1) 2) 3) ,

4) , 5) .

5.2. Используя свойства показателей и китайскую теорему об остатках, решите следующие показательные сравнения по составному модулю:

1) 2) 3) ,