Как решать диофантовы уравнения алгоритмом евклида

А следовательно общее решение системы двух диофантовых уравнений

Проверим, правильно ли посчитали

Для первого уравнения

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

Но радоваться рано, несмотря на то, что мы получили общее решение, мы получаем не все возможные значения.

Почему? Да потому что вектор имеет НОД =19

и фактически наше общее решение имеет вид

Так как числа в скобках должны быть целыми, то обозначим их t и наше, уже точно окончательное общее решение системы двух диофантовых уравнений имеет вид

Еще несколько примеров, и небольшие ремарки к алгоритму.

Теперь что калькулятор не может.

Очень сильно не любит уравнения с нулевыми коэффициентами. Особенно первое. Например, вот такую систему

калькулятор не решит.

Прибавим к первому уравнению, второе. Таким образом в первом уравнении исчезают все нулевые коэффициенты и калькулятор сможет решить эту систему. Ну как не решит? Решит, если прибегнем к уловке, и постараемся убрать все нулевые коэффициенты

Проверка показывает что общее решение корректно.

��️ Видео

Классический способ решения Диофантовых уравнений ➜ Решите уравнение в целых числах ➜ 13x-7y=6 Скачать

Решение диофантовых уравнений Скачать

Линейные диофантовы уравнения Скачать

Расширенный алгоритм евклида Скачать

РЕШАЕМ ДИОФАНТОВОЕ УРАВНЕНИЕ | ПРОСТЫМИ СЛОВАМИ Скачать

30 Алгоритм Евклида Скачать

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

Математика. Натуральные числа: Алгоритм Евклида. Центр онлайн-обучения «Фоксфорд» Скачать

Полезные мелочи | алгоритм Евклида | диофантовы уравнения и коэффициенты Безу Скачать

Диофантовы уравнения с двумя неизвестными Скачать

Как решать Диофантовы уравнения ➜ Решите уравнение в целых числах 4x+5y=6 Скачать

Полезные мелочи | алгоритм Евклида | диофантовы уравнения | примеры | 2 Скачать

Арифметика и числовые алгоритмы. Делители числа. Простые числа. НОД НОК Алгоритм Евклида (gcd lcm) Скачать

алгоритм евклида — почему он работает? Скачать

18. Метод цепных дробей. Алексей Савватеев. 100 уроков математики 6+ Скачать

Как решать диофантовы уравнения алгоритмом евклида

Алгоритм Евклида. Линейные диофантовы уравнения с двумя неизвестными

1. Целые числа. Делимость с
остатком
Элементарная теория чисел имеет дело с натуральными числами 1, 2,
3, . (множество натуральных чисел обозначается символом N ) и целыми
числами . , -3, -2, -1, 0, 1, 2, 3, . (множество целых чисел обозначается
символом Z ).
Определение. Пусть a, b Z . Число a делится на число b , если
найдется такое число q Z , что a qb . Синонимы: a кратно b , b — делитель
a . Запись: a b или b | a .
Пусть a1 a2 . an c1 c2 . ck — равенство сумм целых чисел. Если
все слагаемые в этом равенстве, кроме одного, кратны b , то и оставшееся
слагаемое обязано быть кратным b .

3.

Теорема. Для данного целого отличного от нуля числа b , всякое целое число
a единственным образом представимо в виде a bq r , где 0 r b .
Доказательство. Ясно, что одно представление числа a равенством
a bq r мы получим, если возьмем bq равным наибольшему кратному
числа b , не превосходящему a (см. Рис. 1).
Тогда, очевидно, 0 r b . Докажем единственность такого представления.
Пусть
a bq r
и
a bq1 r1
— два таких представления. Значит,
0 a a b q q1 r r1 . Здесь 0 делится на b ; b q q1 делится на b ,
следовательно, r r1 обязано делиться на b . Так как 0 r b и 0 r1 b ,
то r r1 b и r r1 делится на b , значит, r r1 равно нулю, а, значит, и q q1
равно нулю, т.е. два таких представления совпадают.

4.

2. Наибольший общий делитель
Определение. Число
d Z , делящее одновременно числа
a, b, c. k Z , называется общим делителем этих чисел. Наибольшее d с
таким свойством называется наибольшим общим делителем. Обозначение:
d a, b, c. k .

