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

Спільним дільником цілих чисел а і 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 кроці. Тобто r_n-2=r_n-1q_n+r_n 0≤r_n<r_n-1 r_n-1=r_nq_n+1 Тоді остача r_n і буде НСД, а вказані рівності представляють собою алгоритм Евкліда

а=bq₀+r₀ 0≤r₀<b

b=r₀q₁+r₁ 0≤r₁<r₀

r₀=r₁q₂+r₂ 0≤r₂<r₁ (1)

…………………….

r_n-2=r_n-1q_n+r_n 0≤r_n<r_n-1

r_n-1=r_nq_n+1

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

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

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

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

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

Тобто ▲

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

1.

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

▲

2.

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

НСД: Нехай

Зокрема,

НСК:

Зокрема,

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