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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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