7. Обчислення нсд і нск способом канонічного розкладу на прості множники та за алгоритмом Евкліда.

7. У теорії чисел для знаходження НСК і НСД використовують два способи:

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

2) спосіб знаходження НСД, який називають алгоритмом Евкліда. Він ґрунтується на такій теоремі.

Теорема: якщо натуральне число а можна представити у вигляді a=bq+r, де a,b,q,rєN, то множина спільних дільників чисел a і b співпадає з множиною спільних дільників чисел b і r.

Доведення: нехай a=bq+r. Позначимо через М множину таких натуральних чисел d, які є дільниками чисел а і b, тобто М={dN/a db d}. Через К позначимо множину таких натуральних чисел k, які є дільниками чисел b і r, тобто K={kN/b kr k}. Для доведення теореми нам потрібно показати, що кожен елемент множини M є елементом множини K і навпаки. Отже, доведення складається із двох частин.

У першій частині доведемо, що кожен елемент множини M є елементом множини K. Нехай xM. Оскільки (a x)(b x), то за теоремою про подільність різниці та добутку (a-bq) x. Зважаючи на те, що a-bq=r, маємо r x. Тоді . Оскільки елемент х в множині M ми вибирали довільно, то наші міркування можна повторити для кожного елемента множини M, а тому кожен елемент множини M є елементом множини K, тобто MK. Перша частина теореми доведена.

У другій частині доведемо, що кожен елемент множини K є елементом множини M. Нехай ). Оскільки bq+r=a, то а у. Отже, . Оскільки елемент y ми вибираємо довільно, то наші міркування можна повторити для кожного елемента множини K. Отже, KM. Друга частина теореми доведена.

За доведеним у першій частині MK, а за доведеним у другій частині KM. Відповідно до означення рівності множин випливає, що M=K, тобто множини співпадають. Теорема доведена повністю.

Ця теорема дає можливість звести знаходження НСД для чисел a і b до знаходження НСД чисел b і r, які менші за задані числа. Теоретичною основою цього є наступна теорема.

Теорема: в алгоритмі Евкліда, який застосований до натуральних чисел a і b, остання, відмінна від нуля остача, буде дорівнювати НСД цих чисел.

Доведення: для того, щоб знайти НСД даних чисел за алгоритмом Евкліда треба найбільше число поділити на найменше, потім найменше число на остачу, потім першу остачу на другу і т.д., аж доки не отримаємо в остачі 0. Тоді остання відмінна від 0 остача і буде НСД. Якщо a b, то НСД(а,b)=b. Якщо ж а не ділиться націло на b, то відповідно до теореми про ділення з остачею маємо: a=bq+r, де a,b,q,rN, abrr₁r₂…r_k і b=rq₁+r₁, r=r₁q₂+r₂ тощо. Оскільки ми маємо abrr₁r₂…r_k, то за принципом найменшого числа ми прийдемо до випадку, коли якесь r_k=0, а тому ділення буде виконуватися націло. Тоді НСД(r_k-1,0)=r_k-1. Теорема доведена.

Проілюструємо обидва способи знаходження НСД і НСК на таких прикладах.

Вправа 1: знайти НСД(248, 1024) за допомогою канонічного розкладу.

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

Розкладаємо числа 248 і 1024 на прості множники (див. таблицю № 4.9.).

248	2	1024	2
124	2	512	2
62	2	256	2
31	31	128	2
1		64	2
248=2331		32	2
		16	2
		8	2
		4	2
		2	2
		1
		1024=210

Таблиця № 4.9.

Щоб знайти НСД(248,1024) потрібно записати добуток спільних множників у найменшому степені. Оскільки спільним множником є тільки число 2 у третьому степені, то НСД(248,1024)=2³=8.

Вправа 2: знайти НСК(512,90) способом розкладу на прості множники.

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

Розкладаємо числа 512 і 90 на прості множники (див. таблицю № 4.10.).

512	2	90	2
256	2	45	3
128	2	15	3
64	2	5	5
32	2	1
16	2	90=2325.
8	2
4	2
2	2
1
512 = 29.

Таблиця № 4.10.

Щоб знайти НСК(512,90) потрібно записати добуток всіх множників у найбільшому степені. Отже, маємо: НСК(512,90)=2⁹ 3²5=23040.

Вправа 3: знайти НСД(2002,12506) за допомогою алгоритму Евкліда.