Алгоритм Евклида.
занимательные факты по алгебре (8 класс)

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

Слово «алгоритм» является русской транскрипцией латинизированного имени арабского математика   ал – Хорезми Абу Абдуллы Мухаммеда ибн  ал – Маджуси – (787- ок.850) и означает список команд, выполняя которые можно достигнуть требуемого результата. Алгоритм нахождения наибольшего общего делителя по заданным натуральным числам   и  изложил Евклид в  IX  книге «Начал».

            Пусть даны два числа  ,  .

                 
Имеем, следовательно, процесс оборвется максимум через    шагов. Всякий делитель    и   делит.  Если же просматривать эту цепочку равенств от последнего к первому, то видно, что ,  , и т.д., т.е.    делит    и .  Поэтому   - наибольший общий делитель чисел    и , т.е.  .

Этот алгоритм, кроме того, дает практический способ нахождения чисел   и   из   таких, что  .

Действительно, из цепочки равенств имеем:

         Оценку количества делений в  алгоритме Евклида  дает следующая теорема, доказанная французским математиком Г.Ламе в 1845г.

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

Пусть a ≥ b – натуральные числа и b записывается m цифрами в десятичной системе счисления. Это означает, что 10m-1  ≤ b < 10m. Требуется доказать, что алгоритм Евклида, применимый к числам a, b, выполнит не более 5m делений с остатком.

Положим r0=a и обозначим r1=b,r2,…,rn – последовательность делителей в алгоритме Евклида. Тогда ri-1=qiri+ri+1, 0≤ ri+1i, i=1,2,…,n-1, rn=(a,b). Докажем справедливость неравенств rn-I ≥ λi, i=1,2,…,n-1, где  есть корень квадратного уравнения λ2-λ-1=0. Для этого воспользуемся методом математической индукции. При i=0 имеем rn ≥ 1=λ0. При i=1 находим rn-1≥ rn+1≥2≥λ, так что рассматриваемое неравенство опять справедливо. Предположим теперь, что 1≤k<n-1 неравенство rn-I ≥ λi, i=1,2,…,n-1 выполняется при всех  i ≤ k. Имеем следующую цепочку равенств и неравенств rn-k-1=qn-krn-k+rn-k+1≥rn-k+rn-k+1≥λk+λk-1=λk+1.

Таким образом, рассматриваемое неравенство выполняется и при i=k+1. Это доказывает справедливость неравенства при всех i=1,2,…,n-1. Поскольку 10m>b и b=r1≥λn-1, видим, что m>(n-1)lgλ>(n-1)/5. В последнем неравенстве была использована оценка λ>101/5=1,58… Таким образом, n<5m+1. 

Пример.

Пусть   =252, =123.  Запишем деление уголком, и каждый раз то, что было в уголке, т.е. делитель приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок.

            252|123

            246|2

        123|6

        12  |20

      6|   3

      6|2

      0

Запись того же самого в виде цепочки равенств:

252=123∙2+6

123=6∙20+3

6=3∙2

Таким образом,  (252, 123)=3.

Линейное представление наибольшего общего делителя:

3=123–6∙20=123–(252 – 123∙2)∙20=123–252∙20+123∙40=252∙(-20)+123∙41,

и тогда    и    равны, соответственно, -20  и  41.

Т.е.  3=252∙(-20) + 123∙41.

Задачи

1. Найдите      а)   =(81719, 52003),

                        б)   =(33649, 30107),

                        в)   =(317811, 196418)

и их представление в виде   ,  

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

4.4.   Неопределенные уравнение первой степени с двумя неизвестными

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

             Наиболее известной, решенной Диофантом, является задача «о разложении на два квадрата». Ее эквивалентом является известная всем теорема Пифагора. Эта теорема была известна в Вавилонии, возможно ее знали и в Древнем Египте, но впервые она была доказана в пифагорейской школе.

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

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

           Рассмотрим линейное уравнение  (1),                                 

где , ,  - ненулевые целые числа.

           Если  не делится на , то уравнение (1) в целых числах не имеет решения.

           Если , то на него все коэффициенты уравнения (1) можно сократить (предполагается, что решение у (1) есть). Поэтому далее будем рассматривать случай взаимно простых  и , т.е. .

          Пусть  и  удовлетворяют уравнению (1),

 ,  с целым параметром  задают все решения уравнения.

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

Пример 1. . Здесь частное решение легко подбирается , , поэтому общее решение: , .

Пример 2. . Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент: . Подставляя вместо  числа 0, 1, 2, 3, 4 (остатки при делении на 5), мы получим частное решение , , тогда общее решение ,

