Алгоритм евклида уравнение в целых числах

Решение уравнений в целых числах

Математика, 9 класс

, ДВГГУ

Решение уравнений в целых числах

Решение уравнений в целых числах является одной из древнейших математических задач.

Алгебраическое уравнение с целыми коэффициентами, имеющее более одного неизвестного, когда стоит задача найти его целые или рациональные решения называется неопределенным или диофантовым, по имени древнегреческого математика Диофанта, который занимался проблемой решения таких уравнений. По некоторым данным Диофант жил до 364 года н. э. Достоверно известно лишь своеобразное жизнеописание Диофанта, которое по преданию было высечено на его надгробии и представляло задачу-головоломку: «Бог ниспослал ему быть мальчиком шестую часть жизни; добавив к сему двенадцатую часть, Он покрыл его щеки пушком; после седьмой части Он зажег ему свет супружества и через пять лет после вступления в брак даровал ему сына. Увы! Несчастный поздний ребенок, достигнув меры половины полной жизни отца, он был унесен безжалостным роком. Через четыре года, утешая постигшее его горе наукой о числах, он [Диофант] завершил свою жизнь».

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

Определение 1. Наибольшим общим делителем (НОД) целых чисел a1, a2,…, an называется такой их положительный общий делитель, который делится на любой другой общий делитель этих чисел.

Теорема 2. Если , то существуют такие целые числа х и у, что имеет место равенство .

Замечание. Это равенство называется линейной комбинацией или линейным представлением НОД через эти числа.

Определение 3. Числа а и b называются взаимно простыми, если НОД этих чисел равен 1.

Теорема 4. (теорема о делении с остатком) Для любого целого а и целого существуют и единственные целые q и r, такие что .

Замечание. Если то q называется неполным частным, а r – остатком от деления a на b. В частности, если , то и делится на .

Из теоремы 4 следует, что при фиксированном целом m > 0 любое целое число а можно представить в одном из следующих видов:

При этом если то будем иметь , если и

, если .

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

Теорема 5. Пусть a и b – два целых числа, 0 и , тогда .

Этот способ называется алгоритмом Евклида. Задача нахождения НОД чисел a и b сводится к более простой задаче нахождения НОД b и r, . Если r = 0, то . Если же , то рассуждения повторяем, отправляясь от b и r. В результате получаем цепочку равенств:

, ,

, ,

, , ……………………(**)

, ,

.

Мы получим убывающую последовательность натуральных чисел

которая не может быть бесконечной. Поэтому существует остаток, равный нулю: пусть . На основании теоремы 10 из (**) следует, что .

1. Решение неопределенных уравнений первой степени от двух переменных в целых числах

Рассмотрим два метода решения диофантовых уравнений первой степени от двух переменных.

Алгоритм этого метода рассмотрим на примере решения конкретного уравнения. Шаги алгоритма, которые необходимо применять при решении любого такого уравнения выделим курсивом.

Пример 1. Решить уравнение в целых числах 5x + 8y = 39.

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

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

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

4. Решаем его уже относительно переменной y, рассуждая точно также как в п.1, 2: . Выделяя целую часть, получим:

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

6. Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z: = . Требуя, чтобы было целым, получим: 1 – u = 2v, откуда u = 1 – 2v. Дробей больше нет, спуск закончен (процесс продолжаем до тез пор, пока в выражении для очередной переменной не останется дробей).

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

z = = = 3v – 1; = 3 – 5v.

= = 3+8v.

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

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

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

Теорема 1.1. Если в уравнении , , то уравнение имеет, по крайней, мере одно решение.

Теорема 2.2. Если в уравнении , и с не делится на , то уравнение целых решений не имеет.

Теорема 3.3. Если в уравнении , и , то оно равносильно уравнению , в котором .

Теорема 4.4. Если в уравнении , , то все целые решения этого уравнения заключены в формулах:

где х0, у0 – целое решение уравнения , — любое целое число.

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

1. Найти наибольший общий делитель чисел a и b,

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

если и , то

2. Разделить почленно уравнение на , получив при этом уравнение , в котором .

3. Найти целое решение (х0, у0) уравнения путем представления 1 как линейной комбинации чисел и ;

4. Составить общую формулу целых решений данного уравнения

где х0, у0 – целое решение уравнения , — любое целое число.

Пример 2. Решить уравнение в целых числах 407х – 2816y = 33.

Воспользуемся составленным алгоритмом.

1. Используя алгоритм Евклида, найдем наибольший общий делитель чисел 407 и 2816:

2816 = 407·6 + 374;

33 = 11·3. Следовательно (407,2816) = 11, причем 33 делится на 11

2. Разделим обе части первоначального уравнения на 11, получим уравнение 37х – 256y = 3, причем (37, 256) = 1

3. С помощью алгоритма Евклида найдем линейное представление числа 1 через числа 37 и 256.

Выразим 1 из последнего равенства, затем, последовательно поднимаясь по цепочке равенств, будем выражать 3; 34 и полученные выражения подставим в выражение для 1.

