logo
Лекція 5

1. Розв’язування квадратних конгруенцій за простим модулем

Розглянемо квадратну двочленну конгруенцію за простим непарним модулем :

, (1)

За допомогою очевидної заміни змінної до конгруенції (1) зводиться довільне рівняння

.

Число називається квадратичним лишком за модулем , якщо конгруенція (1) має розв’язки. Число називається квадратичним нелишком за модулем , якщо конгруенція (1) розв’язків не має.

За критерієм Ейлера для визначення квадратичних лишків і нелишків., якщо , то конгруенція (1) має розв’язки тоді і тільки тоді, коли , тобто

(2)

Готової формули для розв’язування алгебраїчних конгруенцій другого степеня не існує.

Відомі окремі випадки:

  1. Якщо , то .

  2. Якщо , то у випадку , а у випадку .

У випадках , для розв’язування (1) застосовується апроксимаційний (наближувальний) алгоритм, який полягає у наступному:

  1. Обчислити значення символу Лежандра . Якщо , – квадратичний лишок, якщо , квадратичний нелишок.

  2. Записати число у вигляді добутку парного і непарного чисел: , .

  3. Знайти випадковий квадратичний нелишок за модулем , тобто для виконано співвідношення .

  4. Покласти .

  5. Обчислити . ( – наближене значення кореня конгруенції ).

Квадратний корінь з за модулем шукати у вигляді .

  1. Знайти степінь , . Щоб визначити число , , запишемо його у двійковій системі числення

.

  1. Визначити, які значення (0 або 1) набувають двійкові цифри наступним чином:

7.1) Обчислити .