занятие 15

Тема: Делимость и остатки

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

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

При условии, что a > b выполняется равенство: НОД (a;b) = НОД (b;a - b).

Вот как работает алгоритм Евклида для конкретных чисел:

НОД (451; 287) = НОД (287; 451-284) = НОД (287; 164) = НОД (164; 287 - 164) =                        = НОД (164; 123) = НОД (123; 164 - 123) = НОД (123; 41) = НОД (41; 123 - 41) =                          = НОД (82; 41) = НОД (41; 41) = 41.

Применение алгоритма Евклида.

     Задача 19. Найдите наибольший общий делитель чисел 2n + 13 и n + 7. 

Решение: НОД (2n + 13; n + 7) = НОД (n + 7; n + 6) = НОД (n + 6; 1) = 1.

Задачи для самостоятельного решения

Учитывая, что для сокращения дробей необходим наибольший общий делитель, который находится с помощью НОД, решите:

Задача 20. Докажите, что дробь несократима ни при каком натуральном n.

     Задача "не в тему №1". Отец вдвое старше сына. Сын родился, когда отцу было 28 лет. Сколько лет отцу сейчас?

     Задача "не в тему №2". Как разрезать клетчатый квадрат 5 на 5 на 8 различных фигур, чтобы все клеточки остались целыми. Фигуры считаются различными, если их нельзя наложить друг на друга так, чтобы они совпали.

     Задача "не в тему №3". На столе стоят 8 стаканов с водой. Разрешается взять любые два стакана и перелить часть воды из одного стакана в другой так, чтобы воды в них стало поровну. Как несколькими такими переливаниями добиться, чтобы воды во всех стаканах стало поровну?

Решения и ответы

     Задача 20. НОД (12n +1; 30n + 2) = НОД (12n +1; 18n +1) = НОД (12n + 1; 6n) =                   = НОД (6n; 6n + 1) = 1, что говорит о том, что числитель и знаменатель этой дроби не имеют общих делителей, кроме 1, то есть дробь несократима ни при каком натуральном n.

     Задача "не в тему №1. Отец вдвое старше сына, то есть до рождения сына отец прожил столько же лет, сколько и после его рождения. 28 + 28 = 56.

     Ответ: отцу 56 лет

     Задача "не в тему №2". Вспоминаем про фигурки пентамино

С помощью этих фигурок можно замостить квадрат 5 на 5 различными способами и затем разрезать. 

     Задача "не в тему №3". Пронумеруем стаканы числами от 1 до 8. Сначала уравняем количество воды в первом и втором, третьем и четвёртом, пятом и шестом,, седьмом и восьмом. Затем уравняем первый стакан с третьим, а второй - с четвертым. Теперь во всех стаканах с первого по четвертый воды поровну. Добьёмся того же в стаканах с пятого по восьмой. Уффф!

Теперь уравниваем первый с пятым, второй с шестым, третий с седьмым, четвертый - с восьмым.

Готово!