5.

Теорема (Свойство 1). Если a, b d , то найдутся такие целые числа
u и v , что d au bv .
Доказательство.
Рассмотрим
множество
au bv | u, v Z .
Очевидно, что Z , а (можно проверить, что — идеал в Z ). Очевидно, что
a, b,0 . Пусть x, y и y 0 . Тогда остаток от деления x на y
принадлежит . Действительно:
x yq r ,0 r y,
r x yq au1 bv1 au2 bv2 q a u1 u2q b v1 v2q .
на
Пусть d — наименьшее положительное число из . Тогда a делится
d . В самом деле, a dq r1 ,0 r1 d , a , d , значит, r1 ,
следовательно, r1 0 . Аналогичными рассуждениями получается, что b
делится на d , значит, d — общий делитель a на b .
Далее, раз d , то d au0 bv0 . Если теперь d1 — общий делитель a и
b , то d1 | au0 bv0 , т.е. d1 | d . Значит, d d1 и d — наибольший общий
делитель.

6.

Теорема (свойство 2). Для любых целых чисел a и k , справедливо:
a, ka a ; 1, a 1 .
Теорема (свойство 3). Если a bq c , то совокупность общих
делителей a и b совпадает с совокупностью общих делителей b и c , в
частности, a, b b, c .
Доказательство. Пусть d | a , d | b , тогда d | c . Пусть d | c , d | b , тогда
d | a .
Если d целое число раз укладывается в a на b , то, очевидно, что d
обязано целое число раз уложиться и в c .

7.

Теорема (свойство 4). Пусть a, b и m — произвольные целые числа.
Тогда am, bm m a, b .
Доказательство. Если d — наибольший общий делитель чисел a и b ,
dm | am и dm | bm , т.е. dm — делитель am и bm . Покажем, что dm наибольший общий делитель этих чисел. Поскольку d — наибольший общий
делитель чисел a и b , то согласно свойству 1, для некоторых целых чисел u
и v выполнено равенство d au bv . Умножив это равенство на m , получим
равенство: dm amu bmv .
Видно, что если некоторое число s делит одновременно am и bm , то s
обязано делить и dm , т.е. s dm , следовательно, dm — наибольший общий
делитель.

8.

a b a, b
Теорема (свойство 5). Пусть s — делитель a и b . Тогда: ,
.
s
s s
Теорема (свойство 6). Если a, b 1, то ac, b c, b .
Доказательство. Пусть c, b d . Имеем: d | b , d | c , следовательно,
d | ac , т.е. d — делитель ac и b . Пусть теперь ac, b s . Имеем: s | b , s | ac ,
s — делитель b , т.е. либо s 1 , либо s не делит a . Это означает, что s | c ,
значит s | d . Итак, d и s делятся друг на друга, т.е. d s .

9.

3. Взаимно простые числа
Определение. Целые числа a и b называются взаимно простыми, если
a, b 1 .
Вспоминая свойство 1 из предыдущего пункта, можно заметить, что
два числа a и b являются взаимно простыми тогда и только тогда, когда
найдутся целые числа u и v такие, что au bv 1.

10.

4. Алгоритм Евклида
Алгоритмом Евклида мы называем совокупность последовательных
действий, позволяющих найти наибольший общий делитель двух
натуральных чисел.
Теорема 7. Если a bq c , то (a, b) (b, c) .
Для отыскания (a, b) при a b применяется алгоритм Евклида,
основанный на теореме 7.
Алгоритм Евклида состоит в получении равенств вида:
Тогда (a, b) rn — последнему не равному нулю остатку алгоритма
Евклида.

11.

Пример 1. Найти с помощью алгоритма Евклида (2004, 1941).
Решение. 2004 = 1941 · 1 + 63
1941 = 63 · 30 + 51
53 = 51 · 1 + 12
51 = 12 · 4 + 3
12 = 3 · 4
Итак, (2004, 1941) = 3.

12.

