Презентація до заняття гуртка алгоритм евкліда. Презентація на тему "Алгоритм евкліду". Ідея алгоритму Евкліда

Клас: 6

Цілі уроку:

• закріпити алгоритм знаходження найбільшого загального дільника за допомогою розкладання на множники;
• повторити супутні визначення та поняття;
• познайомити учнів із алгоритмом Евкліда;
• формувати навички математичної культури

Обладнання: комп'ютер, проектор, екран.

Хід уроку

1. Орг.момент (перевірка готовності учнів до уроку, відмітка відсутніх) (1 хв)

2. Усна робота: (6 хв)

1. Замініть твір ступенем:

г) а * а * а * а * а

1. Обчисліть: 2 3; 5 2; 3 3; 10 4 .
2. Знайдіть значення виразу: (3?3?5?11): (3?11). Який висновок можна зробити?
3. Виконайте поділ aна bякщо а=170, b=35. Запишіть рівністю, чому дорівнює а.

Цю рівність записати у загальному вигляді: а буде поділеним, а b - дільником. Нехай приватна дорівнює q, а залишок r, тоді: а = bq + r , причому q може бути як натуральним числом, і нулем. Чи будь-яким числом може бути r? [r - натуральне число, причому 0 < r < b .] Що можна сказати про числа а та b, якщо r = 0? Поділ націло - окремий випадок поділу із залишком.

4. З'ясуйте та поясніть, чи ділиться без залишку число а на число b, якщо:

а) а = 2 3 * 3 * 5 * 7;

б) а = 2 4 * 3 * 5 7;

b = 2 7 * 3 * 5 4

в) а = 2*3 4*5*13;

b = 2*3 3*5*11.

3. Актуалізація базових знань(10 хв)

1) Запитання:

Що називають дільником числа а ?

Яке число називають простим?

Що означає розкласти число на звичайні множники?

Сформулюйте ознаки подільності на 2, 3, 5, 9,10;

Наведіть приклад однозначної складової числа;

Чи вірно, що число 77-просте число?

Чому, якщо одне число можна розкласти на 2 простих множники, а інше на 3 простих множники, то ці числа не дорівнюють?

Яким числом: простим чи складовим є добуток двох простих чисел?

Що називається найбільшим спільним дільником двох чи більше чисел?

Які числа називаються взаємно-простими?

Повторити способи знаходження НОД: Для пошуку НОД натуральних чисел існують різні алгоритми

1 спосіб:Якщо дані два числа і вони порівняно невеликі, то найкращий алгоритм – безпосередній перебір. Однак для великих чисел знаходити НОД(а;b) шляхом перерахування всіх дільників чисел аі b- процес трудомісткий та ненадійний.

Корисно пам'ятати, що НОД будь-якої кількості чисел не перевищує найменшого з них.

2 спосіб:за допомогою розкладання чисел на множники (найпоширеніший) (Додаток, слайд1)

2) Обчисліть НОД чисел 24 та 16.

3) Розкладіть на прості множники числа: 875 та 8000 та обчисліть НОД цих чисел.

(На прикладі числа 8000 повторити більш простий спосіб розкладання на прості множники чисел, що закінчуються нулями: так як 10 = 2 * 5, то 8000 = 2 * 5 * 2 * 5 * 2 * 5 * 2 * 2 * 2 = = 2 6 * 5 3)

4) Чи може НОД трьох чисел дорівнювати 15, якщо їх добуток дорівнює 3000? [ ні, так як

15 = 3 * 5, отже, число 3 має входити до розкладання кожного з трьох чисел. Але, 3000 = 2 3 * 3 * 5 3.]

5) Р їшіть завдання"У клас привезли підручники: з математики 24, з історії 36 та з географії 48. Яку найбільшу кількість комплектів можна скласти з цих книг так, щоб у кожному було однакове число книг з математики, історії та географії? По скільки книг буде в кожному комплекті ?"

4. Перевірна робота (Додаток, слайд 2) (6 хв)

5. Вивчення нового матеріалу (10 хв)

Вчитель:Вивчений спосіб відшукання НОД(а, b) простий, зрозумілий і зручний, але в нього є істотний недолік: якщо ці числа великі, та ще й не дуже легко розкладаються на множники, то завдання відшукання НОД(а, b) стає досить важким. До того ж може виявитися, що, ґрунтовно попрацювавши, ми переконаємося, що НОД(а, b)=1 і начебто вся робота зроблена даремно.