Пример 3. . Здесь использовать предыдущий способ затруднительно (придется подставлять 14 значений ). Поэтому мы приведем универсальный метод поиска частного решения. Из задачи 12.26 следует существование  и  таких, что . Тогда ,  будет частным решением нашего уравнения. Построим  и  явно. Из алгоритма Евклида имеем: , , . Из последнего равенства: , подставляя  (из второго равенства), получим . Наконец, подставляя  (из первого равенства), получим . Итак, , , , .

Другим универсальным методом является использование цепных дробей.

Последовательность равенств (1) можно записать в виде равносильной цепочки

,        ,        , …

,                .                                (2)                    

Поставим теперь задачу выразить отношение  через одни только числа , , …, , . На основании равенств (2) находим:

                                (3)                            

В этом равенстве  - целое число, , , …,  - целые положительные числа. Выражение такого вида, как правая часть равенства (3), называется конечной цепной дробью.

          Рассмотрим  теорию уравнений  первой степени с двумя неизвестными

         ах+by+c=0  (1),  где а и b  – целые числа, отличные от нуля, а с – произвольное целое  в   общем  виде. Будем считать, что коэффициенты а и b  не имеют общих делителей, т.к. имеет  место следующая теорема.

  Теорема 1. Если в уравнении   ах+by+c=0, (a,b)=d>1 и cd, то

                      оно равносильно уравнению  a1х+b1y+c1=0, в

                      котором (a1,b1)=1.

Действительно, если наибольший общий делитель этих коэффициентов d=(a,b) отличен от единицы, то справедливы равенства a=a1d, b=b1d; уравнение (1) принимает вид

(а1х+b1y)d+c=0  (2)

и может иметь целые решения только в том случае, когда с делится на d. Таким образом, в случае (a,b)=d≠1все коэффициенты уравнения (1) должны делиться на d, и, сокращая (2) на d, придем к уравнению

a1х+b1y+c1=0, где ,

коэффициенты которого а1 и b1 взаимно просты.

  Теорема 2. Если в уравнении ах+by+c=0, (a,b)=d>1  и с не

                      делится на d, то уравнение целых решений

                      не имеет.

Рассмотрим сначала случай, когда с=0. Уравнение (1) перепишется так: ах+by=0    (3).

Решая  это уравнение относительно х, получим:

.

Ясно, что х будет принимать целые значения в том и только в том случае, когда у делится на а без остатка. Но всякое целое у, кратное а, можно записать в виде   у=аt, где t принимает произвольные целые значения (t=0,±1,±2,…).  Подставим это значение у в предыдущее уравнение, тогда

 И мы получаем формулы, содержащие все целые решения уравнения (3): x=-bt,    y=at   (t=0,±1,±2,…).

Перейдем теперь к случаю с≠0.

Для нахождения всех целых решений уравнения (1) достаточно найти какое-нибудь одно его решение, т.е. найти такие целые числа х0, у0, для которых   ах0+by0+c=0.

       Теорема 3. Пусть a и b взаимно просты и [х0,у0] – какое-нибудь

                           решение уравнения ах+by+c=0. Тогда формулы

                           x=x0 - bt,

                           y=y0 +at

                           при t=0,±1,±2,… дают все решения уравнения (1).

Как  же найти какое-нибудь одно решение [х0,у0] уравнения (1) в общем случае, когда с≠0? Начнем с примера, в котором воспользуемся непрерывными цепными дробями.

Пример 4. Найти все целые решения уравнения 127х - 52y+1=0.

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

Правильную дробь  заменим равной ей дробью .

Тогда получим:

Проделаем такие же преобразования с полученной в знаменателе неправильной дробью :

Теперь исходная дробь имеет вид:

Повторим те же рассуждения для дроби :

Тогда

Выделяя целую часть неправильной дроби :

Придем к окончательному результату:

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

Приведем полученное выражение к общему знаменателю и отбросим его, тогда

127·9-52·22+1=0.

Из сопоставления полученного равенства с уравнением 127х-52y+1=0 следует, что х=9, у=22 будет решением этого уравнения, и согласно теореме все его решения будут содержаться в прогрессиях

х = 9 + 52t,    y = 22 + 127t    (t=0,±1,±2,…).

В общем случае для нахождения решения уравнения ах+by+c=0 надо разложить отношение коэффициентов при неизвестных в цепную дробь, отбросить ее последнее звено и проделать выкладки, подобные тем, которые были проведены выше.

Можно показать, что пара чисел [х0,у0], где

