![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Обчислення НСД і НСК способом канонічного розкладу на прості множники та за алгоритмом Евкліда.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 У першій частині доведемо, що кожен елемент множини M є елементом множини K. Нехай xÎM. Оскільки (a У другій частині доведемо, що кожен елемент множини K є елементом множини M. Нехай За доведеним у першій частині MÌK, а за доведеним у другій частині KÌM. Відповідно до означення рівності множин випливає, що M=K, тобто множини співпадають. Теорема доведена повністю. Ця теорема дає можливість звести знаходження НСД для чисел a і b до знаходження НСД чисел b і r, які менші за задані числа. Теоретичною основою цього є наступна теорема. Теорема: в алгоритмі Евкліда, який застосований до натуральних чисел a і b, остання, відмінна від нуля остача, буде дорівнювати НСД цих чисел. Доведення: для того, щоб знайти НСД даних чисел за алгоритмом Евкліда треба найбільше число поділити на найменше, потім найменше число на остачу, потім першу остачу на другу і т.д., аж доки не отримаємо в остачі 0. Тоді остання відмінна від 0 остача і буде НСД. Якщо a Проілюструємо обидва способи знаходження НСД і НСК на таких прикладах. Вправа 1: знайти НСД(248, 1024) за допомогою канонічного розкладу. Розв’язання: Розкладаємо числа 248 і 1024 на прості множники (див. таблицю № 4.9.). Щоб знайти НСД(248,1024) потрібно записати добуток спільних множників у найменшому степені. Оскільки спільним множником є тільки число 2 у третьому степені, то НСД(248,1024)=23=8. Вправа 2: знайти НСК(512,90) способом розкладу на прості множники. Розв’язання: Розкладаємо числа 512 і 90 на прості множники (див. таблицю № 4.10.). Щоб знайти НСК(512,90) потрібно записати добуток всіх множників у найбільшому степені. Отже, маємо: НСК(512,90)=29· 32·5=23040.
Таблиця № 4.9.
Таблиця № 4.10.
Вправа 3: знайти НСД(2002,12506) за допомогою алгоритму Евкліда. Розв’язання: Використовуючи алгоритм Евкліда для знаходження НСД слід більше число ділити на менше, потім менше число ділимо на першу остачу, потім першу остачу на другу остачу тощо. Цей процес продовжуватиметься доти, доки не отримаємо в остачі 0. При використанні алгоритму Евкліда для знаходження НСД запис потрібно починати з правого боку сторінки. Покажемо це на конкретному прикладі (див. таблицю № 4.11.):
Таблиця № 4.11.
Якщо відомий НСД чисел та самі числа, то для знаходження НСК чисел потрібно використати таку властивість:
|