Евклід знайшов чудовий спосіб відшукання НОД(а,b) без будь-якої попередньої обробки чисел. (Додаток, слайди 3 та 4)Згодом цей алгоритм стали називати алгоритмом Евкліда)

Познайомимося із алгоритмом Евкліда. Нехай потрібно знайти НОД (102; 84). Розділимо одне число на інше та визначимо залишок.

Тепер проробимо таку ж операцію для чисел 84 та 18:

Наступний крок - для 18 та 12:

Тепер для 12 і 6:

0-залишок. Процес закінчився.

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

84 >18 > 12> 6 >0

Якщо придивитися до записаних рівностей, можна встановити, що НОД всіх пар чисел рівні між собою (запропонувати учням подумати -чому?),

тобто НОД(102; 84) = НОД (84; 18) = НОД (18; 12) = НОД (12; 6) = 6. Але число 6-останній, не рівний 0 залишок .

Дійсно, якщо с - довільний спільний дільник чисел а і b, то r = a - bq поділяється на c; і навпаки, якщо с – довільний спільний дільник чисел b та r, то а ділиться на с. Тобто всі спільні дільники пар (а; b) і (b; r) збігаються, а значить, збігаються і їх найбільші спільні дільники.

Зручність алгоритму Евкліда стає особливо помітною, якщо застосувати форму запису як таблиці:

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

Таким чином, найбільшим загальним дільником двох чисел є останній, не рівний 0 залишок при розподілі більшого числа на менше, тобто якщо a = b*q + r, то НОД(a; b) = НОД(b; r)

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

6. Вправи (10 хв)

