1. Для чисел та :

а) за допомогою канонічних розкладів знайти найбільший спільний дільник та найменше спільне кратне ;

б) за допомогою алгоритму Евкліда знайти і визначити цілі числа такі, що .

Розв’язання. а) Запишемо канонічні розклади заданих чисел:

1246	2		1892	2
623	7		946	2
89	89		473	11
	1		43	43
				1

Отже, , а .

Щоб знайти найбільший спільний дільник (НСД) чисел, треба з їх канонічних розкладів виписати однакові прості множники в найменшій степені, тобто

.

Для знаходження найменшого спільного кратного (НСК) чисел треба з їх канонічних розкладів виписати всі прості множники, які входять хоча б до одного із розкладів. З однакових простих множників обрати той, який стоїть у найбільшому степені:

.

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

НСД та НСК двох чисел та пов’язані рівністю:

.

Перевіримо правильність проведених обчислень, застосувавши наведену вище тотожність:

.

б) Алгоритм Евкліда складається з декількох кроків, кожен з яких є діленням з залишком.

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

НСД двох чисел дорівнює останньому нерівному нулю залишку в алгоритмі Евкліда.

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

Два числа називаються взаємно простими, якщо їх НСД дорівнює 1.

Виконаємо ділення у стовпчик (так як , то ділимо на ):

–			–
	1246			646

–			–
	600			598

–
	46
	0

Таким чином, НСД заданих чисел

.

Для знаходження лінійного представлення НСД запишемо наведені результати ділення у вигляді буквених виразів, і на кожному етапі будемо виражати залишки через задані числа та :

;

;

;

;

Отже, . А тоді

.

Відповідь. а) , .

б) , .

2. Для числа знайти значення функції Ейлера від , суму й число усіх натуральних дільників.

Розв’язання. Як уже було показано у прикладі 1, канонічний розклад числа має вигляд: .

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

Функція Ейлера представляє собою кількість натуральних чисел, що не перевищують і є взаємно простими з .

Для числа функція Ейлера обчислюється за формулою:

.

Таким чином,

.

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

Функція – це сума натуральних дільників числа . Нехай , тоді

.

Використовуючи цю формулу, маємо, що

.

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

Функція – це кількість натуральних дільників числа , причому, якщо , то

.

Отже, для заданого числа

.

Відповідь. ; ; .

3. Розв’язати систему в натуральних числах.

Розв’язання. Нехай , тоді , а також , , причому . Підставляємо ці вирази у перше рівняння системи:

.

Записуємо всілякі розклади числа 4 на натуральні доданки:

, , .

Пара не підходить, так як . Тому маємо, що та . А отже

, ; , .

Відповідь. , .

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