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

Широко поширеного в електронній комерції. Також алгоритм використовується при вирішенні лінійних діофантових рівнянь, при побудові безперервних дробів, в методі Штурму. Алгоритм Евкліда є основним інструментом для доказу теорем у сучасній теорії чисел , наприклад таких як теорема Лагранжа о сумі чотирьох квадратів і основна теорема арифметики .

Енциклопедичний YouTube

1 / 5

✪ Математика. Алгоритм Евкліда. Центр онлайн-навчання «Фоксфорд»

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

✪ Алгоритм Евкліда, швидкий спосібзнайти НІД

✪ Математика 71. Найбільший спільний дільник. Алгоритм Евкліда - Академія цікавих наук

✪ 20 Цикл while Алгоритм Евкліда Python

Субтитри

Історія

Давньогрецькі математики називали цей алгоритм ἀνθυφαίρεσις або ἀνταναίρεσις - «Взаємне віднімання». Цей алгоритм не був відкритий Евклідом, оскільки згадка про нього є вже в ТопікАрістотеля. У «Початках» Евкліда він описаний двічі - у VII книзі для знаходження найбільшого загального дільника двох натуральних чисел і в X книзі для знаходження найбільшої загальної міри двох однорідних величин. В обох випадках дано геометричне опис алгоритму, знаходження «загальної міри» двох відрізків.

Опис

Алгоритм Евкліда для цілих чисел

Нехай a (\displaystyle a)і b (\displaystyle b)- цілі числа, не рівні одночасно нулю, та послідовність чисел

a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))

визначено тим, що кожне r k (\displaystyle r_(k))- це залишок від розподілу попереднього числа на попереднє, а передостаннє ділиться на останнє націло, тобто:

a = b q 0 + r 1 (displaystyle a = bq_ (0) + r_ (1),) b = r 1 q 1 + r 2 , (\displaystyle b = r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 , (\displaystyle r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots ) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots ) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)

Тоді НОД( a, b), найбільший спільний дільник aі b, дорівнює r n, останньому ненульовому члену цієї послідовності.

Існуваннятаких r 1 , r 2 , ..., r n , тобто можливість поділу із залишком mна nдля будь-якого цілого mі цілого n≠ 0, доводиться індукцією за m.

Коректністьцього алгоритму випливає з наступних двох тверджень:

• Нехай a = b⋅q + rтоді НОД (a, b) = НОД (b, r).

Доведення

• НОД( r, 0) = rдля будь-якого ненульового r(оскільки 0 ділиться на будь-яке ціле число, крім нуля).

Геометричний алгоритм Евкліда

Нехай дані два відрізки довжини aі b. Віднімемо з більшого відрізка менший і замінимо більший відрізок отриманою різницею. Повторюємо цю операцію, поки відрізки не дорівнюють. Якщо це станеться, то вихідні відрізки можна порівняти, і останній отриманий відрізок є їх найбільшим загальним заходом. Якщо загальної міри немає, процес нескінченний. У такому вигляді алгоритм описаний Евклідом і реалізується за допомогою циркуля та лінійки.

приклад

Для ілюстрації алгоритм Евкліда буде використаний, щоб знайти НОД a= 1071 та b= 462. Для початку від 1071 віднімемо кратне значення 462, поки не отримаємо різницю менше, ніж 462. Ми повинні двічі відібрати 462, ( q 0 = 2), залишаючись із залишком 147:

1071 = 2×462 + 147.

Потім від 462 заберемо кратне значення 147, поки не отримаємо різницю менше, ніж 147. Ми повинні тричі відібрати 147 ( q 1 = 3), залишаючись із залишком 21:

462 = 3×147 + 21.

Потім від 147 заберемо кратне значення 21, поки не отримаємо різницю менше, ніж 21. Ми повинні сім разів відібрати 21 ( q 2 = 7), залишаючись без залишку:

147 = 7×21 + 0.

Таким чином послідовність a > b > r 1 > r 2 > r 3 > … > r n у даному конкретному випадку виглядатиме так:

1071 > 462 > 147 > 21.