1. Доцільно розглянути приклад. Нехай треба знайти НОД чисел 323 і 437. Зробити це підбором або розкладанням на прості множники не просто, оскільки жодне з цих чисел не кратне 2, 3, 5, 7, 11. Поступаємо наступним чином (

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

Цілі:повторити вивчені раніше теми Найбільший спільний дільник та найменше спільне кратне, познайомити з алгоритмом Евкліда.

Завдання навчання – повторити поняття Найбільший спільний дільник та найменше загальне кратне правило їх знаходження. Ознайомитись з алгоритмом Евкліда. Закріпити алгоритм Евкліда розв'язанням відповідних завдань.

Завдання розвитку – розвиток логічного мислення, уваги, пам'яті мовлення, вміння самостійно відкривати нові знання, математичну допитливість, пізнавальний інтерес до предмета.

Завдання виховання – виховувати культуру математичного мислення, взаємодопомогу, виконувати самоперевірку та аналізувати свої помилки.

Робота на картках

Знайдіть НОД чи НОК чисел і розшифруйте фразу:

34

16

300

6

1

12

2

34

11

17

Д: НОД(33,88)

Г: НОК(9,40)

В: НОК(14,42)

Е: НОД(48,18)

Р: НОК(17,5)

З: НОД(48,24)

До: НОД (72,12)

Л: НОД(20,14)

Е: НОД(30,18)

М: НОК(25,12)

Т: НОК(4,8,16)

Н: НОК(12,40)

В: НОД(18,35)

А: НОД(17,34)

І: НОД(102,68)

Е: НОД(18,12)

В останню таблицю запишіть пари чисел, що залишилися

Відповіді:

34

16

300

6

1

12

2

34

11

17

А

Л

Г

Про

Р

І

Т

М

Е

В

До

Л

І

Д

А

Д: НОД (33,88) = 11

Г: НОК (9,40) = 360

В: НОК (14,42) = 42

Е: НОД (48,18) = 6

Р: НОК (17,5) = 85

З: НОД(48,24) = 24

До: НОД (72,12) = 12

Л: НОД (20,14) = 2

Е: НОД (30,18) = 6

М: НОК (25,12) = 300

Т: НОК (4,8,16) = 16

Н: НОК(12,40) = 120

В: НОД(18,35) = 1

А: НОД (17,34) = 17

І: НОД (102,68) = 34

Е: НОД (18,12) = 6

Відгадати ще 2 слова

Що можна сказати про числа останньої таблиці? Вони взаємно прості, тобто. якщо ми розкладемо дані числа на прості множники, то вони не будуть однакових множників. Як знайти НОД таких чисел? Нід таких чисел =1. А як знайти НОК, щоб знайти НОК потрібно ці числа перемножити один на одного.

У першій колонці пари чисел, які одне з них не ділиться на інше націло. Тобто. залишок не дорівнює 0.

Як ви знаходили НОД та НОК таких чисел. (За допомогою розкладання цих чисел на прості множники)

НОК (12,40) = 2 3 * 3 * 5 = 120

Згадаймо правило знаходження НОД та НОК, знайдемо та перевіримо формулу НОК(а,в)=(а*b ):НОД(а,b )

3 *3*11=264

НОК (а, в) = (а * b): НОД (а, b)

264=(33*88):11=3*88=264

НОК (20,14) = 2 2 * 5 * 7 = 140

НОК (а, в) = (а * b): НОД (а, b)

140=(20*14):2=10*14=140

НОД (12,40) = 2 2 = 4

НОК (а, в) = (а * b): НОД (а, b)

120=(12*40):4=3*4=120

Вивчення нової теми:

НОД яких пар чисел вийшло 6?

6=НД(48,18)=НД(30,18)=НД(12,18)

Що ви помітили? Як отримали 30? 48-18

Як отримали 12? 30-18

При а>в = НОД (а-в,в)

Тобто. НОД(а,в) При в>а = НОД(а,в-а)

Хто може продовжити цю рівність?

6 = НОД (48,18) = НОД (30,18) = НОД (12,18) = НОД (12,6) = НОД (6,6) = 6

На цьому правилі і ґрунтується алгоритм Евкліда.

Алгоритм Евкліда- ефективний для знаходження двох. Алгоритм названий на честь , який вперше описав його у VII та X книгах «».

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

Давньогрецькі математики називали цей алгоритм-«взаємне віднімання».

Суть цього методу полягає в наступному: віднімай з більшого числа менше поки числа не зрівняються, замінюючи більше різницею. Як тільки це станеться НОД знайдено. (Приклад на дошці – числа 48 та 18)

Перше питання – чи рівні ці числа? Ні не рівні, отже ми з більшого віднімаємо менше 48-18 = 30. 30 не дорівнює 18, отже 30-18 = 12, 18-12 = 6, 12-6 = 6. Тобто ми виконуємо ці дії, доки цифри не зрівняються. Отже НОД(48,18)=6

Знаючи НОД чисел 48 та 18 знайдіть НОК. НОК (48,18) = (48 * 18): 6 = 48 * 3 = 144

Знайдемо з допомогою алгоритму Евкліда НОД(102;68).

Знайдемо НОД (357; 273)

Тут ми 3 рази віднімали число 84 і тричі число 21.

Як, не виробляючи віднімань, дізнатися, скільки віднімань буде в одній серії, і яка різниця вийде? Які випадки слід розглянути? ( Вказівка: згадайте про поділ.)

Загальне правило можна сформулювати так: якщо число aне ділиться на b, то воно замінюється своїм залишком від розподілу на b(в разі a< bцей залишок дорівнює a); якщо aділиться на b, то замінюємо його числом b. Таке саме правило, з перестановкою aі b, діє і для b. Більша кількість ділять на менше, потім менше на перший залишок, потім перший залишок – на другий залишок і т.д., доки не вийде 0. Тодіостанній залишок не рівний 0 – це НОД .

Знайти НОД (357; 273).

357 273 273 84 84 21 НОД (357; 273) = 21

273 1 252 3 21 4

84 21 0

357=1*273+84 273=3*84+21 84=4*21

НОД(357,273)=НД(273,84)=НД(84,21)=21

Зручність алгоритму Евкліда стає особливо помітною, якщо застосувати форму запису як таблиці:

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

Таким чином, найбільшим загальним дільником двох чисел є останній, не рівний 0 залишок при розподілі більшого числа на менше, тобтоякщо a = b *q + r, то НОД(a; b) = НОД(b; r)

Така послідовність операцій і називається алгоритмом Евкліда.

1) За допомогою алгоритму Евкліда знайти НОД чисел:

А) 703, 481, Б) 2112 та 1680; В) 5075 та 1450