Пример 2. Найти с помощью алгоритма Евклида (525, 231).
Решение. Ниже приводится запись деления уголком, и каждый раз то,
что было в уголке, т.е. делитель, приписывается к остатку от деления с левой
стороны, а остаток, как новый делитель, берется в уголок:
Запись того же самого в виде цепочки равенств:
525 = 231 · 2 + 63
231 = 63 · 3 + 42
63 = 42 · 1 + 21
42 = 21 · 2
Таким образом, (525, 231) = 21. Линейное представление наибольшего
общего делителя:
21 = 63 – 42 · 1 = 63 – (231 – 63 · 3) · 1 =
= 525 – 231 · 2 – (231 – (525 – 231 · 2) · 3) =
= 525 · 4 – 231 · 9,
следовательно, u 4 и v 9 .

13.

4. Линейные диофантовы
уравнения с двумя неизвестными
Диофантовыми называются уравнения вида
ax by c ,
где a, b, c – целые числа. При этом решения ищутся в целых числах.
Пусть требуется решить линейное диофантово уравнение:
ax by c ,
где a, b, c Z ; a и b — не нули.
Пусть a, b d . Тогда a a1d ; b b1d и уравнение выглядит так:
a1d x b1d y c , т.е. d a1 x b1 y c .
Ясно, у такого уравнения решение существует только тогда, когда d | c .
Пусть d делит c . Поделим обе части уравнения на d и всюду далее будем
считать a, b 1.

14.

Случай 1. Пусть c 0 , уравнение имеет вид ax by 0 — «однородное
b
y.
a
Так как x должен быть целым числом, то y at , где t — произвольное
целое число (параметр). Значит x bt и решениями однородного
диофантова уравнения ax by 0 являются все пары вида bt , at , где
диофантово уравнение». Далее, получаем x
t 0; 1; 2;. Множество всех таких пар называется общим решением
однородного диофантова уравнения, любая же конкретная пара из этого
множества называется частным решением.

15.

Случай 2. Пусть c 0 . Этот случай закрывается следующей теоремой.
Теорема. Пусть
a, b 1, x0 , y0
— частное решение диофантова
уравнения ax by c . Тогда его общее решение задается формулами:
x x0 bt
y y0 at.
Доказательство. То, что правые части указанных в формулировке
теоремы равенств действительно являются решениями, проверяется их
непосредственной подстановкой в исходное уравнение. Покажем, что любое
решение уравнения ax by c имеет именно такой вид, какой указан в
формулировке теоремы. Пусть
x , y
*
*
— какое-нибудь решение уравнения
ax by c . Тогда ax* by* c , но ведь и ax0 by0 c . Вычтем из первого
равенства второе и получим:
a x* x0 b y* y0 0
— однородное уравнение. Далее, воспользуемся случаем 1, пишем сразу общее
решение: x* x0 bt , y* y0 at , откуда получаем:
x* x0 bt
*
y y0 at.

16.

Пример 3. Решить в целых числах уравнение 7 x 12 y 43 .
Решение. Воспользуемся алгоритмом Евклида:
12 = 7 · 1 + 5
7=5·1+2
5=2·2+1
2=1·2
Значит, наибольший общий делитель 7 и 12 равен 1, а его линейное
выражение следующее:
1 = 5 – 2 · 2 = 5 – (7 — 5) · 2 = (12 – 7) – (7 – (12 – 7) · 2) = 12 · 3 + 7 · (-5),
т.е. u 5 , v 3 . Частное решение:
x0 uc 5 43 215
y0 vc 3 43 129 .
Общее решение диофантового уравнения:
x 215 12t
y 129 7t .
легко видеть, что при t 18 , получаются x 1 , y 3 .

Линейное диофантово уравнение и 4 способа его решения

Првило 1. Если с не делится на d, то уравнение ах + ву = с не имеет решений в целых числах. Н.О.Д.(а,в) = d.

Правило 2. Чтобы найти решение уравнения ах + ву = с при взаимно-простых а и в, нужно сначала найти решение (Х_о ; у_о) уравнения ах + ву = 1; числа СХ_о , Су_о составляют решение уравнения ах + ву = с.

Решить в целых числах (х,у) уравнение

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

Знаем, что если Н.О.Д.(а;в) =1, т.е. а и в взаимно-простые числа, то уравнение (1)

имеет решение в целых числах х и у. Н.О.Д.(5;8) =1. Методом подбора находим частное решение: Х_о = 7; у_о =2.