Оскільки останній залишок дорівнює нулю, алгоритм закінчується числом 21 і НОД(1071, 462) = 21.

У табличній формі кроки були такі:

Застосування

Розширений алгоритм Евкліда та співвідношення Безу

Формули для r i (\displaystyle r_(i))можуть бути переписані таким чином:

r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots ) НІД (a, b) = r n = a s + b t (\displaystyle (a, b) = r_(n) = as+bt)

Тут sі tцілі. Це уявлення найбільшого, загального, дільника називається співвідношенням «Безу», а числа sі t- Коефіцієнтами  Безу. Співвідношення Безу є ключовим у доказі леми, Евкліда та основної теореми, арифметики.

Ланцюгові дроби

Алгоритм Евкліда досить тісно пов'язаний з ланцюговими дрібницями. Ставлення a/bдопускає подання у вигляді ланцюгового дробу:

a b = [q 0; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).

При цьому ланцюговий дріб без останнього члена дорівнює відношенню коефіцієнтів Безу t/s, взятому зі знаком мінус:

[q 0; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).

Послідовність рівностей, що задає алгоритм Евкліда, може бути переписана у формі:

a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 1 = q N (\displaystyle (\begin(aligned)(\frac(a)(b))&=q_(0)+(\frac(r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2)))(r_ (N-1)))&=q_(N)\end(aligned)))

Останнє доданок у правій частині рівності завжди дорівнює зворотному значенню лівої частини наступного рівняння. Тому перші два рівняння можуть бути об'єднані у формі:

a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac(a)(b))=q_(0)+(\cfrac(1)(q_(1)+(\cfrac(r_( 1))(r_(0))))))

Третя рівність може бути використана, щоб замінити знаменник виразу r 1 /r 0, отримаємо:

a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac(a)(b))=q_(0)+(\cfrac(1)(q_(1)+(\) cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))

Останнє відношення залишків r k /r k−1 завжди може бути замінено з використанням наступної рівності в послідовності і так до останнього рівняння. Результатом є ланцюговий дріб:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [q 0; q 1 , q 2 , … , q N ] (\displaystyle (\frac(a)(b))=q_(0)+(\cfrac(1)(q_(1)+(\cfrac(1)(q_) (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N)))))))))))

Узагальнений алгоритм Евкліда для багаточленів

Алгоритм Евкліда та розширений алгоритм Евкліда природним чиномузагальнюється на кільце багаточленів k[x] від однієї змінної над довільним полем k, оскільки для таких багаточленів визначено операцію поділу із залишком. За виконання алгоритму Евкліда для многочленов аналогічно алгоритму Евкліда цілих чисел виходить послідовність полиномиальных залишків (PRS) .

Приклад для кільця Z[x]

Нехай cont(f) за визначенням - НОД коефіцієнтів многочлена f(x) з Z[x] - змістбагаточлена. Приватне від розподілу f(x) на cont(f) називається примітивною частиноюбагаточлена f(x) і позначається primpart(f(x)). Ці визначення знадобляться для знаходження НОД двох багаточленів p 1 (x)і p 2 (x)у кільці Z[x]. Для многочленів над цілими числами вірно таке:

C o n t ((\displaystyle cont()НОДНІД (c o n t (p 1 (x)) , c o n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x)),cont(p_(2)(x))\),)

P r i m p a r t ((\displaystyle primpart()НІД ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=)НІД ( p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ) . (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\).)

Таким чином, завдання пошуку НОД двох довільних багаточленів зводиться до пошуку НОД примітивних поліномів.

Нехай є два примітивні багаточлени p 1 (x) і p 2 (x) з Z[x], для яких виконується співвідношення між їх ступенями: deg(p 1 (x)) = m і deg(p 2 (x)) = n, m> n. Поділ многочленів із залишком передбачає точну ділимість старшого коефіцієнта поділеного на старший коефіцієнт дільника, у випадку розподіл із залишком виконати неможливо. Тому вводять алгоритм псевдоподілу, який все ж таки дозволяє отримати псевдочастинний і псевдозалишок (prem), які самі по собі належать безлічі багаточленів над цілими числами.