НОД(703; 481) = 37

НОД(2112; 1680) = 48

НОД(5075; 1450) =

Перевірити результати на комп'ютері.

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

НОД (150, ____) = ____

НОД(450,315,135)=____

НОД (135, ____) = ____

НОД(2160,1350,1080)=____

НОД (1080, ____) = ____

НОД(5300,3180,2120)=____

НОД (2120, ____) = ____

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

та третього даного числа.

7. Перевірка результатів на комп'ютері. Самостійне вирішення завдань.

1) Для учнів класу приготували однакові подарунки. У всіх подарунках було 120 шоколадок, 280 цукерок та 320 горіхів. Скільки учнів у першому класі, якщо відомо, що їх понад 30?

Відповідь:________________________

2) На станції стоять три пасажирські поїзди: у першому – 418 місць у купейних вагонах, у другому – 494, а у третьому – 456. Скільки купейних вагонів у кожному поїзді, якщо у кожному вагоні однакова кількість місць та їх загальна кількість більша за 20? Відповідь _________________________

3) Зі 156 чайних, 234 білих та 390 червоних троянд зробили букети, причому у всіх букетах троянд кожного виду було порівну і число таких букетів було більше 50. Скільки букетів зробили з цих троянд і скільки троянд кожного виду було в одному букеті? Відповідь_________________

Підсумок уроку. З яким способом знаходження НОД та НОК ми познайомилися на уроці. Алгоритм Евкліда. Як інакше називають цей спосіб? (Метод віднімання). У чому вдосконалили цей метод? За допомогою поділу, більше число ділять на менше, потім менше на перший залишок, потім перший залишок на другий залишок і т.д., доки не отримають 0. Останній відмінний від нуля залишок і є НОД чисел.

Щоб користуватися попереднім переглядом презентацій, створіть собі обліковий запис Google і увійдіть до нього: https://accounts.google.com

Підписи до слайдів:

АЛГОРИТМ ЕВКЛІДА, давньогрецький математик. Працював в Олександрії у 3 ст. до зв. е. Головна праця "Початку" (15 книг), що містить основи античної математики, елементарної геометрії, теорії чисел, загальної теорії відносин та методу визначення площ та обсягів, що включав елементи теорії меж. Вплинув на розвиток математики. Роботи з астрономії, оптики, теорії музики. Евклід (365-300 до. н. е.)

Алгоритм Евкліда Алгоритм Евкліда - це алгоритм знаходження найбільшого загального дільника (НД) двох цілих невід'ємних чисел. Евклід (365-300 до. н. е.) Давньогрецькі математики називали цей алгоритм ἀνθυφαίρεσις або ἀνταναίρεσις - «взаємне віднімання».

Обчислення НОД НОД = найбільший загальний дільник двох натуральних чисел - це найбільше число, на яке обидва вихідні числа діляться без залишку. НОД(a , b)= НОД(a-b, b)= НОД(a, b-a) Замінюємо більше двох чисел різницею більшого і меншого до того часу, що вони стануть рівні. Це і є НОД. НОД (18 , 45) = НОД (18 , 45-18) = НОД (18 , 27) = НОД (18 , 9) = = НОД (9,9) = 9 Приклад:

КРОК Операція M N Умова 1 Введення M 48 2 Введення N 18 3 M  N 48 18, так 4 M>N 48>18, так 5 M:=M-N 30 6 M  N 30  18, так 7 M>N 30 >18, так 8 M:=M-N 12 9 M  N 12 18, так 10 M>N 12 >18, ні 11 N:=N-M 6 12 M  N 12  6, так 13 M>N 12 >6 , так 14 M:=M-N 6 15 M  N 6  6, ні 16 Висновок M

program Evklid; var m, n: integer; begin writeln ("vved 2 chisla"); readln (m, n); while mn do begin якщо m>n then m:=m-n else n:= n-m ; end; write ("nod=",m); readln end.

0. Виконайте на комп'ютері програму Evklid. Протестуйте її при значеннях М = 32, N = 24; M = 696, N = 234. 1 . Перевірити, чи два дані числа взаємно простими. Примітка. Два числа називаються взаємно простими, якщо їхній найбільший спільний дільник дорівнює 1. 2 . Знайти найменше загальне кратне (НОК) чисел n і m, якщо НОК(n, m) = n * m / НОД (n, m). 3 . Дано натуральні числа m і n. Знайти такі натуральні p і q, що не мають спільних дільників, що p/q = m/n. 4. Знайти НОД трьох чисел. Примітка. НОД(a , b , c)= НОД(НОД(a , b), c) Завдання