1 = 34 – 3·11 = 34 – (37 – 34·1) ·11 = 34·12 – 37·11 = (256 – 37·6) ·12 – 37·11 =

– 83·37 – 256·(–12). Таким образом, 37·(– 83) – 256·(–12) = 1, следовательно пара чисел х0 = – 83 и у0 = – 12 есть решение уравнения 37х – 256y = 3.

4. Запишем общие формулы решений первоначального уравнения

где t — любое целое число.

Замечание. Можно доказать, что если пара (х1,y1) — целое решение уравнения , где , то все целые решения этого уравнения находятся по формулам: .

2. Методы решения некоторых нелинейных диофантовых уравнений

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

Метод разложения на множители

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

Пример 3. Решить уравнение в целых числах y3 — x3 = 91.

Решение. 1) Используя формулы сокращенного умножения, разложим правую часть уравнения на множители:

2) Выпишем все делители числа 91: ± 1; ± 7; ± 13; ± 91

3) Проводим исследование. Заметим, что для любых целых x и y число

следовательно, оба сомножителя в левой части уравнения должны быть положительными. Тогда уравнение (1) равносильно совокупности систем уравнений:

; ; ;

4) Решив системы, получим: первая система имеет решения (5; 6), (-6; -5); третья (-3; 4),(-4;3); вторая и четвертая решений в целых числах не имеют.

Ответ: уравнение (1) имеет четыре решения (5; 6); (-6; -5); (-3; 4); (-4;3).

Пример 4. Решить в целых числах уравнение x + y = xy.

Решение. 1) Перенесем все члены уравнения влево и к обеим частям полученного уравнения прибавим (–1): x + y – xy – 1 = – 1

Сгруппируем первое – четвертое и второе – третье слагаемые и вынесем общие множители, в результате получим уравнение: (x — 1)(y — 1) = 1

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

3) Записав соответствующие системы уравнений и решив их, получим решение исходного уравнения. Ответ: (0,0) и (2,2).

Пример 5. Доказать, что уравнение (x — y)3 + (y — z)3 + (z — x)3 = 30 не имеет решений в целых числах.

Решение. 1) Разложим левую часть уравнения на множители и обе части уравнения разделим на 3, в результате получим уравнение:

2) Делителями 10 являются числа ±1, ±2, ±5, ±10. Заметим также, что сумма сомножителей левой части уравнения (2) равна 0. Нетрудно проверить, что сумма любых трех чисел из множества делителей числа 10, дающих в произведении 10, не будет равняться 0. Следовательно, исходное уравнение не имеет решений в целых числах.

Метод испытания остатков

Этот метод основан на исследовании возможных остатков левой и правой частей уравнения от деления на некоторое фиксированное натуральное число.

Рассмотрим примеры, которые раскрывают сущность данного метода.

Пример 6. Решить в целых числах уравнение x2 + 1 = 3y.

Решение. 1) Заметим, что правая часть уравнения делится на 3 при любом целом y.

2) Исследуем какие остатки может иметь при делении на три левая часть этого уравнения.

По теореме о делении с остатком целое число х либо делится на 3, либо при делении на три в остатке дает 1 или 2.

Если х = 3k, то правая часть уравнения на 3 не делится.

Если х = 3k+1, то x2 + 1= (3k+1)2+1=3m+2, следовательно, опять левая часть на 3 не делится.

Если х = 3k+2, то x2 + 1= (3k+2)2+1=3m+2, следовательно, и в этом случае левая часть уравнения на три не делится.

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

Пример 7. Решить в целых числах x³ — 3y³ — 9z³ = 0.

Решение. 1) Очевидно, что решением уравнения будет тройка чисел (0; 0; 0).

2) Выясним, имеет ли уравнение другие решения. Для этого преобразуем уравнение к виду

Так как правая часть полученного уравнения делится на 3, то и левая обязана делится на три, следовательно, так как 3 — число простое, х делится на 3, т. е. х = 3k, подставим это выражение в уравнение (3): 27k3 = 3y³ + 9z³, откуда

следовательно, y³ делится на 3 и y = 3m. Подставим полученное выражение в уравнение (4): 9k3 = 27m³ + 3z³, откуда

В свою очередь, из этого уравнения следует, что z3 делится на 3, и z = 3n. Подставив это выражение в (5), получим, что k3 должно делиться на 3.

Итак, оказалось, что числа, удовлетворяющие первоначальному уравнению, кратны трём, и сколько раз мы не делили бы их на 3, опять должны получаться числа, кратные трём. Единственное целое число, удовлетворяющее этому условию, будет нуль, т. е. решение данного уравнения (0; 0; 0) является единственным.

Контрольное задание №1

Представленные ниже задачи являются контрольным заданием №1 для учащихся 9 классов. Решения необходимо оформить в отдельной тетради и выслать по адресу 8, ХКЦТТ, ХКЗФМШ. Для зачета нужно набрать не менее 15 баллов (каждая правильно решенная задача оценивается в 3 балла).

М.9.1.1. Решив задачу, помещенную вначале статьи, определить сколько лет прожил Диофант.