Під псевдоділенням розумітимемо, що самому поділу передує множення полінома p 1 (x) (\displaystyle p_(1)(x))на (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), тобто

L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg ⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

де q (x) (\displaystyle q(x))і r(x) (\displaystyle r(x))- відповідно псевдоприватне та псевдозалишок.

Отже, p 1 (x) , p 2 (x) ∈ Z [x] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), причому deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Тоді алгоритм Евкліда складається з наступних кроків:

1. Обчислення НОД змістів:

C:= (\displaystyle c:=)НІД (cont (p 1), cont (p 2)) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).

2. Обчислення примітивних елементів:

P 1 '(x): = p r i m p a r t (p 1 (x)); (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)

P 2 '(x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)

3. Побудова послідовності поліноміальних залишків:

P 1 ′ (x) , (\displaystyle p_(1)"(x),)

P 2 ′ (x) , (\displaystyle p_(2)"(x),)

P 3 (x) := p r em (p 1 '(x) , p 2 '(x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2) )"(x)),)

P 4 (x) := p r em (p 2 '(x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (x)),)

P 5 (x) := p r em (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x )),)

. . . (\displaystyle...)

P h (x) := p r em (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)

Найбільший спільний дільник

Визначення 2

Якщо натуральне число a ділиться на натуральне число $b$, $b$ називають дільником числа $a$, а число $a$ називають кратним числа $b$.

Нехай $a$ та $b$-натуральні числа. Число $c$ називають спільним дільником і для $a$ і $b$.

Безліч спільних дільників чисел $a$ і $b$ звичайно, оскільки жоден із цих дільників не може бути більшим, ніж $a$. Отже, серед цих дільників є найбільший, який називають найбільшим спільним дільником чисел $a$ і $b$ і для його позначення використовують записи:

$НОД \ (a; b) \ або \ D \ (a; b) $

Щоб знайти найбільший спільний дільник двох, чисел необхідно:

1. Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде найбільшим шуканим спільним дільником.

Приклад 1

Знайти НОД чисел $121$ і $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Вибрати числа, які входять до розкладання цих чисел

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

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

$НОД=2\cdot 11=22$

Приклад 2

Знайти НОД одночленів $63$ і $81$.

Будемо знаходити згідно з представленим алгоритмом. Для цього:

Розкладемо числа на прості множники

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Вибираємо числа, що входять до розкладання цих чисел

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

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

$НОД=3\cdot 3=9$

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

Приклад 3

Знайти НОД чисел $48$ та $60$.

Рішення:

Знайдемо безліч дільників числа $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Тепер знайдемо безліч дільників числа $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$

Знайдемо перетин цих множин: $ \ left \ (( \ rm 1,2,3,4,6,12) \ right \) $ - це безліч буде визначати безліч спільних дільників чисел $ 48 $ і $ 60 $. Найбільший елемент у даній множині буде число $12$. Значить, найбільший спільний дільник чисел $48$ і $60$ буде $12$.

Визначення НОК

Визначення 3

Загальним кратним натуральних чисел$a$ і $b$ називається натуральне число, яке кратне $a$ і $b$.

Загальними кратними чисел називаються числа які діляться на вихідні без залишку.

Найменше із загальних кратних буде називатися найменшим загальним кратним і позначається НОК$(a;b)$ або K$(a;b).$

Щоб знайти НОК двох чисел, необхідно:

1. Розкласти числа на прості множники
2. Виписати множники, що входять до складу першого числа та додати до них множники, які входять до складу другого та не ходять до складу першого

Приклад 4

Знайти НОК чисел $99$ та $77$.

Будемо знаходити згідно з представленим алгоритмом. Для цього

Розкласти числа на прості множники

$99=3\cdot 3\cdot 11$

Виписати множники, що входять до складу першого

додати до них множники, які входять до складу другого та не ходять до складу першого

Знайти добуток чисел, знайдених на кроці 2.Отримане число і буде шуканим найменшим загальним кратним

$НОК=3cdot 3cdot 11cdot 7=693$

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

Твердження, на яких заснований алгоритм Евкліда:

Якщо $a$ і $b$ --натуральні числа, причому $a\vdots b$, то $D(a;b)=b$

Якщо $a$ і $b$ --натуральні числа, такі що $b

Користуючись $D(a;b)= D(a-b;b)$, можна послідовно зменшувати ці цифри до тих пір, поки не дійдемо до такої пари чисел, що одне з них ділиться на інше. Тоді найменше з цих чисел і буде шуканим найбільшим спільним дільником для чисел $a$ і $b$.

Властивості НОД та НОК

1. Будь-яке загальне кратне чисел $a$ і $b$ ділиться на K$(a;b)$
2. Якщо $a\vdots b$ , то $(a;b)=a$

Якщо К$(a;b)=k$ і $m$-натуральне число, то К$(am;bm)=km$

Якщо $d$-загальний дільник для $a$ і $b$, то К($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $

Якщо $a\vdots c$ і $b\vdots c$ , то $\frac(ab)(c)$ - загальне кратне чисел $a$ і $b$

Для будь-яких натуральних чисел $a$ і $b$ виконується рівність

$D(a;b)\cdot До(a;b)=ab$

Будь-який спільний дільник чисел $a$ і $b$ є дільником числа $D(a;b)$

Алгоритм Евкліда- це спосіб знаходження найбільшого загального дільника (НДД) двох цілих чисел. Оригінальна версія алгоритму, коли НОД перебуває відніманням, було відкрито Евклидом (III в. е.). Нині найчастіше при обчисленні НОД алгоритмом Евкліда використовують поділ, оскільки цей метод ефективніший.

Обчислення НОД поділом

Найбільший спільний дільник пари чисел – це найбільше число, яке ціле ділить обидва числа пари. Нехай потрібно обчислити НОД для чисел 108 і 72. Алгоритм обчислення поділом буде таким:

1. Розділимо більше (ділене) на менше (ділитель): 108 / 72 = 1, залишок 36.
2. Оскільки залишок не дорівнював нулю, то зробимо дільник ділимим, а залишок – дільником: 72 / 36 = 2, залишок 0.
3. Коли залишок дорівнює нулю, дільник є шуканим НОД для пари заданих чисел. Тобто НОД(108, 72) = 36. Справді, 108/36 = 3 і 72/36 = 2.

У цьому алгоритмі розподіл повторюється до тих пір, поки залишок не стане рівним нулю. Коли він таким стає, НОДом є дільник останнього поділу. Наприклад, потрібно знайти НОД(106, 16):

1. 106/16 = 6, залишок 10
2. 16/10 = 1, залишок 6
3. 10/6 = 1, залишок 4
4. 6/4 = 1, залишок 2
5. 4/2 = 2, залишок 0
6. НОД(106, 16) = 2

Обчислення НІД відніманням

При знаходженні НОД відніманням також потрібно досягти нуля. Алгоритм схожий з методом поділу, тільки тут на кожному наступному етапі віднімається і зменшується стають віднімання і різницю з попереднього кроку. При цьому завжди з більшої кількості віднімається менше. Цей різновид алгоритму підходить тільки для позитивних цілих чисел.

Нехай потрібно знайти НОД(108, 72):

1. 108 - 72 = 36
2. 72 - 36 = 36
3. 36 - 36 = 0
4. НОД(108, 72) = 36

Знайдемо НОД(44, 60):

1. 60 - 44 = 16
2. 44 - 16 = 28
3. 28 - 16 = 12
4. 16 - 12 = 4
5. 12 - 4 = 8
6. 8 - 4 = 4
7. 4 - 4 = 0
8. НОД(44, 60) = 4

Цей алгоритм іноді описують по-іншому. Віднімання закінчують раніше, на кроці, коли одне число націло ділить інше. Тобто комбінують віднімання з перевіркою ділимості. Тоді перебування НОД для 44 і 60 буде виглядати так:

1. Чи ділить 44 націло 60? Ні. 60 – 44 = 16.
2. Чи ділить 16 націло 44? Ні. 44 – 16 = 28.
3. Чи ділить 16 націло 28? Ні. 28 – 16 = 12.
4. Чи ділить 12 націло 16? Ні. 16 – 12 = 4.
5. Чи ділить 4 націло 12? Так. Отже, НОД(44, 60) = 4.

Зверніть увагу, НОДом є не приватне, а дільник. Якщо у прикладі ми розділимо 12 на 4, то отримаємо 3. Але це не НОД.

Доказ алгоритму Евкліда

Візьмемо до уваги факт, що якщо одне натуральне число з пари націло ділить інше, то їх НОД дорівнюватиме меншому з них. Записати це можна так:

якщо a/b націло, то НОД(a, b) = b. Наприклад, НОД(15, 5) = 5.

Таким чином, якщо зрештою ми приходимо до пари чисел, одне з яких ділить націло інше, то менше буде для обох найбільшим спільним дільником. Саме така пара чисел шукається алгоритмом Евкліда: одне число ціле ділить інше.

Другий факт. Потрібно довести, що якщо одне число більше за інше, то їх найбільший спільний дільник дорівнює найбільшому загальному дільнику для меншого числа з пари, і різниці більшого і меншого чисел. Це можна записати так:

якщо a< b, то НОД(a, b) = НОД(a, b - a).

Довести, що НОД(a, b) = НОД(a, b - a) можна в такий спосіб. Нехай b – a = c. Якщо якесь число x ділить націло a і b, воно буде також ділити націло c. Адже якщо a і b різні, то дільник у них вкладається ціле, але різне число разів. І якщо відняти одне з іншого, то дільник також повинен вкладатися ціле число разів у отриману різницю.

Якщо послідовно зменшувати a і b, то рано чи пізно дійдемо такого значення меншого з них, яке націло ділить більше. Найменше у такій парі буде найбільшим спільним дільником для вихідної пари натуральних чисел. У цьому полягає алгоритм Евклида.

Розглянемо два основних методи знаходження НОД двома основними способами: з використанням алгоритму Евкліда та шляхом розкладання на прості множники. Застосуємо обидва методи для двох, трьох та більшої кількості чисел.

Алгоритм Евкліда для знаходження НОД

Алгоритм Евкліда дозволяє легко вирахувати найбільший спільний дільник для двох позитивних чисел. Формулювання та доказ алгоритму Евкліда ми навели у розділі «Найбільший спільний дільник: визначник, приклади».

Суть алгоритму полягає в тому, щоб послідовно проводити розподіл із залишком, у ході якого виходить ряд рівностей виду:

a = b · q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Ми можемо закінчити поділ тоді, коли r k + 1 = 0, при цьому r k = НОД (a, b).

Приклад 1

64 і 48 .

Рішення

Введемо позначення: a = 64 , b = 48 .

На основі алгоритму Евкліда проведемо поділ 64 на 48 .

Отримаємо 1 і залишок 16 . Виходить, що q 1 = 1 r 1 = 16 .

Другим кроком розділимо 48 на 16 отримаємо 3 . Тобто q 2 = 3, а r 2 = 0.Таким чином, число 16 – це найбільший спільний дільник для чисел з умови.

Відповідь:НОД (64, 48) = 16 .

Приклад 2

Чому дорівнює НОД чисел 111 і 432 ?

Рішення

Ділимо 432 на 111 . Відповідно до алгоритму Евкліда отримуємо ланцюжок рівностей 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Таким чином, найбільший спільний дільник чисел 111 і 432 - Це 3 .

Відповідь:НОД (111, 432) = 3 .

Приклад 3

Знайдіть найбільший спільний дільник чисел 661 та 113 .

Рішення

Проведемо послідовно розподіл чисел і отримаємо НОД (661 , 113) = 1 . Це означає, що 661 та 113 – це взаємно прості числа. Ми могли б з'ясувати це до початку обчислень, якби звернулися до таблиці простих чисел.

Відповідь:НОД (661, 113) = 1 .

Знаходження НОД за допомогою розкладання чисел на прості множники

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

Приклад 4

Якщо ми розкладемо числа 220 і 600 на прості множники, то отримаємо два твори: 220 = 2 · 2 · 5 · 11і 600 = 2 · 2 · 2 · 3 · 5 · 5. Спільними у цих двох творах будуть множники 2, 2 та 5. Це означає, що НОД (220, 600) = 2 · 2 · 5 = 20.

Приклад 5

Знайдіть найбільший спільний дільник чисел 72 і 96 .

Рішення

Знайдемо всі прості множники чисел 72 і 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Спільними для двох чисел прості множники: 2, 2, 2 та 3. Це означає, що НОД (72, 96) = 2 · 2 · 2 · 3 = 24.

Відповідь:НОД (72, 96) = 24 .

Правило знаходження найбільшого загального дільника двох чисел ґрунтується на властивостях найбільшого загального дільника, згідно з яким НОД (m · a 1 , m · b 1) = m · НОД (a 1 , b 1) , де m – будь-яке ціле позитивне число.

Знаходження НОД трьох та більшої кількості чисел

Незалежно від кількості чисел, для яких нам потрібно знайти НОД, ми будемо діяти по тому самому алгоритму, який полягає в послідовному знаходженні НОД двох чисел. Засновано цей алгоритм на застосуванні наступної теореми: НОД кількох чисел a 1 , a 2 , … , a kдорівнює числу d k, яке знаходиться при послідовному обчисленні НОД (a 1 , a 2) = d 2, НОД (d 2 , a 3) = d 3 , НОД (d 3 , a 4) = d 4 , … , НОД (d k - 1 , a k) = d k .

Приклад 6

Знайдіть найбільший спільний дільник чотирьох чисел 78, 294, 570 і 36 .

Рішення

Введемо позначення: a 1 = 78 , a 2 = 294 , a 3 = 570 , a 4 = 36 .

Почнемо з того, що знайдемо НОД чисел 78 та 294: d 2 =НІД (78 , 294) = 6 .

Тепер приступимо до знаходження d 3 = НОД (d 2, a 3) = НОД (6, 570). Згідно з алгоритмом Евкліда 570 = 6 · 95 .Це означає що d 3 =НІД (6 , 570) = 6 .

Знайдемо d 4 = НОД (d 3, a 4) = НОД (6, 36). 36 ділиться на 6 без залишку. Це дозволяє нам отримати d 4 =НІД (6 , 36) = 6 .

d 4 = 6тобто НОД (78 , 294 , 570 , 36) = 6 .

Відповідь:

А тепер давайте розглянемо ще один спосіб обчислення НОД для тих та більшої кількості чисел. Ми можемо знайти НОД, перемноживши всі загальні прості множники чисел.

Приклад 7

Обчисліть НОД чисел 78, 294, 570 та 36 .

Рішення

Зробимо розкладання даних чисел на прості множники: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3 .

Для всіх чотирьох чисел загальними простими множниками будуть числа 2 та 3.

Виходить, що НОД (78, 294, 570, 36) = 2 · 3 = 6.

Відповідь:НОД (78, 294, 570, 36) = 6 .

Знаходження НІД негативних чисел

Якщо нам доводиться мати справу з негативними числами, то знаходження найбільшого спільного дільника ми можемо скористатися модулями цих чисел. Ми можемо так вчинити, знаючи властивість чисел із протилежними знаками: числа nі - nмають однакові дільники.

Приклад 8

Знайдіть НОД негативних цілих чисел − 231 і − 140 .

Рішення

На виконання обчислень візьмемо модулі чисел, даних за умови. Це будуть числа 231 та 140 . Запишемо це коротко: НОД (− 231 , − 140) = НОД (231, 140). Тепер застосуємо алгоритм Евкліда для знаходження простих множників двох чисел: 231 = 140 · 1 + 91; 140 = 91 · 1 + 49; 91 = 49 · 1 + 42; 49 = 42 · 1 + 7 та 42 = 7 · 6. Отримуємо, що НОД (231, 140) = 7 .

А тому що НІД (− 231 , − 140) = НІД (231 , 140) , то НОД чисел − 231 і − 140 дорівнює 7 .

Відповідь:НОД (− 231 , − 140) = 7 .

Приклад 9

Визначте НОД трьох чисел − 585 , 81 та − 189 .

Рішення

Замінимо негативні числа у наведеному переліку на їх абсолютні величини, отримаємо НОД (− 585 , 81 , − 189) = НІД (585 , 81 , 189) . Потім розкладемо всі дані числа на прості множники: 585 = 3 · 3 · 5 · 13, 81 = 3 · 3 · 3 · 3 і 189 = 3 · 3 · 3 · 7. Загальними для трьох чисел є прості множники 3 та 3 . Виходить, що НОД (585 , 81 , 189) = НОД (− 585 , 81 , − 189) = 9 .

Відповідь:НОД (− 585 , 81 , − 189) = 9 .

Якщо ви помітили помилку в тексті, будь ласка, виділіть її та натисніть Ctrl+Enter

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

Найбільший спільний дільник

Розглянемо таке завдання: потрібно скласти програму визначення найбільшого загального дільника (НДД) двох натуральних чисел.

Згадаймо математику. Найбільший спільний дільник двох натуральних чисел - це найбільше натуральне число, яке вони діляться націло. Наприклад, у чисел 12 і 18 є спільні дільники: 2, 3, 6. Найбільшим спільним дільником є ​​число 6. Це записується так:

НОД(12, 18) = 6.

Позначимо вихідні дані як М u N. Постановка задачі виглядає так:
Дано:М, N
Знайти:НОД(М, N).

В даному випадку якоїсь додаткової математичної формалізації не потрібно. Сама постановка завдання має формальний математичний характер. Не існує формули для обчислення НОД(М, N) за значеннями М і N. Але досить давно, задовго до появи ЕОМ, був відомий алгоритмічний спосіб вирішення цього завдання. Називається він алгоритмом Евкліда .

Ідея алгоритму Евкліда

Ідея цього алгоритму полягає в тому властивості, що й M>N, то

НОД(М, N) = НОД(М - N, N).

Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці (модуля їх різниці) та меншого числа.

Легко довести цю властивість. Нехай До - загальний дільник М u N (M> N). Це означає, що М = mК, N = nК, де m, n – натуральні числа, причому m > n. Тоді М - N = К(m - n), звідки випливає, що К - дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками їх різниці М - N, у тому числі найбільший спільний дільник.

Друга очевидна властивість:

НОД(М, М) = М.

Для "ручного" рахунку алгоритм Евкліда виглядає так:

1) якщо числа рівні, то взяти будь-яке з них як відповідь, інакше продовжити виконання алгоритму;

2) замінити більшу кількість різницею більшого та меншого з чисел;