Попередній перегляд:

Тема: "Алгоритм Евкліда"

Цілі уроку:

1. Освітні:

1. навчитися застосовувати алгоритм Евкліда для знаходження НОД двох та трьох чисел
2. закріпити навички щодо використання алгоритмічних структур «Розгалуження» та «Цикл»
3. отримати досвід написання та налагодження програм мовою програмування Паскаль

1. Виховна:

1. формування самостійності та відповідальності щодо нового матеріалу

1. Розвиваюча:

1. розвиток уваги та аналітичного мислення

План уроку:

1. Організаційний момент
2. Актуалізація знань
3. Пояснення нової теми
4. Практична частина
5. Підбиття підсумків уроку
6. Домашнє завдання.

Організаційний момент

Вітання. Хто відсутній. Число. Тема урока. Питання щодо домашнього завдання.

Актуалізація знань.

Запитання:

Які типи алгоритмічних структур ви знаєте?

Яка структура називається лінійною? (Бл-сх)

Яка структура називається такою, що розгалужується? (Бл-сх)

Яка структура називається циклічною? (Бл-сх)

Які види циклів ви знаєте?

Як реалізується мовою програмування Паскаль цикл із відомим числом повторень?

Як реалізується мовою програмування Паскаль цикл із невідомим числом повторень?

Пояснення нової теми (презентація)

Про Евкліда;

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

Ідея цього алгоритму заснована на:

1. Властивість, що й M>N, то НОД(М, N) = НОД(М - N, N).

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

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

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

НОД(М, М) = М.

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

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

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

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

Блок-схема алгоритму Евкліда

Програма на ЯП Паскаль

program Evklid;

var m, n: integer;

begin

writeln ("vved 2 chisla");

readln (m, n);

While mn do

Begin

If m>n

Then m:=m-n

Else n:=n-m;

End;

Write ("nod =", m);

readln

end.

Практична частина

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

1. Виконайте на комп'ютері програму Evklid. Протестуйте її на значеннях М = 32, N = 24; М=696, N=234.
2. Перевірити, чи два дані числа взаємно простими. Примітка. Два числа називаються взаємно простими, якщо найбільший загальний дільник дорівнює 1.

Підбиття підсумків уроку

Сьогодні на уроці ми познайомилися з алгоритмом Евкліда, що дозволяє знаходити НОД двох цілих невід'ємних чисел, написали програму мовою програмування Паскаль, що реалізує цей алгоритм. На будинок ви отримаєте завдання, в якому ви застосовуватимете даний алгоритм для знаходження НОД трьох чисел та НОК двох чисел.

Домашнє завдання.

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

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

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

А  В = НОД(А, В)  НОК(А, В)

Постановка Завдання Розглянемо таку задачу: потрібно скласти програму визначення найбільшого загального дільника (НД) двох натуральних чисел. Згадаймо математику. Найбільший спільний дільник двох натуральних чисел – це найбільше натуральне число, на яке вони діляться націло. Наприклад, у чисел 12 та 18 є спільні дільники: 2, 3, 6. Найбільшим загальним дільником є ​​число 6. Це записується так: НОД(12,18) = 6. Позначимо вихідні дані як М та N. Постановка задачі виглядає наступним чином : Дано: М, N Знайти: НОД(М, N).