М.9.1.2. Решить уравнения в целых числах

М.9.1.3. Найдите день моего рождения, если сумма чисел равных произведению даты рождения на 12 и номера месяца рождения на 31 равна 380.

М.9.1.4. Кусок проволоки длиной 102 см нужно разрезать на части длиной 15 см и 12 см, так чтобы была использована вся проволока. Как это сделать?

М.9.1.5. Решить уравнения в целых числах

М.9.1.6. Докажите, что уравнение x2 – y2 = 30 не имеет решений в целых числах.

М.9.1.7. Существуют ли целые числа m и n, удовлетворяющие уравнению m2 + 1994 = n2

1. Башмакова, И. Г. Диофант и диофантовы уравнения. – М.: Наука, 1972.

2. Фоминых, Ю. Ф. Диофантовы уравнения //Математика в шк. – 1996. — №6.

3. Школьная энциклопедия. Математика. / под редакцией – М.: Издательство «Большая российская энциклопедия», 1996.

4. Бабинская, И. Л. Задачи математических олимпиад. – М., 1975.

5. Васильев, Н. Б. Задачи Всесоюзных математических олимпиад. – М., 1998.

6. Курляндчик, Л. Метод бесконечного спуска // Приложение к журналу «Квант». 1999. – №3.

7. Яковлев, Г. Н. Всесоюзные математические олимпиады школьников. М., 1992.

8. Серпинский, В. О решении уравнений в целых числах. – М, 1961.

9. Перельман, Я. И. Занимательная алгебра. – М.: Наука, 1975.

Элективный курс Сказки Шехерезады и уравнения Диофанта Балашов 2009 Содержание

Главная > Элективный курс

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Применение алгоритма Евклида для нахождения наибольшего общего делителя двух чисел (повторение).

Существует довольно простой прием, позволяющий находить наибольший делитель двух натуральных чисел. Этот прием называется алгоритмом Евклида. Вы с ним познакомились еще при изучении курса математики в 5 – 6 классах. Евклид, великий ученый, живший около 2000 лет назад, занимался не только геометрией, которая носит его имя. Ему принадлежит решение ряда важных задач арифметики и, в частности, тот способ нахождения наибольшего общего делителя, который мы сегодня будем использовать при изучении нового материала. А сейчас повторим суть алгоритма Евклида .

Чтобы найти наибольший общий делитель двух чисел:

1) надо большее из двух чисел разделить на меньшее;

2) потом меньшее из чисел на остаток при первом делении;

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

Рассмотрим пример. Найти НОД (645; 381).

Разделим с остатком 645 на 381. Мы получим: 645=381·1+264.

Далее разделим с остатком 381 на 264, получим: 381=264·1+117.

Теперь разделим с остатком 264 на 117, получим: 264=117·2+30.

Продолжим процесс деления, разделим с остатком 117 на 30, получим: 117=30·3+27. Далее, 30=27·1+3. Следующий шаг – делим 27 на 3, получаем, что 27=3·9 +0, т. е. 27 делится на 3 без остатка. Значит, наибольший общий делитель чисел 27 и 3 равен 3, следовательно, и наибольший общий делитель чисел 645 и 381 равен 3, т. е. последнему отличному от нуля остатку.

Таким образом, НОД (645; 381) = 3.

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

2. Вывод формул для решения диофантовых уравнений с использованием алгоритма Евклида.

Прежде чем рассмотреть решение линейного уравнения с двумя неизвестными:

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

Чтобы доказать утверждение о наибольшем общем делителе, представим описанный процесс в виде следующей цепочки равенств: если a > b , то

·b = r 1 q 1 + r 2

r 1 = r 2 q 2 + r 3 (2)

r n – 1 = r n q n

Здесь r 1 , . . . , r n — положительные остатки, убывающие с возрастанием номера. Отсутствие остатка в последнем равенстве следует из того, что натуральные числа r n не могут убывать бесконечно, поэтому на некотором шаге остаток станет нулевым.

Обратимся к системе (2). Из первого равенства, выразив остаток r 1 через a и b , получим r 1 = a – b · q 0 . Подставляя его во второе равенство, найдём r 2 = b (1 + q 0 q 1 ) – a · q 1 . Продолжая этот процесс дальше, мы сможем выразить все остатки через a и b , в том числе и последний: r n = Aa + Bb . В результате нами доказано

что найдутся такие целые числа A и B , что d = Aa + Bb . Заметим, что коэффициенты A и B имеют разные знаки; если НОД ( a , b ) = 1 , то Aa + Bb = 1 . Как найти числа A и B , видно из алгоритма Евклида.

Перейдем теперь к решению линейного уравнения с двумя неизвестными:

Возможны два случая: либо число c делится на d = НОД( a , b ) , либо нет.

В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a 1 x + b 1 y = c 1 , коэффициенты которого

a 1 = a / d и b 1 = b / d взаимно просты.

Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делиться на d и поэтому не может равняться числу c , которое на d не делится.

