Найбільший спільний дільник і способи його знаходження

Сторінка 1

Означення 3. Дільником числа називають таке число, на яке дане число ділиться без остачі (націло).

Наприклад, число 9 є дільником числа 81, а число 13 – дільником числа 26.

Означення 4. Найбільшим спільним дільником (НСД) декількох чисел називають найбільше число, на яке кожне з даних чисел ділиться без остачі.

Для знаходження найбільшого спільного дільника чисел а і b (НСД (а; b)) потрібно:

1. Знайти всі дільники числа а і всі дільники числа b

2. Знайти спільні дільники чисел а і b, тобто дільники, які є дільниками кожного з чисел а і b

3. Обчислити добуток всіх спільних дільників, беручи кожен з множників з найменшим показником.

Результат записати у вигляді НСД (а; b)

Означення 5. Взаємно простими числами називаються числа, які не мають інших спільних дільників крім одиниці.

Другий спосіб знаходження НСД пов'язаний з давньогрецьким математиком Евклідом, який виклав у 7 книзі своїх «Начал». Цей спосіб легший, доступніший і більше подобається дітям.

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

Теорема 8. Якщо , то НСД([3]

Теорема 9. Якщо то НСД(НСД(.

Доведення.

Нехай - множина спільних дільників і b. B-множина спільних дільників b і r.

1)

Отже, (теорема про подільність різниці).

Отже,

2)

. Отже, (теорема про подільність суми).

. Отже, .

(1), (2) (означення рівних множин), тобто, множини спільних дільників співпадають, отже, рівними є їх найбільші елементи:

НСД()=НСД().

Теорему доведено.

Доведення твердження дозволяє знаходження НСД() замінити на знаходження НСД менших чисел, що спрощує обчислення. Причому таку заміну можна здійснювати неодноразово.

Алгоритм Евкліда:

Алгоритм Евкліда ітеративний, тобто, пошук розв'язку відбувається за декілька кроків; вихідні дані попереднього кроку служать вхідними для наступного. Нехай k – ціле число, що дорівнює кількості виконаних кроків, починаючи з 0. Кожен крок починається з двома невід'ємними залишками rk−1 та rk−2. Оскільки алгоритм гарантує, що залишки постійно зменшуватимуться на кожному кроці, rk−1 менше за попердній залишок rk−2. Задачею кроку k є пошук частки qk та залишку rk, що задовільняють рівнянню:

rk−2 = qk rk−1 + rk

де rk < rk−1. Іншими словами, добутки меншого числа rk−1 віднімають від більшого числа rk−2 доки залишок буде менше за rk−1. На початковому кроці (k = 0), залишки r−2 та r−1 дорівнюють a та b, числам, для яких шукають НСД. На наступному кроці (k = 1), залишки дорівнюють b та залишку r0 першого кроку, і так далі. Таким чином, алгоритм можна записати як послідовність рівнянь

Страницы: 1 2



Психолого-педагогічний аналіз категорії «фізична задача»
Під фізичною задачею на практиці розуміють деяку фізичну проблему, яка в загальному випадку розв’язується за допомогою логічних умовиводів, математичних дій та експерименту на основі законів та метод ...

Особливості організації морального виховання у початковій школі
З перетворенням України на самостійну державу освіта стала власною справою українського народу. Розбудова система освіти, докорінне її реформування мають стати підґрунтям відтворення інтелектуального ...

Читання як вид навчальної діяльності

Громадянська освіта

Читання - основний засіб навчання, інструмент пізнання навколишнього світу. >>>

Copyright © 2019 - All Rights Reserved - www.pedahohikam.net