N, то НОД (М, N) = НОД (М - N, N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці і меншого числа." М - N, N) Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці та меншого числа." class="link_thumb"> 4 !}Ідея алгоритму Ідея цього алгоритму полягає в тому властивості, що й M>N, то НОД(М,N) = НОД(М - N,N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їхньої позитивної різниці та меншого числа. N, то НОД (М, N) = НОД (М - N, N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці і меншого числа."> N, то НОД(М,N) = НОД(М - N,N). меншого числа."> N, то НОД(М,N) = НОД(М - N,N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці і меншого числа." М - N, N) Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці та меншого числа."> title="Ідея алгоритму Ідея цього алгоритму полягає в тому властивості, що й M>N, то НОД(М,N) = НОД(М - N,N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їхньої позитивної різниці та меншого числа."> !}

N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки випливає, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками" title="(!LANG:Доказ Нехай До спільний дільник М і.) N (M>N) Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т> п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками" class="link_thumb"> 5 !}Доказ Нехай До спільного дільника М і. N (M>N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки випливає, що К дільник числа М - N. Отже, всі загальні дільники чисел М і N є дільниками їх різниці M-N, у тому числі й найбільший спільний дільник. Звідси: НОД (М, N) = НОД (М - N, N). Друга очевидна властивість: НОД(М, М) = М. N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі загальні дільники чисел М і N є дільниками"> N). Це означає, що М = тК, N = пК , де т, п натуральні числа, причому т> п. Тоді М - N = К (т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками їх різниці M-N, у тому числі і найбільший спільний дільник.Звідси: НОД(М, N) = НОД(М - N,N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки випливає, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками" title="(!LANG:Доказ Нехай До спільний дільник М і.) N (M>N) Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т> п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками"> title="Доказ Нехай До спільного дільника М і. N (M>N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками"> !}

Програма мовою Паскаль Program Evklid; var М, N: integer; begin writeln("Введіть M та N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end. N then M:=M-N else N:=N-M end; write("HOD=",M) end."> N then M:=M-N else N:=N-M end; write("HOD=",M) end."> N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="(!LANG:Програма мовою Паскаль Program Evklid; var М, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="(!LANG:Програма мовою Паскаль Program Evklid; var М, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}

Cлайд 1

Cлайд 2

Алгоритм Евкліда Алгоритм Евкліда - це алгоритм знаходження найбільшого загального дільника (НД) двох цілих невід'ємних чисел. Евклід (365-300 до. н. е.) Давньогрецькі математики називали цей алгоритм ἀνθυφαίρεσις або ἀνταναίρεσις - «взаємне віднімання».

Cлайд 3

Обчислення НОД НОД = найбільший загальний дільник двох натуральних чисел - це найбільше число, на яке обидва вихідні числа діляться без залишку. НОД(a, b)= НОД(a-b, b)= НОД(a, b-a) Замінюємо більше двох чисел різницею більшого і меншого до того часу, що вони стануть рівні. Це і є НОД. НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27) = НОД (18, 9) = = НОД (9,9) = 9 Приклад:

Cлайд 4

КРОК Операція M N Умова 1 ВведенняM 48 2 ВведенняN 18 3 M N 48 18,так 4 M>N 48>18,так 5 M:=M-N 30 6 M N 30 18, так 7 M>N 30>18,так 8 M:= M-N 12 9 M N 12 18,так 10 M>N 12>18,ні 11 N:=N-M 6 12 M N 12 6,так 13 M>N 12>6,так 14 M:=M-N 6 15 M N 6 6, ні 16 ВисновокM

Cлайд 5

program Evklid; var m, n: integer; begin writeln ("vved 2 chisla"); readln (m, n); while mn do begin якщо m>n then m:=m-n else n:=n-m; end; write ("nod=",m); readln end.

Cлайд 6

0.Виконайте на комп'ютері програму Evklid. Протестуйте її при значеннях М = 32, N = 24; M = 696, N = 234. 1. Перевірити, чи два дані числа взаємно простими. Примітка. Два числа називаються взаємно простими, якщо найбільший загальний дільник дорівнює 1. 2. Знайти найменше загальне кратне (НОК) чисел n і m, якщо НОК(n, m) = n * m / НОД (n, m). 3. Дано натуральні числа m і n. Знайти такі натуральні p і q, що не мають спільних дільників, що p/q = m/n. 4. Знайти НОД трьох чисел. Примітка. НОД (a, b, c) = НОД (НОД (a, b), c) Завдання

Cлайд 7

ЕВКЛІД, давньогрецький математик. Працював в Олександрії у 3 ст. до зв. е. Головна праця "Початку" (15 книг), що містить основи античної математики, елементарної геометрії, теорії чисел, загальної теорії відносин та методу визначення площ та обсягів, що включав елементи теорії меж. Вплинув на розвиток математики. Роботи з астрономії, оптики, теорії музики.