Подготовила Ученица 9 « А » класса МОУ СОШ 124 Губарькова Лариса Преподаватель Чушкин А. А. - презентация

1 Подготовила Ученица 9 « А » класса МОУ СОШ 124 Губарькова Лариса Преподаватель Чушкин А. А.

2 Алгоритм Евклида – это способ нахождения наибольшего общего делителя двух целых чисел, а также наибольшей общей меры двух соизмеримых отрезков. Чтобы найти наибольший общий делитель двух целых положительных чисел, нужно сначала большее число разделить на меньшее, затем второе число разделить на остаток от первого деления, потом первый остаток - на второй и т. д. Последний ненулёвой положительный остаток в этом процессе и будет наибольшим общим делителем данных чисел.

3 Алгоритм Евклида известен издавна. Ему уже более 2000 лет. Этот алгоритм сформулирован в Началах Евклида, где из него выводятся свойства простых чисел, наименьшего общего кратного и т. д. Как способ нахождения наибольшей общей меры двух отрезков алгоритм Евклида ( иногда называемый методом попеременного вычитания ) был известен ещё пифагорейцам. К середине XVI в. алгоритм Евклида был распространён на многочлены, от одного переменного в дальнейшем удалось определить алгоритм Евклида и для некоторых других алгебраических объектах.

4 Алгоритм Евклида имеет много применений. Равенства, определяющие его, дают возможность представить наибольший делитель d чисел a и b в виде d=ax+by (x;y- целые числа ), а это позволяет находить решение Диофантовых уравнений 1- й степени с двумя неизвестными.

5 Алгоритм Евклида является средством для представления рационального числа в виде цепной дроби. Он часто используется в программах для электронных вычислительных машин.

6 Возьмём в качестве исходных отрезков сторону AB и AC равнобедренного треугольника ABC, у которого A=C = 72°, B= 36°. В качестве первого остатка мы получим отрезок AD (CD- биссектриса угла C), и, как легко видеть, последовательность и нулевых остатков будет бесконечной. Значит, отрезки AB и AC не соизмеримы.

7 Обозначив исходные числа через а и б, положительные остатки, получающиеся в результате делений, через r1,r2 …, rn, а неполные частные через q1, q2, можно записать алгоритм Евклида в виде цепочки равенств. a=bq1 +r1, b=r1q2 +r2, rn-2=rn-1qn+rn, rn- 1=rnqn+1. Приведём пример. Пусть а =777, b=629. Тогда 777=629*1+148, 629=148*4+37, 148=37*4. Последний ненулевой остаток 37 есть наибольший общий делитель чисел 777 и 629.