Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Найбільший спільний дільник двох чисел. Алгоритм Евкліда Найменше спільне кратне і його зв’язок з найбільшим спільним дільником





Спільним дільником цілих чисел а і b називають таке ціле число с, яке є дільником кожного з чисел

→ с=СД(а,b)

СД чисел а і b називають їх найбільшим СД якщо він ділиться на будь-який інший спільний дільник. Позначення d=(a, b)

Спосіб знаходження НСД був запропонований Евклідом у VII книзі Начал, та носить назву алгоритму Евкліда

Оскільки НСД (а,b)=(-а, b)=(а,-b)=(-а, -b) то завжди можна вважати, що а і b єN. Розділимо а на b з остачею а=bq0+r0 0≤r0<b. Якщо r0=0, то а=bq і НСД(а,b)=b Нехай r0≠0 тоді розділимо b на r0 з остачею: b=r0q1+r1 0≤r1<r0. Якщо r1≠0 то r0 ділимо на r1, r0=r1q2+r2, 0≤r2<r1

………………………………………

Оскільки послідовність остач r0>r1>r2>…>0 є строго спадною і обмежена знизу числом 0, то через зчисленне число кроків остача від ділення rі на rі+1 дорівнюватиме 0Нехай це станеться на n+2 кроці. Тобто rn-2=rn-1qn+rn 0≤rn<rn-1 rn-1=rnqn+1 Тоді остача rn і буде НСД, а вказані рівності представляють собою алгоритм Евкліда

а=bq0+r0 0≤r0<b

b=r0q1+r1 0≤r1<r0

r0=r1q2+r2 0≤r2<r1 (1)

…………………….

rn-2=rn-1qn+rn 0≤rn<rn-1

rn-1=rnqn+1

Теорема. Якщо а, bєN , а не ділиться на b то НСД цих чисел є остання відмінна від нуля остача у алгоритмі Евкліда.

Д-ня. Покажемо спочатку, що rn=СД(а,b) для цього розглянемо рівності 1 знизу вгору. З останньої рівності випливає, що rn-1 ділиться націло на rn, з передостанньої rn-2 ділиться націло на rn, і так далі, з четвертої r1 на rn, з третьої – r0 на rn, а раз так то і b ділиться на rn і а ділиться на rn. Отже rn=СД(а,b) Покажемо, що rn:с, де с-довільний дільник (а,b). Розглянемо рівності 1. Оскільки а:с і b:с, то і з першої рівності r0:с, з другого рівняння r1:с … rn:с, отже rn=НСД(а,b) за означенням.▲

Зазначимо, що НСД 2 чмсел визначається однозначно, справді нехай Оскільки d1 і d2 СД(а,b) тоді за означенням НСД і d1=d2

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

1.

2. Якщо aєZ, bєN і а=bq+r, 0≤r<b, то (а,b)=(b,r)



Д-ня. Позначимо d=(а,b) та покажемо, що d=СД(b,r). Оскільки а:d і b:d і а=bq+r то r:d, отже d=СД(b, r). Покажемо, що d:с=СД(b,r), оскільки с-СД то b:с та r:с, то а:с (а=bq+r) тоді с=СД(а,b) і за означенням d:с. Тобто (а,b)=(b, r)▲

3. Якщо а і bєN і НСД(а,b)=d, то (ма,mb)=md

Для доведення слід проаналізувати рівняння алгоритму Евкліда помножені на m.

4. Для довільних а,bєN , якщо с=СД(а,b), то

Д-ня. (а,b)=

5. . Для довільних а,bєN де (а,b)=d

Д-ня випливає з попереднього

6. .Якщо а,bєN, аb:с і (а,с)=1 →b:с

Д-ня. аb:с (за умовою) bс:с, тому с=СД(аb,bс) з іншого боку (аb,bс)=b(а,с)=1 За означенням НСД b:с▲

7. Для довільних а,bєN існують цілі числа u і v такі, що аu+bv=d, d=(а,b) лінійне представлення НСД чисел а і b.

 

Натуральні числа а і b називаються взаємно простими, якщо їх НСД=1

 

Ціле число М називається СК чисел а і b якщо воно ділиться на кожне з цих чисел.

Додатнє спільне кратне чисел а і b називається найменшим СК, якщо воно ділить кожне спільне кратне.

Теорема.

Д-ня. Позначимо СК (а,b)=m, (а,b)=d. Тоді а:d, b:d і а=а1d, b=b1d причому (а1, b1)=1. Оскільки m=СК(а,b), то m:а, m=аk, kєZ і m:b. Тоді , або = Звідси . Оскільки (а1, b1)=1, то або . Тоді = або Число m буде найменшим при зданих а і b, якщо t≠1.

Тобто

Властивості НСК.

1.

Д-ня. Знайдемо НСК [ab,bc] за останньою теоремою.

2.

Аналогічно тому, як були введені означення НСД та НСК двох чисел можна ввести поняття НСД та НСК кількох чисел за формулами:

НСД: Нехай

Зокрема,

НСК:

Зокрема,


8. Конгруентність цілих чисел.






Date: 2015-04-23; view: 607; Нарушение авторских прав

mydocx.ru - 2015-2020 year. (0.021 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию