Приветствую Вас, уважаемые Читатели! Сегодня у нас день занимательной арифметики, который будет посвящен одному из первых дошедших до нас арифметических алгоритмов. Только познакомимся мы с ним самым простым и наглядным путем. Итак, поехали!
Вспомните: у Вас под рукой тетрадный лист в клеточку, скучное занятие, чем Вы можете заняться? Для начала - нарисовать прямоугольник!
Ширина и длина выбраны совершенно произвольно. Что будем делать дальше? Я предлагаю взять и разделить прямоугольник на квадраты, взяв за их сторону наименьшую из сторон прямоугольника:
Оставшуюся полоску справа мы уже можем разделить без остатка на три квадрата со стороной 2:
А что бы случилось, если бы мы убрали клетки, а нарисовали бы эту картинку на простом листе бумаги? Приняв сторону оставшегося квадрата за 1, мы бы получили:
Приняв сторону квадрата за 7, получили бы исходный прямоугольник с параметрами 49 на 21, и т.д. Оказывается, мы таким простым геометрическим способом нашли наибольший общий делитель!
- НОД(14,6) = 2
- НОД (10,3) = 1 - взаимно простые числа
- НОД (43,21) = 7
НОД - это сторона самого последнего квадрата!
В школе нас учили находить НОД, используя разложение на простые множители, как на рисунке выше. Древние греки же делали по-другому: свой алгоритм они называли антифарезис, а дошел он до нас по названием "алгоритм Евклида". Таким образом, "провести антифарезис" - значит найти наибольший общий делитель двух чисел. В текстовом виде:
Антифарезис 305 и 24:
- 305 делим на 24, получаем 12 и в остатке 17
- 24 делим на 17, получаем 1 и в остатке 7
- 17 делим на 7, получаем 2 и в остатке 3
- 7 делим на 3, получаем 2 и в остатке 1.
Ответ: НОД (305,24) = 1 - числа взаимно простые.
С первого взгляда кажется, что алгоритм сложнее, чем предложенный на школьной скамье. Однако, впечатление обманчиво: в реальности действительно больших чисел факторизация много затратнее чем алгоритм Евклида, который к тому же многократно модернизирован современными математиками.
Для тех, кто сомневается, предлагаю Вам вручную найти:
НОД (44 758 272 401, 13 164 197 765)
В 1844 Габриэль Ламе доказал, что максимальное количество шагов, которое приведет к окончанию алгоритма Евклида не более чем в пять раз превышает количество десятичных знаков большего из чисел. Так что для нашего случая, максимум придется пройти 55 шагов, и то, это ситуация взаимной простоты...
Лично мне графический способ объяснения алгоритма Евклида очень нравится и помогает не запутаться "что на что делить и из чего что вычитать". Спасибо за внимание!