Итак, пара чисел (7;2) — частное решение уравнения (1).

Значит, выполняется равенство: 5 x 7 – 8 x 2 = 19 … (2)

Вопрос: Как имея одно решение записать все остальные решения?

Вычтем из уравнения (1) равенство (2) и получим: 5(х -7) – 8(у — 2) =0.

Отсюда х – 7 = . Из полученного равенства видно, что число (х – 7) будет целым тогда и только тогда, когда (у – 2) делится на 5, т.е. у – 2 = 5n, где n какое-нибудь целое число. Итак, у = 2 + 5n, х = 7 + 8n, где n Z.

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

Второй способ. Решение уравнения относительно одного неизвестного.

Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент. 5х — 8у = 19 х = .

Остатки при делении на 5: 0,1,2,3,4. Подставим вместо у эти числа.

Если у = 2, то х = = = 7 Z.

Итак, частным решением является пара (7;2).

Тогда общее решение: n Z.

Третий способ. Универсальный способ поиска частного решения.

Для решения применим алгоритм Евклида. Мы знаем, что для любых двух натуральных чисел а, в, таких, что Н.О.Д.(а,в) = 1 существуют целые числа х,у такие, что ах + ву = 1.

1. Сначала решим уравнение 5m – 8n = 1 используя алгоритм Евклида.

2. Затем найдем частное решение уравнения (1)по правилу 2.

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

1. Найдем представление: 1 = 5m – 8n. Для этого используем алгоритм Евклида.

Из этого равенства выразим 1. 1 = 3 — 2 = 3 – (5 — 3 ) =

