Властивості степеневих конгруенцій

Якщо, то розв’язок єдиний:.

Загальний метод розв’язку лінійних конгруенцій з одним невідомим.

Порівняння виду можуть мати кілька розв’язків, мати єдиний розв’язок або не мати розв’язків взагалі.

Відзначимо, що якщо модуль і коефіцієнти конгруенції розділити або помножити як цілі числа на те саме число, те отримана конгруенція буде істинною.

Це випливає з того, що якщо ділиться на, а ділиться на, те ділиться на.

Теорема. Розв’язки конгруенції існують тоді і тільки тоді, коли ділить.

В цьому випадку, крім вихідного порівняння, розв'язне порівняння виду з єдиним розв’язком.

Очевидно, всі розв’язки вихідного порівняння в діапазоні є числами виду ,.

Зокрема, якщо просте, то порівняння має не більш одного розв’язку.

Квадратичною конгруенцією називається конгруенція виду, де - невідомий лишок.

Ціле число називається квадратичним лишком за модулем, якщо конгруенція розв'язна. Якщо конгруенція розв'язна, то для складеного модуля число розвязків, як правило, більше двох. Питання про можливість розв'язання квадратичної конгруенції за складеним модулем, факторизация якого невідома, є нерозвязуваною проблемою.

Очевидно, якщо, те є квадратичним лишком за модулем будь-якого простого дільника числа. Для модулів, що є простими числами, проблема легко піддається аналізу.

Теорема. Число ненульових квадратичних лишків дорівнює числу квадратичних нелишків.

Нехай - непарне просте число. Нехай квадратичний влишок за модулем.

Очевидно, при існує єдиний розв’язок:.

Усі ненульові лишки за модулем знаходяться серед чисел, отже, їхні квадрати складають список і конгруенція має розв’язок, якщо належить до цього списку.

Далі, якщо, те існують два очевидних розв’язки. Крім того, кількість розв’язів не може перевищувати степеня многочлена в лівій частині, тобто двох. Щоб переконатися, що розв’язів саме два, досить показати, що. Однак, якщо це не так, то, що вірно тільки для.

Зауважимо тепер, що в нашому списку квадратичних лишків усі лишки попарно неконгруентні. Дійсно, якщо, наприклад, і, те конгруенція мала б чотири розв’язи:,, що неможливо. Таким чином, кількість ненульових квадратичних розв’язків дорівнює. Отже, кількість квадратичних нелишків також дорівнює.

Стапеневі конгруенції виду.

Нехай - первісний елемент простого поля. Тоді існують числа і, такі що,, тому.

Оскільки, то. Властивості останньої конгруенції цілком характеризують можливість розв'язання вихідного. Будь-який його розв’язок приводить до розв’язку конгруенції.При великих значеннях змінних, розв’язуванню задачі перешкоджає необхідність явного виразу числа у виді.

У загальному випадку, розв’язати задачу знаходження обчислювально неможливо (проблема дискретного логарифму).

Відомий наступний результат: нехай - просте,,, тоді порівняння має розв’язків. При одержуємо, що число первісних коренів у поле дорівнює.

Дата добавления: 2014-10-15