3) повернутись до виконання п. 1.

Розглянемо цей алгоритм з прикладу М=32, N=24:

Структура алгоритму - цикл поки з вкладеним розгалуженням. Цикл повторюється, поки значення М та N не рівні один одному. У розгалуженні більше двох значень замінюється з їхньої різницю.

А тепер подивіться на таблицю трасування алгоритму для вихідних значень М = 32, N = 24.

Крок	Операція	M	N	Умова
1	введення М	32
2	введення N		24
3	M ¹ N			32 ¹ 24, так
4	M>N			32>24, так
5	M:=M-N	8
6	M ¹ N			8 ¹ 24, так
7	M>N			8>24, ні
8	N:=N-M		16
9	M ¹ N			8 ¹ 16, так
10	M>N			8>16, ні
11	N:=N-M		8
12	M ¹ N			8 ¹ 8, ні
13	висновок M	8
14	кінець

У результаті вийшов правильний результат.

Програма на АЯ та на Паскалі

Запишемо алгоритм на АЯ та програму на Паскалі.

Запитання та завдання

1. Виконайте на комп'ютері програму Evklid. Протестуйте її на значеннях М = 32, N = 24; М=696, N=234.

2. Складіть програму знаходження найбільшого загального дільника трьох чисел, використовуючи таку формулу:

НОД(А, B, С) = НОД(НОД(А, В), С).

3. Складіть програму знаходження найменшого загального кратного (НОК) двох чисел, використовуючи формулу:

А × В = НОД (А, В) × НОК (А, В).