= 3 — 5 = 3 = (8 — 5 — 5 82 -5

= 5(-2). Итак, m = -3, n = -2.

2. Частное решение уравнения (1): Х_о = 19m; у_о =19n.

Пара (-57; -38)- частное решение (1).

3. Общее решение уравнения (1): n Z.

Четвертый способ. Геометрический.

1. Решим уравнение 5х – 8у = 1 геометрически.

2. Запишем частное решение уравнения (1).

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

Отложим на окружности последовательно друг за другом равные дуги, составляющие

-ю часть полной окружности. За 8 шагов получим все вершины правильного вписанного в окружность 8-угольника. При этом сделаем 5 полных оборотов.

На 5 – ом шаге получили вершину, соседнюю с начальной, при этом сделали 3 полных оборота и еще прошли — ю часть окружности, так что х = у + .

Итак, Х_о = 5, у_о =3 является частным решением уравнения 5х – 8у = 1.

2. Частное решение уравнения (1): Х_о = 19 у_о =19

3. Общее решение уравнения (1): n Z.

Как решать диофантовы уравнения алгоритмом евклида

XVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

• Главная
• Список секций
• Математика
• АЛГОРИТМ ЕВКЛИДА И ЛИНЕЙНЫЕ ДИОФАНТОВЫ УРАВНЕНИЯ

АЛГОРИТМ ЕВКЛИДА И ЛИНЕЙНЫЕ ДИОФАНТОВЫ УРАВНЕНИЯ

Ковин И.А. 1
1 г.Тюмень, МАОУ СОШ №25, к.1
Мишукова С.А. 1
1 МАОУ СОШ №25, г.Тюмень

Автор работы награжден дипломом победителя III степени

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке «Файлы работы» в формате PDF

«Алгоритм Евклида и линейные диофантовы уравнения» – справедливо считаются одним из интереснейших разделов алгебры. Знания из данного раздела помогут при решении олимпиадных задач. В данной работе мы подробно изучили выше перечисленную тему

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

Цель проекта: погрузиться в такой раздел алгебры, как «Алгоритм Евклида и линейные диофантовы уравнения», изучить диофантовы уравнения и способы их решения. Обобщить полученные знания и представить их в виде буклета для уроков алгебры и математики.

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

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

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

Систематизировать полученные знания и представить их в виде буклета для использования на дополнительных занятиях по математике.

Объект исследования: линейные уравнения.

Предмет исследования: диофантовы уравнения, типы и способы их решения, алгоритм Евклида.

Методы исследования: изучение, ознакомление, опрос, сравнение, анализ, обобщение.

В школе на уроках алгебры мы часто затрагиваем тему уравнений с двумя переменными. Однако многим ученикам сложно решать линейные уравнения из-за недостаточного углубления в тему. Диофантовы уравнения являются одним из типов линейных уравнений. Для решения таких уравнений существует множество методов и в ходе нашего исследования мы задались вопросом: Какой метод решения линейных диофантовых уравнений самый понятный и быстрый?

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

Гипотеза: если учащиеся недостаточно знают такое понятие, как «Алгоритм Евклида и линейные диофантовы уравнения», то пробуждение интереса и совместная работа по этой теме позволит лучше в ней ориентироваться, решать некоторые нестандартные и олимпиадные задания, а также подготовиться к решению ряда задач ЕГЭ.

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

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

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

Систематизировать полученные знания и представить их в виде буклета для использования на дополнительных занятиях по математике.

Объект исследования: линейные уравнения.

Предмет исследования: диофантовы уравнения, типы и способы их решения.

Методы исследования:

изучение различных методов решения диофантовых уравнений

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

сравнительный анализ результатов

Практическое применение: данную работу можно применить на уроках алгебры и математики.

I. Теоретическая часть

Диофант – древнегреческий ученый из Александрии. О его жизни нет почти никаких сведений. Известно, что он прожил 84 года. Использовал не геометрический подход, как это было принято у древних греков, а его решения предвосхищают алгебраические и теоретические методы. Сохранилась часть математического трактата Диофанта «Арифметика», книги о многоугольных числах. Именем Диофанта названы 2 больших раздела теории «чисел-теория диофантовых чисел» и «теория диофантовых приближений»[5].

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

«Арифметика» Диофанта — это сборник задач, каждая из которых снабжена решением и необходимым пояснением. В собрание входят весьма разнообразные задачи, а их решение часто в высшей степени остроумно. Диофант практиковался в нахождении решений неопределенных уравнений вида , или систем таких уравнений. Типично для Диофанта, что его интересуют только положительные целые и рациональные решения. Иррациональные решения он называет «невозможными» и тщательно подбирает коэффициенты так, чтобы получились искомые положительные, рациональные решения[5].

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

1.2 Диофантовы уравнения

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

где а и b — целые взаимно простые числа, имеют бесконечно много решений: если х₀ и у₀ — одно решение, то числа х = х₀ + bn, y = y₀ — an тоже будут решениями.

Чтобы решить линейное диофантово уравнение, нужно найти значения переменных «х» и «у», которые являются целыми числами. Целочисленное решение сложнее обычного и требует определенного набора действий. Сначала необходимо вычислить НОД коэффициентов, а затем найти решение. Если вы нашли одно целочисленное решение линейного уравнения, можно применить простой шаблон, чтобы найти бесконечное множество других решений[5].

Запишем уравнение в стандартной форме:

Линейное уравнение — это уравнение, в котором показатели степени переменных не превышают 1. Чтобы решить такое линейное уравнение, сначала запишите его в стандартной форме. Стандартная форма линейного уравнения выглядит так: Ax + By = C , где A , B и C — целые числа.

Если уравнение дано в другой форме, приведите его к стандартной форме с помощью основных алгебраических действий. Например, дано уравнение : 23 x + 4 y – 7 x = -3 y +15. Приведите подобные члены и запишите уравнение так: 16 x +7 y = 15

Упростите уравнение. Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты A , B и C . Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.

Например, если все три коэффициента четные, разделите их как минимум на 2.

42 x + 36 y = 48 (все члены делятся на 2)

21 x + 18 y = 24(теперь все члены делятся на 3)

7 x + 6 y = 8(это уравнение больше нельзя упростить)[6]

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

Евклид (325-265 гг. до н.э.) – древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Первый математик Александрийской школы. В своем фундаментальном труде «Начала» описывал планиметрию, стереометрию и теорию чисел[1].

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

Алгоритм Евклида — это ряд повторных делений, в котором предыдущий остаток используется как следующий делитель. Последний делитель, который делит числа нацело, является наибольшим общим делителем (НОД) двух чисел[1].

Например, найдем НОД чисел 272 и 36 с помощью алгоритма Евклида:

272 = 7*36 + 20 — разделите большее число (272) на меньшее (36) и обратите внимание на остаток (20);

36 = 1*20 + 16 — разделите предыдущий делитель (36) на предыдущий остаток (20). Обратите внимание на новый остаток (16);

20 = 1*16 + 4 — разделите предыдущий делитель (20) на предыдущий остаток (16). Обратите внимание на новый остаток (4);

16 = 4*4 + 0 — разделите предыдущий делитель (16) на предыдущий остаток (4). Так как остаток равен 0, можно сказать, что 4 является НОД исходных двух чисел 272 и 36[2].

II. Практическая часть

2.1 Решение задач с помощью диофантовых уравнений.

В магазине продаётся шоколад двух видов: молочный и горький. Весь шоколад хранится в коробках. Молочного шоколада на складе имеется 7 коробок, а горького 4. Известно, что горького шоколада было на одну плитку больше. Сколько плиток шоколада находятся в коробках каждого вида?

Пусть х – количество плиток молочного шоколада в одной коробке,

у – количество плиток горького шоколада в одной коробке,

тогда по условию этой задачи можно составить уравнение:

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

Выразим 7=4∙1+3, следовательно 3=7-4∙1.

Выразим 4=3∙1+1, следовательно 1=4-3∙1=4-(7-4∙1)=4-7+4∙1=4∙2-7∙1=1.

Ответ: молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки[7].

В каталоге картинной галереи всего 96 картин. На каких-то страницах расположено 4 картины, а на каких-то 6. Сколько страниц каждого вида есть в каталоге?

Пусть х – количество страниц с четырьмя картинами,

у – количество страниц с шестью картинами,

тогда по условию этой задачи можно составить уравнение:

Решим задачу, используя метод относительно одного неизвестного.

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

Делим все уравнение на этот коэффициент:

Остатки при делении на 4: 1,2,3. Подставим вместо у эти числа.

Если у=1, то х=(96-6∙1):4=90:4 — Не походит, решение не в целых числах.

Если у=2, то х=(96-6∙2):4=21 – Подходит.

Если у=3, то х=(96-6∙3):4=78:4 — Не походит, решение не в целых числах.

Ответ: на 21 странице расположено по 4 картины, а на 2 страницах по 6 картин[3].

У мальчика было 50 копеек, на которые он хотел купить почтовые марки. В киоске имелись марки по 3 копейки и по 4 копейки, но у киоскера совсем не было мелочи. Помогите мальчику и киоскеру выйти из создавшегося положения.

Пусть х — марок по 3 копейки. Тогда у – марок по 4 копейки. Тогда по условию этой задачи можно составить уравнение:

Решим задачу, используя графический метод:

Подберём значения для «x» и найдём значение «у».

Если х = 2, тогда:

Если х = 3, тогда:

Если х = 4, тогда:

Тогда, составив график функций, можно заметить что значение х = 3 не подходит для решения задачи, а подходящими значениями являются: х = 2; у = 14 и х = 4; у = 3.

Задача имеет множество вариантов решений.

Ответ: мальчик может купить как 2 марки по 3 копейки и 14 марок по 4 копейки, так и 4 марки по 3 копейки и 3 марки по 4 копейки[7].

2.2 Результаты анкетирования

Мы решили выяснить, что знают учащиеся 8, 10 и 11 классов о диофантовых уравнениях и способах их решений. Для этого мы провели анкетирование 50 человек по следующим вопросам (Приложение 2).

Знаете ли вы, что такое диофантовы уравнения? Как показывает приложение 2, больше половины (66%) ребят ответили, что они не знают, что такое диофантовы уравнения, 34% — знают.

Сталкивались ли Вы с трудностями при решении линейных уравнений с двумя переменными? 48% ребят сталкивались с трудностями, 52% — не сталкивались.

Знаете ли Вы, что такое «Алгоритм Евклида»? 30% ответили, что знают, 70% — что не знают.

Как вы считаете, достаточно ли времени выделяется на уроках алгебры для

изучения линейных диофантовых уравнений и способов их решения? 62% ребят считают, что недостаточно времени, 38% ответили, что достаточно.

В результате анкетирования мы выяснили, что учащимся не достаточно времени для изучения данной темы и многие не ознакомлены с понятием «Алгоритм Евклида».

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

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

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

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

Вагутен В. Н. «Алгоритм Евклида и основная теорема арифметики // Квант. 1972 №6»

Гельфонд А. О. «Решение уравнений в целых числах. — М.: Наука, 1978»

Горбачёв Н. В. «Сборник олимпиадных задач по математике. МЦНМО, 2004»

Лепёхин Ю. В. «Математика. Задания для подготовки к олимпиадам. 7-8 / Волгоград: Учитель, 2015»

Михайлов И. «О диофантовом анализе // Квант. 1980 №6. Факультативный курс по математике. 7-9 / сост. И. Л. Никольская. М.: Просвещение, 1991»

Пичурин Л. Ф. «За страницами учебника алгебры 7-9 / М.: Просвещение»

Фарков А. В. «Готовимся к олимпиадам по математике / М.: Издательство «Экзамен». 2007»

Рис. 1. Портрет Диофанта – древнегреческого математика.

Рис. 2. Книга «Арифметика» – древнегреческая рукопись по математике, созданная

Диофантом в III веке.

Рис. 3. Портрет Евклида — древнегреческого математика.

Рис. 4. Алгоритм Евклида

Анкета для учащихся 8-11 классов

Знаете ли вы, что такое диофантовы уравнения?

Сталкивались ли Вы с трудностями при решении линейных уравнений с двумя переменными

А)Да Б)Нет, никогда не сталкивался(ась)

