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

Сторінка 2

a = q0 b + r0

b = q1 r0 + r1

r0 = q2 r1 + r2

r1 = q3 r2 + r3

Якщо a менше за b, першим кроком алгоритм переставляє числа. Наприклад, якщо a < b, початкова частка q0 дорівнює нулю, а залишок r0 дорівнює a. Тому rk менше за попередній залишок rk−1 для всіх k ≥ 0. Оскільки залишки зменшуються на кожному кроці але не можуть бути від'ємними, деякий залишок rN дорівнюватиме нулю, і тоді алгоритм зупиняється Останній ненульовий залишок rN−1 і є найбільшим спільним дільником чисел a та b. Число N має бути скінченним, оскільки існує лише скінченна кількість цілих чисел між початковим залишком r0 та нулем.

Доведення.

Вірність алгоритму Евкліда можна довести за два кроки. На першому кроці доводять, що останній ненульовий залишок rN−1 ділить a та b. Оскільки він є спільним дільником, він має бути не більше або дорівнювати найбільшому спільному дільникові g. На другому кроці, доводять, що будь-який спільний дільник a та b, включаючи g, має ділити rN−1; таким чином, g має бути менше або дорівнювати rN−1. Обидва припущення можуть бути дійсними водночас якщо rN−1 = g. Аби показати, що rN−1 ділить a та b (перший крок), rN−1 ділить попередника rN−2

rN−2 = qN rN−1

оскільки останній залишок rN дорівнює нулю. rN−1 також ділить наступного попередника rN−3 rN−3 = qN−1 rN−2 + rN−1

оскільки ділить обидва значення з правої частини рівняння. Аналогічно, rN−1 ділить всі попередні залишки, разом з a та b. Жоден з попередніх залишків rN−2, rN−3, і далі, не ділить a та b, оскільки лишається залишок від ділення. Оскільки rN−1 спільний дільник a та b, rN−1 ≤ g. На наступному кроці, довільне натуральне число c, що ділить a та b (іншими словами, будь-який спільний дільник a та b) ділить залишки rk. За визначенням, a та b можна записати як добутки c: a = mc та b = nc, де m та n – натуральні числа. Таким чином, c ділить початковий залишок r0, оскільки r0 = a − q0b = mc − q0nc = (m − q0n) c. Аналогічно, можна показати, що c також ділить наступні залишки r1, r2, і так далі. Таким чином, найбільший спільний дільник g має ділити rN−1, звідки випливає, що g ≤ rN−1. Оскільки на першому кроці було показано зворотнє (rN−1 ≤ g), виходить, що g = rN−1. Звідси, g найбільший спільний дільник для всіх наступних пар: g = НСД (a, b) = НСД (b, r0) = НСД(r0, r1) = … = НСД(rN−2, rN−1) = rN−1, що й треба було довести. Теорему доведено.

Властивості НСД

Для будь-яких натуральних чисел і b існує єдиний НСД.

Якщо <b, то НСД(, b) (НСД не перевищує меншого з даних чисел).

Якщо , то НСД(, b)=b.

Частки від ділення чисел і b на їх НСД – числа взаємно прості.

Доведення.

Нехай НСД (, b)= b і .

Доведемо, що НСД(=1.

Припустимо супротивне, тобто НСД(=m>1. Тоді

Але d – найбільший спільний дільник. Одержали суперечність.

Властивість доведено.

Страницы: 1 2 



Основні соціально-педагогічні умови формування відповідального ставлення до власного здоров’я у старших підлітків
Все частіше і частіше ми чуємо про здоровий спосіб життя по радіо і з екранів телевізорів, читаємо на сторінках газет і журналів. Чому ж стільки уваги приділяється цьому питанню? Причин доволі багато ...

Значення гармонійного виховання людини
Публікації вченої дають відповідь на питання про те, яким має бути ідеал соціально захищеної дитини, якими мають бути соціально-виховні обов'язки держави та ін. Ще в 1918 р. вона писала: «Найдорожчий ...

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

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

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

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