Алгоритм Евклида
статья (6 класс) по теме

Работу выполнила ученица 6 класса Суур-оол А.

Руководитель Сакак А.С.

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

Есть одна наука, без которой невозможна никакая другая.

Это математика. Ее понятия, представления и

символы служат тем языком, на котором говорят,

 пишут и думают другие науки.

                            С.Л.Соболев

Математика – самая древняя из наук, она была и остается необходимой людям. Слово «математика» греческого происхождения. Оно означает «наука», «размышление».

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

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

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

В 6-ом классе мы математику начали изучать с темы «Делимость чисел». При ее изучении познакомились с новыми свойствами чисел. Знание признаков делимости, наибольшего общего делителя полезно при сокращении дробей, а при сложении и вычитании дробей с разными знаменателями важно другое умение – отыскивать наименьший общий знаменатель, который является наименьшим общим кратным знаменателей этих дробей. В этой работе я хочу рассказать об одном замечательном способе нахождения наибольшего общего делителя.

Начнем с примера. Даны два числа 24 и 30. Выпишем всех делителей этих чисел.

Делители 24 – 1, 2, 3, 4, 6, 8, 12, 24.

Делители 30 – 1, 2, 3, 5, 6, 10, 15, 30.

Общие делители – 1, 2, 3, 6.

Наибольший общий делитель – 6.  НОД(12,30)=6.

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

         Есть другой способ (он нам известен).

Чтобы найти НОД нескольких натуральных чисел, надо:

1)   Разложить их на простые множители;

2)   Из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел;

3)   Найти произведение оставшихся множителей.

 30 2       24 2

 15 3       12 2              НОД(24,30)=2.3=6

  5  5        6  2

       1             3  3

                     1

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

         Есть замечательный способ отыскания НОД без какой бы ни было предварительной обработки чисел. Такой способ придумали древнегреческие ученые более двух тысяч лет тому назад. Он носит название «алгоритм Евклида». О жизни греческого математика Евклида достоверные данные не известны. Считается, что он жил в III в. до н.э. в г.Александрии. Конечно, как и о других великих людях, о нем известно немало легенд, одна из которых очень поучительна. Египетский царь Птолемей  Iспросил Евклида, нет ли более короткого пути для понимания геометрии, чем тот, который содержится в «Началах» (в современном издании эта книга имеет более 500 станиц, и, конечно, для ее изучения нужно немало времени и усердия). Евклид гордо ответил Птолемею, что «в геометрии нет царской дороги». Евклиду принадлежит выдающееся научное произведение, называемое «Начала». Оно состоит из 13 книг и излагает основы всей древнегреческой математики: элементарной геометрии, арифметики, методов определения площадей, объемов тел. Арифметике посвящены 7, 8, 9-я книги «Начал». Именно здесь и описывается алгоритм Евклида (алгоритм нахождения НОД).

         Прежде чем познакомиться с этим способом, нам придется повторить деление с остатком. Деление одного натурального числа на другое нацело не всегда возможно.

23: 4=5(ост.3)

Число 23 здесь делимое, 4- делитель, 5 – неполное частное и 3 – остаток. В числе 23 содержится 5 раз по 4 да еще 3. Имеем: 23=4.5+3.

Чтобы найти делимое при делении с остатком, надо умножить неполное частное на делитель и к полученному произведению прибавить остаток.

         Теперь можно познакомиться с алгоритмом Евклида. Пусть требуется найти НОД(102; 84). Найдем для этих чисел неполное частное и остаток, т.е. разделим одно на другое:

102=84.1+18,     18<84.

Теперь проделаем такую же операцию для чисел 84 и 18:

84=18.4+12,    12<18.

Следующий шаг – для 18 и 12:

18=12 .1+6, 6<12.

Теперь – для 12 и 6:

12= 6.2+0.

Процесс закончился.

         Может ли этот процесс оказаться бесконечным? Нет, потому что остатки убывают. Теперь присмотримся к записанным равенствам. Из первого ясно, что всякий делитель чисел 102 и 84, в том числе и наибольший, должен быть также и общим делителем, в том числе и наибольшим, чисел 84 и 18. Из второй строчки видно, что НОД(84,18)=НОД(18,12). Третья строчка показывает, что НОД(18,12)=НОД(12,6). Но из последней строчки видно, что число 6 (последний не равный нулю остаток в нашей цепочке равенств) делит нацело число 12 и является НОД чисел 6 и 12, а, следовательно, и 12 и 18, и18 и 84, и 84 и 102. Таким образом, НОД(102,84)=6; мы даже  не пытались разложить на множители числа 102 и 84!

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

         В этой табличке сначала записывают исходные числа, делят в уме, записывая остатки справа, а частные – внизу, пока процесс не закончится. Последний делитель и есть НОД.

 Найдем НОД(468,252) и НОД(1920,1536):

 НОД(468,252)=36,   НОД(1920,1536)=384. Обратите внимание на второй пример. В нем первый остаток оказался и последним. Если искать в этом примере НОД путем разложения на простые множители, то работа займет больше времени.

         Найдем НОД(2016,1320)   НОД(3465,3105)

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

          Напомним, как это делается. Пусть, например, надо найти наименьшее общее кратное чисел 14 и 20. Для этого надо

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

20 2                14 2

     10 2                 7  7

       5 5                  1              НОК(20,14)=2.2.5.7=140

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

   НОК(а,b).

И если вы с помощью алгоритма Евклида нашли НОД двух чисел, то вам остается разделить их произведение на этот НОД. При .этом фактически умножать даже нет необходимости. Найдем НОК(468,252). Мы знаем, что НОД(468,252)=36. Отсюда

Можно найти НОК(468,252).

Литература

1. 1.    Н. Виленкин. Математика 6 кл.- М., Мнемозина, 2001.
2. 2.    Л. Пичурин. За страницами учебника математики. – М., Просвещение, 1990
3. 3.    Большая энциклопедия Кирилла и Мефодия 2007.
4. 4.    В.Гусев. Математика.- М., Просвещение, 1998