5. Використовуючи метод Ейлера знайти розв’язок порівняння першого степеня .

Розв’язання. Як було показано вище, дане порівняння має один розв’язок.

! Теоретичні відомості !

Метод Ейлера. Для порівняння , де , розв’язок можна знаходити за формулою:

.

У нашому випадку, , , . Оскільки , то умови застосування методу Ейлера виконані. Шуканий розв’язок

.

Функція Ейлера . Отже,

.

Відповідь. .

6. Розв’язати систему порівнянь першого степеня за допомогою китайської теореми про залишки та за допомогою алгебраїчних перетворень.

Розв’язання. Розв’яжемо задану систему за допомогою китайської теореми про залишки.

! Теоретичні відомості !

Китайська теорема про залишки. Якщо числа попарно взаємно прості, то система порівнянь завжди має розв’язок. Будь-які два розв’язки відрізняються на число, яке кратне .

Приведемо задану систему до стандартного виду:

У даному випадку , , а також , , , тобто всі модулі являються попарно взаємно простими.

Будуємо таблицю:

	1	2	3
	7	5	11
	55	77	35

Тут – модулі у системі порівнянь, – добуток усіх модулів, окрім . Тобто для даної системи, наприклад, .

Знайдемо тепер лінійне представлення НСД чисел та :

,

,

.

Випишемо підкреслені доданки у отриманих розкладах НСД:

, , .

Розв’язком заданої системи порівнянь є клас

.

Знайдемо тепер розв’язок вихідної системи за допомогою арифметичних перетворень.

! Теоретичні відомості !

Метод алгебраїчних перетворень розв’язання системи порівнянь полягає у наступному: спочатку розв’язуємо перше порівняння системи і з його розв’язків обираємо ті, що задовольняють другому порівнянню. Серед спільних розв’язків перших двох порівнянь знаходимо ті, що задовольняють третьому порівнянню і так далі, поки не буде знайдено розв’язок для усіх порівнянь системи.

Спочатку знайдемо розв’язок першого порівняння системи будь-яким методом, наприклад, за допомогою метода алгебраїчних перетворень.

Перевіримо, чи має дане порівняння розв’язки: – один клас розв’язків. Знайдемо його:

.

Підставляємо отриманий розв’язок у друге порівняння системи :

.

Так як , то порівняння має розв’язок. Знаходимо його:

.

Отже, . Цей спільний розв’язок перших двох порівнянь системи підставляємо у третє :

.

Робимо перевірку розв’язності: – порівняння має один клас розв’язків. І за допомогою алгебраїчних перетворень коефіцієнтів отримуємо:

.

Таким чином,

або, що теж саме,

.

Відповідь. .

Контрольна робота № 4

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

Розв’язання.

! Теоретичні відомості !

Символом Лежандра називається вираз виду , де – просте непарне число, , який приймає значення 1 або – 1 у залежності від того, має чи не має розв’язок порівняння .

! Теоретичні відомості !

Властивості символу Лежандра:

1) ; 2) ;

3) . 4) ; 5) .

6) ; 7) ; 8) ;

9) , – прості непарні числа.

Так як , то згідно з другою властивістю символів Лежандра

.

Так як 61 та 197 – прості непарні числа, то за дев’ятою властивістю

.

З того, що , маємо що

.

За властивістю 5), оскільки , можемо записати:

.

Використовуючи властивість 7), обчислюємо

.

А за властивістю 9):

.

Тобто

.

Відповідь. .