Итак, мы можем ограничиться случаем, когда в уравнении (1) коэффициенты a и b взаимно просты. На основании предыдущего предложения найдутся такие целые числа х 0 и у 0 , что ax 0 + by 0 = 1 , откуда пара (сх 0 , су 0 ) удовлетворяет уравнению (1). Вместе с ней уравнению (1) удовлетворяет бесконечное множество пар ( x , у) целых чисел, которые можно найти по формулам

x = cx 0 + bt, y = cy 0 – at. (3)

Здесь t – любое целое число. Нетрудно показать, что других целочисленных решений уравнение ах + by = c не имеет. Решение, записанное в виде (3), называется общим решением уравнения (1). Подставив вместо t конкретное целое число, получим его частное решение.

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

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

Также на занятиях, где материал изучается крупным блоком, целесообразно создание таблицы в виде конспекта изложенного учителем нового материала. Этот конспект должен стать информационно-справочной таблицей и сыграть свою
роль на занятиях тематического или итогового повторения. Сформулируем некоторые требования к его оформлению. Материал в конспекте должен быть разделен на несколько самостоятельных, логически связанных между собой блоков. В него желательно внести вспомогательные вопросы, с помощью которых готовится введение нового, узловые вопросы темы и ее практическое применение.

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

Как разработать такой конспект? Учитель сначала разрабатывает конспект полностью на листе бумаге стандартного размера. На другом таком же листе он выписывает конспект-заготовку в строгом расположении текста на основном конспекте. Этот фрагментарный конспект необходимо размножить, чтобы к лекции такой конспект-заготовку имел каждый ученик. Точно такой конспект «с пропусками» учитель должен заранее написать на доске
перед началом лекции или подготовить его компьютерный вариант для использования в классе с интерактивной доской. Для проведения данной лекции был подготовлен такой
конспект-заготовка (Приложение 4).

3. Примеры решения диофантовых уравнений с использованием алгоритма Евклида.

Рассмотрим решение заданий №6 (а), №7 из Приложения 1.

Задание №6 . Решить уравнение на множестве целых чисел

НОД(7;11)=1, Найдем значение х 0 и у 0 для получения решений уравнения по формулам (3). Применим алгоритм Евклида к числам 11 и 7:

Таким образом, получаем: , следовательно х 0 = –3, у 0 =2

Запишем общее решение уравнения на множестве целых чисел согласно формулам (3):

Придавая конкретные целые значения t , можно получить частные решения уравнения. Например, при t =1, имеем x = –196, у=131.

Задача №7 . Для газификации жилого дома требуется проложить газопровод протяженностью 150 м. Имеются трубы 13 м и 9м длиной. Сколько требуется труб, чтобы не приходилось их разрезать при прокладке газопровода.

Пусть требуется x труб по 9 м, и у труб по 13м. Составим и решим уравнение: 9х+13у=150.

НОД(9;13)=1, уравнение разрешимо во множестве целых чисел.

Найдем значение х 0 и у 0 для получения решений уравнения по формулам (3). Применим алгоритм Евклида к числам 13 и 9:

Запишем общее решение уравнения согласно формулам (3).

Так как x и y неотрицательные целые числа, то чтобы найти значение t , решим систему неравенств:

Ответ. Для прокладывания газопровода потребуется 8 труб длиной по 9м и 6 труб длиной по 13м.

4 . В домашнее задание для учащихся необходимо включить подготовку по теоретическому материалу и практические задания.

Учащиеся должны ответить на следующие вопросы.

В чем суть алгоритма Евклида?

Когда уравнение (1) разрешимо во множестве целых чисел?

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

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

В качестве практических заданий можно предложить для решения задания №6 (б), №8 из Приложения 1. Также можно предложить составить сюжетную задачу, решение которой сводится к уравнению из №6 (б) на множестве целых неотрицательных или натуральных чисел. Найти ее решения.

Решение диофантовых уравнений с использованием алгоритма Евклида

Актуализация знаний ( проверка знания теории и выполнения практических заданий).

Решение задач с использованием алгоритма Евклида.

Постановка домашнего задания.

Оборудование: заполненные конспекты – заготовки предыдущей лекции, карточки с заданиями для фронтальной и групповой работы.

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

Решение задач с использованием алгоритма Евклида .

Задания для решения выбираются по принципу: от простого к сложному. Для овладения методом решения диофантовых уравнений с использованием алгоритма Евклида можно предложить вначале решить уравнения, не связанные, с какой либо реальной ситуацией. Например, № 6 (в, г). Затем можно предложить решение текстовых задач на составление линейных диофантовых уравнений. Например, № 9, 10. Все задания указаны из Приложения 1. Задания можно выполнить в группах, а затем проверить полученные ответы. Ниже приведем решение задачи №9.

Неотъемлемой частью занятия – практикума является решение и нестандартных задач, заданий повышенной трудности. В процессе их выполнения можно использовать прием разбиения на подзадачи. К таким заданиям можно отнести и задачу № 11, которую мы далее рассмотрим.

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

Задача №9. Транспортные организации имеют в наличие машины вместимостью 3, 5 т и 4, 5 т. Следует перевезти груз весом 53 т. Сколько машин нужно взять для одного рейса?

