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

Сторінка 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 © 2018 - All Rights Reserved - www.pedahohikam.net