х0=(-1)n-1 cQn-1  ,   y0=(-1)n cPn-1 ,

является решением уравнения (13) и согласно теореме все решения этого уравнения имеют вид:

x=(-1)n-1 cQn-1 – bt,   y=(-1)n cPn-1 +at   (t=0,±1,±2,…).

Для решения таких уравнений может быть использован и так называемый метод «спуска». Алгоритм этого метода рассмотрим на конкретном примере.

Пример 5. Пусть дано уравнение 5x+8y=39.

Выберем неизвестное, имеющее наименьший коэффициент (в нашем случае это х), и выразим его через другое неизвестное:

Выделим целую часть:

Очевидно, что х будет целым, если выражение   окажется целым, что, в свою очередь, будет иметь место тогда, когда число 4–3y  без остатка делится на 5.  

Введем дополнительную целочисленную переменную z следующим образом: 4–3y=5z. В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами. Решать его будем уже относительно переменной y, рассуждая точно также как в п.1: . Выделяя целую часть, получим:

Рассуждая аналогично предыдущему, вводим новую переменную u:3u=1-2z.

Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z:

Требуя, чтобы   было целым, получим: 1–u=2v, откуда u=1–2v. Дробей больше нет, спуск закончен.

Теперь необходимо «подняться вверх». Выразим через переменную v сначала z, потом y и затем x:

Формулы x=3+8v  и y=3–5v, где v – произвольное целое число, представляют общее решение исходного уравнения в целых числах.

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

Рассмотрим линейное уравнение ,                                              (1)

где , ,  - ненулевые целые числа.

 Если  не делится на , то уравнение (1) в целых числах не имеет решения.

Если , то на него все коэффициенты уравнения (1) можно сократить (предполагается, что решение у (1) есть). Поэтому далее будем рассматривать случай взаимно простых  и , т.е. .

 Пусть  и  удовлетворяют уравнению (1). Докажите, что ,  с целым параметром  задают все решения уравнения (1).

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

Решить: . Здесь частное решение легко подбирается , , поэтому общее решение: , .

Решить: . Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент: . Подставляя вместо  числа 0, 1, 2, 3, 4 (остатки при делении на 5), мы получим частное решение , , тогда общее решение , .

Решить: . Здесь использовать предыдущий способ затруднительно (придется подставлять 14 значений ). Поэтому мы приведем универсальный метод поиска частного решения. Из задачи 12.26 следует существование  и  таких, что . Тогда ,  будет частным решением нашего уравнения. Построим  и  явно. Из алгоритма Евклида имеем: , , . Из последнего равенства: , подставляя  (из второго равенства), получим . Наконец, подставляя  (из первого равенства), получим . Итак, , , , .

Другим универсальным методом является использование цепных дробей.

Последовательность равенств (1) можно записать в виде равносильной цепочки

,        ,        , …

,                .                                                     (2)

Поставим теперь задачу выразить отношение  через одни только числа , , …, , . На основании равенств (2) находим:

                                                             (3)

В этом равенстве  - целое число, , , …,  - целые положительные числа. Выражение такого вида, как правая часть равенства (3), называется конечной цепной дробью и сокращенно обозначается .

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

Решить уравнение: xy + x–3y = –4

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

Другим способом решения этого уравнения является выражение  через : . Так как  должно быть целым число, то  может быть равно только 1, , 7, .

Ограничить перебор можно преобразованием левой части уравнения к сумме неотрицательных функций:

Решить: .

Решение. Уравнение приводится к виду . Отсюда имеем , а так как  - целое число, то  может быть только равен 0, 1, . Легко видеть, что только  возможен. Тогда  и .

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

Решить: .

Решение. Относительно  это уравнение – квадратное: . Условием существования решения является , т.е. . Таким образом, достаточно перебрать случаи .

Ответ. , .

Другой идеей является сравнение левой и правой частей уравнения по какому-то модулю (или сравнение остатков):

Решить: .

Решение. Так как , то , а .

Ответ. Решений нет.

Решить в целых числах: .

Решение. Если , то левая часть , значит, если решение есть, то  четно, т.е. . Тогда . Но , значит, если решение есть, то и  должно быть четным, т.е. . Итак, в результате имеем , или . Отсюда , , т.е. , . При  получаем второй ответ: .

 Популярными  становятся  такие  задачи  не  только  в  олимпиадных  заданиях, а  также в тестах ЕГЭ задачи С6. Например,

C6 Решите уравнение в целых числах:    

C6 Решите уравнение 2 +  − 6 − 12 = 0 в целых числах.