Пусть x машин по 3,5 т.; у машин по 4, 5 т. Составим и решим уравнение: 3,5х+4,5у=53. Перейдем к уравнению с целыми коэффициентами, например, умножим обе части уравнения на 2. Получим: 7х+9у=106.

НОД(7, 9)=1, уравнение имеет целые решения.

Так как t – принимает целые значения, то системе неравенств удовлетворяют значения t =-47 и t =-46. Получим решение диофантова уравнения в натуральных числах:

Таким образом, для одного рейса можно взять:

А) 1 машину вместимостью 3,5 т и 11 машин вместимостью 4,5 т;

В) 10 машин вместимостью 3,5 т и 4 машины вместимостью 4,5 т.

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

Задача №11 . Школа получила 1 млн. руб. на приобретение 100 единиц учебного оборудования (на всю сумму без сдачи). Администрации школы предложили, оборудование стоимостью 3000, 8000 и 12000 руб. за единицу. Сколькими способами школа может закупить это оборудование. Укажите один из способов.

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

1 ) составление системы уравнений .

Пусть приобретено x единиц оборудования по 12000 руб., y единиц оборудования по 8000 руб., z единиц оборудования по
3000 руб.

Всего приобретено 100 единиц оборудования, т.е. x + y + z = 100 , причем на приобретение 100 единиц оборудования затрачено 1 млн. руб., т.е.

12000 x + 8000 y + 3000 z = 1 000 000,

12x + 8y + 3z = 1000 .

Таким образом, получаем систему двух уравнений с тремя неизвестными:

Вопрос учителя: всегда ли задача будет иметь решение? Иначе: какими
должны быть x , y , z ?

( ответ: x >0, y >0, z >0 )

2) обсуждение решения системы.

Во-первых, исключим z , путем вычитания из второго уравнения первого, умноженного на 3. Следовательно, получаем диофантово уравнение 1-ой степени с двумя неизвестными 9 x + 5 y = 700.

Во-вторых, его можно решить способом с использованием алгоритма Евклида.

3) оформление решения задачи.

Так как уже получили уравнение, которое решается известным способом, то оформление решения можно предложить выполнить учащимся дома. В результате решения получается, что приобрести оборудование библиотека может шестью способами. Укажем одно из частных решений задачи: x=65 , y=23, z=12 , т.е. школа на 1 млн. руб. может
приобрести 65 единиц оборудования по 12 тыс. руб., 23 единицы оборудования по 8 тыс. руб., 12 единиц оборудования по 3 тыс. руб.

3. Постановка домашнего задания.

В качестве домашнего задания можно преложить учащимся решить задачи № 2; №3; №5 из Приложения 1 с использованием алгоритма Евклида.

Решение диофантовых уравнений с использованием

План занятия совпадает с планом школьной лекции на указанную тему.

Понятие цепной дроби. Представление рациональных чисел в виде цепной дроби

Формулы для решения диофантовых уравнений с использованием цепной дроби

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

Оборудование: конспект – заготовка лекции на доске и индивидуальные заготовки для каждого ученика.

Занятие № 5 по своей структуре аналогично занятию №3. В качестве примеров решения диофантовых уравнений с использованием цепной дроби, можно рассмотреть задания из Приложения 1. Заметим, что можно взять уже ранее решенные задачи и выполнить их решение новым способом.

Понятие цепной дроби. Представление рациональных чисел в виде цепной дроби

Обратимся вновь к алгоритму Евклида. Из первого равенства системы (2) вытекает, что дробь a / b можно записать в виде суммы целой части и правильной дроби: . Из второго равенства той же системы имеем. Значит,

Продолжим этот процесс до тех пор, пока не придём к знаменателю q п

В результате мы представим обыкновенную дробь a / b в следующем виде: . Эйлер назвал дробь, стоящую в правой части равенства непрерывной . Приблизительно в тоже время в Германии появился другой термин – цепная дробь . Так за этими дробями и сохранились оба названия. Ввиду громоздкости развёрнутой записи цепной дроби применяют компактную запись

a / b = [ q 0 ; q 1 , q 2 , …, q п ] .

Представить рациональное число в виде цепной дроби.

.

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

Если при построении цепной дроби остановиться на знаменателе q k , то получиться дробь [ q 0 ; q 1 , q 2 , …, q к ] , которую называют к-й подходящей дробью для искомой и обозначают Найдем вид некоторых подходящих дробей:

Для рационального числа a / b последовательность подходящих дробей конечна, и ее последний элемент Нетрудно заметить, что имеют место следующие рекуррентные соотношения:

(4)

Формулы для решения диофантовых уравнений с использованием цепной дроби

Вернемся к уравнению: ax + by = c (1). Напомним, что в нем a и b взаимно просты. Решение этого уравнения «способом цепной дроби» завершается применением готовых формул (доказательство которых можно найти в специальных пособиях), представляющих общее решение данного уравнения

(5)

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

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

Алгоритм Евклида для нахождения НОД

