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

Слайд #1

Государственное бюджетное общеобразовательное учреждение
Нижегородская кадетская школа




Применение алгоритма Евклида для решения линейных диофантовых уравнений в двумя неизвестными
Выполнил:
Пономарев Кирилл, 8г класс

Научный руководитель:
Иванов А.А., учитель математики
г.Нижний Новгород, 2024

Слайд #2

Цель работы:
 исследовать и применить алгоритм Евклида для эффективного решения диофантовых уравнений.
 Задачи:
 1. Изучить теорию по теме: «Применение алгоритма Евклида для решения диафантовых уравнений с двумя
неизвестными»
2. Научиться решать задачи при помощи алгоритма Евклида и линейных
диафантовых уравнений

Слайд #3

Диофант
Евклид

Слайд #4

Алгоритм Евклида
Определение 1
Пусть 𝑎, 𝑏 принадлежит ℤ. Число 𝑎 делится на число 𝑏, если найдется такое число 𝑞 принадлежащее ℤ, что 𝑎=𝑞𝑏. Синонимы: 𝑎 кратно 𝑏, 𝑏 - делитель 𝑎. Запись 𝑎:𝑏 или 𝑏/𝑎.
Теорема 1
Для данного целого отличного от нуля числа b, всякое целое число a единственным образом представимо в виде 𝑎=𝑏𝑞+𝑟, где 0≤𝑟< 𝑏 .
Также введем понятие наибольший общий делитель (НОД)
Определение 2
Число 𝑑∈ℤ , делящее одновременно числа 𝑎,𝑏,𝑐…𝑘∈ℤ , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем.

Слайд #5

Пример
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12/6=2 остаток 0
НОД — это делитель 6.
НОД 30,18 =6

Слайд #6

Теорема 2
Если 𝑎=𝑏𝑞+𝑐, то (𝑎,𝑏)=(𝑏,𝑐)
Для отыскания (𝑎,𝑏) при 𝑎>𝑏 применяется алгоритм Евклида, основанный на теореме.
Пример 1
Найти с помощью алгоритма Евклида (2004,1941)
2004=1941×1+63
1941=63×30+51
63=51×1+12
51=12×4+3
12=3×4
Ответ: (2004,1941) = 3
 

Слайд #7

Диафантовы уравнения
Определение 3
Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида 𝑎𝑥 + 𝑏𝑦 = 𝑐, где 𝑎, 𝑏, 𝑐 ∈ 𝑍 и (𝑎, 𝑏, 𝑐) = 1.
Определение 4
Решением уравнения 𝑎𝑥 + 𝑏𝑦 = 𝑐, где 𝑎, 𝑏, 𝑐 ∈ 𝑍 и (𝑎, 𝑏, 𝑐) = 1, называется пара целых чисел, при подстановке которых в уравнение
𝑎𝑥 + 𝑏𝑦 = с получается верное числовое равенство.
Теорема 3
Диофантово уравнение 𝑎𝑥 + 𝑏𝑦 = 𝑐 разрешено в целых числах тогда и только тогда, когда (a, b) = 1.

Слайд #8

Решение задачи при помощи алгоритма Евклида и диофантовых уравнений
Пусть х – количество плиток молочного шоколада в одной коробке,
у – количество плиток горького шоколада в одной коробке,
тогда по условию этой задачи можно составить уравнение:
4у-7х=1.
Решим это уравнение, используя алгоритм Евклида.
4у-7х=1;
Выразим 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.
Ответ: молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки.

Слайд #9

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

Слайд #10

Используемая литература
Вагутен В.Н. алгоритм Евклида и основная теорема арифметики// квант .1972 №6
Галкин Е.В нестандартные задачи по математики. –Челябинск Взгляд 2005