Алгоритм Евклида презентация к уроку информатики и икт (9 класс) на тему. Презентация на тему "алгоритм евклида" Презентация на тему алгоритм евклида

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) 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 if 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. Свойство, что если 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.

Практическая часть

Вопросы и задания:

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

Подведение итогов урока

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

Домашнее задание.

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

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

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

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

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

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

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

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

Задачи воспитания – воспитывать культуру математического мышления, взаимопомощь, выполнять самопроверку и анализировать свои ошибки.

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

Найдите НОД или НОК чисел и расшифруйте фразу:

300

Д: НОД(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)

В последнюю таблицу запишите оставшиеся пары чисел

Ответы:

300

Д: НОД(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. Последний отличный от нуля остаток и есть НОД чисел.

Cлайд 1

Cлайд 2

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 if 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 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.

Класс: 6

Цели урока:

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

Оборудование: компьютер, проектор, экран.

Ход урока

1. Орг.момент (проверка готовности учащихся к уроку, отметка отсутствующих) (1 мин)

2. Устная работа: (6 мин)

1. Замените произведение степенью:

г) а*а*а*а*а

Вычислите: 2 3 ; 5 2 ; 3 3 ; 10 4 .
Найдите значение выражения: (3?3?5?11): (3?11). Какой вывод можно сделать?
Выполните деление a на b , если а=170, b=35. Запишите равенством, чему равно а.

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

Выясните и объясните, делится ли без остатка число а на число 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. Поступаем следующим образом (

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

N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа." title="Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>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). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа." title="Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа."> title="Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа.">

N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями" title="Доказательство Пусть К общий делитель М и. 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. Значит, все общие делители чисел М и N являются делителями" title="Доказательство Пусть К общий делитель М и. 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="Программа на языке Паскаль 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="Программа на языке Паскаль 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.">