Свой алгоритм Евклид (древнегреческий математик, живший примерно в 300 г. до н.э.) придумал для решения задачи о соизмеримости двух отрезков. Общей мерой (единицей измерения) отрезков с длинами $L_1$ и $L_2$ является отрезок с наибольшей возможной длиной $L$, который можно уложить без остатка как в первом отрезке, так и во втором. Например, для отрезков 10 и 15 такой общей мерой будет отрезок с длиной 5 (им можно пользоваться как единицей измерения для обоих отрезков). При этом 5 будет наибольшим общим делителем 10 и 15.

В общем случае, алгоритм Евклида — это метод нахождения наибольшего общего делителя (НОД) нескольких чисел.

Целое число $a$ делится на целое число $b$ ($b \ne 0$), если существует целое число $k$, такое что $a=kb$. В таком случае $b$ называют делителем числа $a$; число $a$ называют кратным числа $b$.

Если $a$ и $b$ делятся на $c$, то их сумма $a+b$ и их разность $a-b$ делятся на $c$.

Если $a$ делится на $c$, а $b$ делится на $d$, то их произведение $a*b$ делится на $c*d$.

$a$ и $b$ – положительные целые числа, $c$ — является общим делителем чисел $a$ и $b$, если $a$ делится на $c$ и $b$ делится на $c$.

Среди общих делителей чисел $a$ и $b$ (не равных одновременно нулю) есть наибольший общий делитель (по-английски Greatest common divisor — GCD), обозначаемый НОД($a,b$) или $GCD(a,b)$.

Если $a$ делится на $b$, то $GCD(a,b) = b$. Например: $GCD(50,10)=10$.

$GCD(a,a)=a$. Например: $GCD(32,32)=32$.

Если $a \gt b$, то $GCD(a,b)=GCD(a-b,b)$.

Если $GCD(a,b)=1$, то числа $a$ и $b$ — взаимно простые.

Алгоритм Евклида с вычитаниями

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

Пример: Найти НОД двух чисел 264 и 192.

Решение: НОД(264, 192) = НОД(72, 192) = НОД(72, 120) = НОД(72, 48) = НОД(24, 48) = НОД(24, 24) = 24

Задача. Найти НОД двух натуральных чисел $a$ и $b$.

Используем для решения задачи алгоритм Евклида с вычитаниями.

Реализация на Pascal:

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

Если применить алгоритм Евклида с вычитаниями к паре чисел $(1,10^<20>)$, то будет выполнено около $10^<20>$ вычитаний, это слишком долго!

