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

Предметные результаты: содействовать развитию у обучающихся мыслительных операций: умения анализировать, выделять главное, математически грамотно излагать свои «суждения» и способы решения.

Метапредметные и личностные результаты: уметь выбирать наиболее эффективные способы решения поставленных задач, сравнивать и анализировать информацию, делать выводы на основе полученной информации.

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

Раскладывать на простые множители довольно сложно (например, число 57599).

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

Пример:

Найдем НОД (576, 240).

Решение:

Вспомним, что если два числа кратны одному и тому же числу, то и их разность кратна этому же числу.

Значит, число 576-240=336 кратно любому общему делителю чисел 576 и 240.

С другой стороны, если число является общим делителем 240 и 336, то оно является и делителем числа 576=240+336.

Итак: любой общий делитель чисел 576 и 240 является общим делителем чисел 336 и 240, а любой общий делитель чисел 336 и 240 является общим делителем чисел 576 и 240.
Значит, общие делители чисел 576 и 240 те же самые, что и чисел 336 и 240, а значит, наибольшие среди них тоже одинаковы!

Значит, НОД (576, 240) = НОД (336,240).

Мы можем искать теперь НОД (336,240).

Повторим вычитание: 336-240=96.

Аналогично рассуждениями получим: НОД (336, 240) = НОД (96, 240).

Снова вычтем: 240-96=144. Теперь НОД (96, 240) = НОД (144, 96).

Вычтем еще раз: 144-96=48. НОД (144, 96) = НОД(96,48)

96-48=48. НОД(96,48) = НОД(48.48)=48.

Таким образом, мы получили, что НОД(576; 240) = 48.

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

Это – медленный алгоритм Евклида.

Заметим, что, применяя алгоритм Евклида, мы вычитаем одно и то же число несколько раз, пока разность не станет меньше вычитаемого:

576-240=336;

336-240=96.

Эти два вычитания можно объединить в одно деление с остатком:

576=2∙240+96.

Аналогично далее вместо двух вычитаний тоже можно записать деление с остатком:

240=2∙96+48;

Наконец, 96=2∙48+0.

Последний ненулевой остаток и есть наибольший общий делитель исходных чисел.

Чтобы найти наибольший общий делитель двух чисел, можно заменять большее из них на остаток от деления большего на меньшее. Последний ненулевой остаток и будет наибольшим общим делителем исходных чисел.

Это – быстрый алгоритм Евклида.

Теперь рассмотрим геометрическую иллюстрацию.

Пример:

Найти НОД(48;20).

Решение:

Нарисуем прямоугольник 48 * 20 и в этом прямоугольнике поместим квадрат 20 * 20. Затем, мы видим, что помещается ещё один такой квадрат. (Это соответствует вычитанию из 48 20.)

Оставшийся прямоугольник имеет размер 8 * 20. В него помещается прямоугольник 8 * 8.

Он тоже поместится два раза и в результате останется прямоугольник 8 * 4. (Это соответствует делению с остатком 20 на 8).

В прямоугольник 8*4 два раза помещается квадрат 4*4 без остатка, а значит,

НОД(48;20) = 4.

1.        Дополнительная информация

Рекомендуемые упражнения:

1.      Найдите НОД (10359086, 707818).

2.      Разложите на множители числа 10359086 и 707818.

3.      Каким может быть НОД (2n+1,2n-3)?

4.      Каким может быть НОД (2n+3, n+2)?

5.    Делится ли 197219722010 на 198?