Знаете ли Вы, что такое «Алгоритм Евклида»?

Как вы считаете, достаточно ли времени выделяется на уроках алгебры для изучения линейных диофантовых уравнений и способов их решения?

А) Да, достаточно Б) Нет, недостаточно

Результаты анкетирования:

Рис.1. Результаты вопроса №1

Рис.2. Результаты вопроса №2

Рис.3. Результаты вопроса №3

Рис.4 Результаты вопроса №4

Рис. 1. Буклет для урок алгебры и математики по теме «Алгоритм Евклида и линейные диафантов уравнения»

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

Здравствуйте, уважаемые читатели! Продолжаю серию дилетантских статей о математике.

• Первая часть
• Вторая часть

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

где — множество любых действительных чисел.

Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.

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

где — множество целых чисел.

Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить как рациональное (дробное) число. Так как же решить это уравнение исключительно в целых числах?

Заинтересовавшихся решением данной задачи прошу под кат.

А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:

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

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

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

Вспоминая, что справедливо говорить, что . А подставив заместо полученный выше результат получим:

Тут мы также видим, что что какие бы не были , всё равно останется целым числом, и это по-прежнему прекрасно.

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

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

Подставим в исходное уравнение:

Тождественно, круто! Давайте попробуем ещё разок на другом примере?

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

Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое — это брать коэффициенты из уравнения которые самые близкие к единице. Однако нужно понимать, что за скобку можно взять только лишь то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Итак:

Введем замену , тогда получим:

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

Введем замену , тогда:

Выразим отсюда нашу одинокую неизвестную :

Из этого следует, что какие бы мы не взяли, все равно останется целым числом. Тогда найдем из соотношения :

Аналогичным образом найдем из соотношения :

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

Таким образом, осталось ответить на вопрос — а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:

Для его решения в целых числах достаточно выполнение следующего условия:

Доказательство

Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.

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

1. Проверяем, а решаемо ли уравнение вообще (вышеописанным свойством ). Если ответ положительный — переходим к следующему пункту.
2. Для ускорения процесса поделим все коэффициенты (включая свободный член) на их .
3. Избавляемся от отрицательных коэффициентов в уравнении заменой
4. Проводим серию замен (разваливая некоторые члены уравнения на суммы и объединяя их в скобки) таким образом, чтобы в конце концов один из членов уравнения был с единичным коэффициентов, и мы смогли вывести его без какого либо деления. Помня при этом, что за скобку можно взять только то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Наконец, объявляем все переменные, через которые выражена оная, как свободные.
5. Выводим остальные переменные через вышевыведенную (выводим из всех наших замен), не забывая также про обратные замены.
6. Объединяем все в единую систему решений.

С вами был Петр,
спасибо за внимание.