Можно за один раз вычитать из $a$ $b$ столько раз, сколько можно. Алгоритм Евклида с делением основан на том, что если $a=bq+r$, где $r$ — остаток от деления $a$ на $b$ ($0 \le r

Рассмотрим алгоритм и процедуру-функцию к решению задачи 1.1, используя для нахождения НОД двух чисел алгоритм Евклида с делением.

Реализация на Pascal :

Вычислить НОД трех натуральных чисел $a$, $b$ и $c$ можно так:

В общем случае, справедлива следующая рекуррентная формула:

$GCD(a_1,a_2. a_n) = GCD(GCD(a_1,a_2. a_), a_n)$.

Ниже приведена функция нахождения НОД для массива натуральных чисел $a(1..n)$ с использованием цикла.

Диофантовы уравнения, расширенный алгоритм Евклида

С помощью алгоритма Евклида можно доказать одно важное свойство НОД.

Если $GCD(a,b)=d$, то можно найти такие целые числа $x$ и $y$, что $ax+by=d$.

Важным частным случаем этого утверждения является:

Если числа $a$ и $b$ взаимно просты ($GCD(a,b) = 1$), то найдутся такие целые числа $x$ и $y$, что $ax + by = 1$.

Решение в целых числах уравнения $ax + by = c$ для любого целого $c$ получается из решения предыдущего уравнения умножением на $c$.

Уравнение вида $ax+by=c$, разрешимое в целых числах, называется диофантовым уравнением (по имени древнегреческого математика Диофанта).

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

• задачи по размену суммы денег купюрами определенного достоинства;
• задачи на переливание.

Критерий разрешимости диофантова уравнения:

Чтобы уравнение $ax+by=c$ имело решение в целых числах $(x,y)$, необходимо и достаточно, чтобы $c$ делилось на $d=GCD(a,b)$.

Если это условие выполнено и $(x_0,y_0)$ – одно из решений этого уравнения, то все целочисленные решения выглядят так:

$y = y_0 — $, где $t$ — целое число;

Способ решения уравнения $ax + by = d$ основан на алгоритме Евклида: определяя $GCD(a,b)$ методом последовательного деления, на каждом шаге выражаем остаток от деления через исходные числа $a$, $b$ до тех пор, пока остаток не станет нулем. Следовательно, на предыдущем шаге остаток равен $GCD(a,b)$, и мы одновременно получаем одно из решений уравнения.

$r_$ делится на $r_n$ без остатка

Следовательно, $r_n=GCD(a,b)$, а $(x_n,y_n)$ – искомое решение уравнения $ax + by = d$;

Рекуррентные формулы определения решения, как видно из выкладок, имеют следующий вид: (для запоминания: начальная “1” — для первого параметра в функции НОД)

Замечание. Достаточно рассмотреть одно рекуррентное соотношение, например, для вычисления $x$, так как можно использовать исходное уравнение для определения $y=(d–ax)/b$.

Пример 1.3: Найти целочисленное решение уравнения $258x + 114y = 6$

258 = 114 · 2 + 30; $q_1 = 2$;

114 = 30 · 3 + 24; $q_2 = 3$;

30 = 24 · 1 + 6; $q_3 = 1$;

24 = 6 · 4; НОД(258,114) = 6

x₃ = 4; y₃ = -9 (таблица вычислений на рис.1.1);

Алгоритм для решения в целых числах уравнения $ax+by=c$.

1. Найдем по алгоритму Евклида с делениями $d=GCD(a,b)$. Одновременно определяем решение уравнения $ax_0+by_0=d$ по вышеизложенным рекуррентным формулам.

2. Проверим, делится ли число $c$ на $GCD(a,b)$. Если нет, то решений в целых числах не существует.

3. Если делится, то делим на $d$ коэффициенты в правой и левой части уравнения $ax+by=c$. Получим эквивалентное уравнение $+=$,
где $a_1=a/d$, $b_1=b/d$, $c_1=c/d$.

4. Найденная пара чисел $(x_0,y_0)$ – частное решение уравнения $x+y=1$, общее решение этого уравнения находится по формулам: $x = x_0+t$ и $у = y_0-t$, где $x_h=t$, $y_h=-t$ ($t$ – любое целое число) являются общим решением однородного уравнения $x+y=0$.

5. Частное решение исходного уравнения $ax+by=c$ получается умножением пары $(x_0,y_0)$ на $c_1$. Общее решение уравнения $ax+by=c$ получается сложением частного решения и общего решения однородного уравнения $ax+by=0$ (или эквивалентного $x+y=0$).

Достоинство данного алгоритма в том, что решение уравнения определяется одновременно с нахождением $GCD(a,b)$ без дополнительных массивов. Алгоритм справедлив также при $a \lt b$.

Целочисленное решение уравнения $ax_0+by_0=GCD(a,b)$

Решение общего линейного диофантова уравнения.

Диофантово уравнение общего вида: $ + + . + = c$, где $a_1, a_2, …, a_n, c$ — целые числа, а $GCD(a_1. a_n)$ — наибольший общий делитель чисел $a_i$, где $1 \le i \le n$ и не все числа $a_i$ равны нулю.

С помощью алгоритма Евклида можно доказать, что диофантово уравнение $++. + = GCD(a_1,a_2. a_n)$ всегда разрешимо, следовательно, критерий разрешимости: для существования решения в целых числах этого уравнения необходимо и достаточно, чтобы число $с$ делилось на $GCD(a_1,a_2. a_n)$.

Рассмотрим алгоритм решения на частном примере.

Пример: найти решение уравнения $18x+42y+10z=14$ в целых числах.

Решение:

Для принятых выше обозначений $a_1=18$, $a_2=42$, $a_3=10$, $c=14$.

Легко угадывается решение: $(x = 0; y = 2; z = -7)$.

Если любому целому числу, представимому левой частью уравнения, сопоставить конкретный набор $(x,y,z)$, то действия с такими числами (сложение, вычитание, умножение на любое целое число) эквивалентны аналогичным действиям с соответствующими наборами (поэлементно). В частности, для коэффициентов уравнения числу 18 можно сопоставить набор $(1,0,0)$, т.к. 18 · 1 + 42 · 0 +10 · 0 = 18, для числа 42 — набор (0,1,0), а для числа 10 — набор (0,0,1).

Найдем число $d=GCD(18,42,10)$ и целочисленное решение уравнения $18x+42y+10z=d$

$GCD(a_1,a_2,a_3)=GCD(GCD(a_1,a_2),a_3))$ для последовательного определения НОД чисел;

$GCD(a,b)=GCD(b,r)$, где $r$ — остаток целочисленного деления $a$ на $b$, причем $0 ≤ r (-2 ,1,0)18(1,0,0)↑↑6 = 42 – 18 · 2

6(-2,1,0)0(7,-3,0)↑↑0 = 18 – 6 · 34(2,-1,1)↑↑6(-2,1,0)4 = 10 – 6 · 12(-4,2,-1)↑↑4(2,-1,1)2 = 6 – 4 · 12(-4,2,- 1)↑↑0(10,- 5,3)0 = 4 – 2 · 22(-4,2,-1)0(7,- 3,0)0(10,-5,3)итоговая строка результатов

Последняя строка таблицы определяет результаты решения диофантова уравнения.

