logo
Лекція 5

7.2) Обчислити , .

Покласти ,

, .

  1. Відповідь: – квадратний корінь з за модулем .

Приклад 1. Розв’язати конгруенцію:

Розв’язання

  1. Обчислимо значення символу Лежандра

Отже, конгруенція має розв’язки.

  1. Запишемо число у вигляді добутку парного і непарного чисел: . Отже, , .

  2. Знайдемо квадратичний нелишок за модулем . Нехай , тому що

.

  1. Покладемо

  1. Обчислимо

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

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

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

7.1) Обчислимо . За розширеним алгоритмом Евкліда визначимо:

.