Ненулевое значение в первом столбце определяет $GCD(18,42,10)=2$. Соответствующий набор $(x = -4, y = 2, z = -1)$ определяет частное решение уравнения $18x + 42y + 10z=GCD(18, 42,10)$. Правая часть исходного уравнения делится на GCD коэффициентов, следовательно, частное решение исходного уравнения существует и определяется умножением на целочисленный коэффициент $c/d=7$, т.е. набор $(x=-28, y=14, z=-7)$ является частным решение исходного уравнения. Наборы при нулевых результирующих коэффициентах определяют независимые решения однородного уравнения $18x+42y+10z=0$. Независимость наборов означает, что нельзя получить соответствующие компоненты одного набора из другого умножением на какое-либо целое число (это следует из сравнения третьих компонент в наборах). Очевидно, что решение однородного уравнения можно умножать на любую целочисленную константу, получая вновь решение. Следовательно, общее решение уравнения можно записать следующим образом.

$\begin x = -28 + 7 t_1 + 10 t_2 \\ y = 14 — 3 t_1 — 5 t_2 \\ z = -7 + 0 t_1 + 3 t_2 \end$
где $t_1$, $t_2$ — любые целые числа

Легко проверить, что для любых целых $t_1$ и $t_2$ тройки $(x,y,z)$ являются решениями уравнения $18x+42y+10z=14$.

Например, для $t_1=4$ и $t_2=0$ имеем $(x=0; y=2; z=-7)$, $18 \cdot 0 + 42 \cdot 2 — 10 \cdot 7=14$.

Алгоритм решения диофантова уравнения

Ниже приводится алгоритм решения уравнения $++. +=GCD(a_1,a_2. a_n)$

Функция GCD(n, a(), x())

Задать набор N а_1

Цикл i от 2 до n

Задать набор N а$_i $

Пока a(i ) ≠ 0

t = a(i); Nt =_ Na$_i $_

a(i) = a(1) — q*a(i); Na$_i $_ = Na_1 — q*Na$_i $

a (1) = t Na _1 = Nt

Конец пока

Конец цикла i

конец функции

Реализация на Pascal:

Задача: Разменять 14 рублей “трешками” и “пятерками”.

Задачи переливания

Задача. В ведре 12 литров молока. Как разлить молоко на две равные части, используя только бидоны 5 и 7 литров?

Покажем, как эта задача сводится к решению в целых числах уравнения $7x+5y=6$.

Следующий алгоритм переливания (рисунок 4) всегда приводит к решению подобных задач:

1) В первый сосуд, если он пуст, наливаем (+1 для x)

2) Из первого сосуда доливаем второй (если возможно)

3) Из второго сосуда, если он полон, выливаем (-1для y)

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

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

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

Подсчитывая количество «наливаний» ($x$ со знаком «+») для одного сосуда и «выливаний» ($y$ со знаком «-«) для другого, находим решение соответствующего диофантова уравнения.

7 * 3 + 5 *(-3) = 6; $x$ = 3, $y$ = -3

Решений у такого уравнения бесконечно много. Если выберем сосуд 5 л в качестве первого – получим решение:

Количество шагов переливаний может зависеть от того, какой вместительности сосуд считать за “первым” (например, если в задаче заменить 5-литровый сосуд 3-литровым).

Для закрепления алгоритма при решении тренировочных задач 1.3 и 1.4 воспользуйтесь программой «Переливай-ка».

Задача 1.3: Разлить поровну 16 ведер кваса, находящегося в 16-ведерном бочонке, имея два пустых бочонка по 11 и 6 ведер.

Задача 1.4: Имеются три бочонка вместимостью 6, 3 и 7 ведер. В первом и третьем содержится 4 и 6 ведер кваса соответственно. Требуется разделить квас поровну между первым и третьим бочонком (по 5 вёдер).

Простые числа

Натуральное число называется простым, если оно не имеет делителей кроме единицы и самого себя.

Основная теорема арифметики. Любое целое положительное число разлагается на простые множители и притом единственным образом (докажите самостоятельно).

Задача 1.5. Определить простые делители натурального числа $n$.

Решето Эратосфена для нахождения простых чисел

Задача. Найти и вывести на экран простые числа, не превосходящие заданного числа N.

Древнегреческий математик Эратосфен (250 – 194 годы до н.э.) записывал все подряд числа на папирусе, а затем выкалывал составные числа по следующему правилу: сначала числа, делящиеся на 2, затем на 3, на 5 и т.д., то есть просеивал их как сквозь решето. В результате чего на папирусе оставались лишь простые числа. Этот алгоритм нахождения простых чисел носит название решета Эратосфена.

Ввести $N$
Массив $$, $i=1. N$ (элементы массива нулевые)
Цикл $i = 2 .. n$
Если $a_i = 0$ то
Шаг=i

Для j = j + h до n с шагом h

Для от i = 2 до n

Если a(i) = 0 то вывести i;

Основная идея этой реализации алгоритма заключается в том, что индексы элементов массива представляют собой числа, а элементы массива – признаки того, являются ли эти числа простыми (значение 0) или составными (значение 1).

Цепные дроби

Цепная дробь (или непрерывная дробь) — это математическое выражение вида:

где a0 где a0 есть целое число и все остальные an натуральные числа (то есть неотрицательные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.