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

• 1 слайд

  Применение алгоритма Евклида для нахождения наибольшего общего делителя двух чисел
  Вспомним, что наибольший общий делитель двух чисел есть последний отличный от нуля остаток в цепочке указанных в примере действий.
  Перейдем теперь к решению линейного уравнения с двумя неизвестными:
  ax + by = c (1)
  Возможны два случая: либо число c делится на
  d = НОД(a,b), либо нет.
  В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a1x + b1y = c1, коэффициенты которого a1 = a/d и b1 = b/d взаимно просты.
  Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делиться на d и поэтому не может равняться числу c, которое на d не делится.
  
  
  

• 2 слайд

  Определение1. Уравнение, в котором число неизвестных более одного, называется неопределенным.
  Определение 2. Неопределённые равнения, в котором ищут только целые решения, называются диофантовыми.
  Определение3 Неоднородным диофантовым уравнением первого порядка с двумя неизвестными x, y называется уравнение вида
  аx + вy = с, где а, в, с, х, у Z с 0
  Утверждение 1. Если свободный член с в уравнении (1) не делится на наибольший общий делитель (НОД) чисел а и в, то уравнение (1) не имеет целых решений.
  Пример: 34x – 17y = 3. НОД (34; 17) = 17, 3 не делится нацело на 17, в целых числах решения нет.
  

• 3 слайд

  Пусть с делится на НОД (а,в). Делением всех коэффициентов можно добиться, что а и в станут взаимно простыми.
  Утверждение 2. Если а и в уравнения (1) взаимно простые числа, то это уравнение имеет по крайней мере одно решение.
  Утверждение 3. Если коэффициенты а и в уравнения (1) являются взаимно простыми числами, то это уравнение имеет бесконечно много решений, найденных из системы:
  x = cx0 + bt,
  y = cy0 – at.
  Здесь t – любое целое число.
  (x0 ; y0 ) – какое-либо решение уравнения (1), t Z
  Определение4. Однородным диофантовым уравнением первого порядка с двумя неизвестными x, y называется уравнение вида (2)
  аx + вy = 0, где а,в, x, y  Z
  Утверждение 4. Если а и в – взаимно простые числа, то всякое решение уравнения (2) имеет вид
  x = bt,
  y = -at.
  .
  

• 4 слайд

  Для решения уравнений с двумя переменными в целых числах существует несколько правил, которые можно отобразить в алгоритме
  Алгоритм решения линейных диофантовых уравнений
  Проверить, имеет ли уравнение решение в целых числах, для этого найти НОД(а,в) с помощью алгоритма Евклида.
  Если с делится на НОД(а,в), то уравнение следует упростить разделив обе его части на НОД(а,в).
  Найти решения уравнения аx + вy = 1, где а, в, х, у  Z ,выписать их согласно Утверждению 3, а затем умножить их на с.
  Вернуться к условиям, накладываемым к решению уравнения.
  

• 5 слайд

  Пример
  Решите Диофантово уравнение при помощи НОД, найденного по алгоритму Эвклида:
  47x − 111y = 89.
  Решение.
  Если НОД(a, b) = 1, то найдутся такие x, y, что a · x + b · y = 1.
  Тогда выполнится: ax · c + by · c = c.
  НОД (47, 111) = 1.
  Найдем x, y:
  111 = 47 · 2 + 17
  47 = 17 · 2 + 13
  17 = 13 · 1 + 4
  13 = 4 · 3 + 1
  4 = =1 · 4 + 0.
  Тогда выполняется: 89 = 47 · (89 · 26) − 111 · (89 · 11).
  x = 89 · 26 + 111t
  y = 89 · 11 - 47t, где t — любое целое.
  Ответ. x = 2314 + 111t,
  y = 979 - 47t, t = Z.
  

• 6 слайд

  Задание
  Решить уравнение на множестве целых чисел
  а) 7х+11у=69
  НОД(7;11)=1, Найдем значение х0 и у0 для получения решений уравнения по формулам (3). Применим алгоритм Евклида к числам 11 и 7:
  
  
  Таким образом, получаем: , следовательно х0 = –3, у0=2
  Запишем общее решение уравнения на множестве целых чисел согласно формулам (3):
  
  
  Придавая конкретные целые значения t, можно получить частные решения уравнения. Например, при t=1, имеем x= –196, у=131.
  
  

• 7 слайд

  Задача
  Для настилки пола шириной в 3 метра имеются доски шириной в 11 см и 13 см. Сколько нужно взять досок того и другого размера?
  Решение.
  Очевидно, что если х - число досок шириной в 11 см, а у – количество досок шириной 13 см, то нам надо решить уравнение
  11х+13у=300 в натуральных числах.
  Попробуем сначала это уравнение решить в целых числах, а затем уже в натуральных.
  НОД(11,13)=1
  Находим его линейное разложение: 1=11·6+13·(-5).
  Умножаем обе части части на 300, получаем
  

• 8 слайд

• 9 слайд

  Решить уравнения в целых числах:
  8x + 14y = 32
  Решение.
  8x + 14y = 32
  1) НОД(8, 14)=2.
  2 делится на 32, следовательно, уравнение имеет целые решения и его можно упростить, разделив обе части на 2.
  2) Решим уравнение 4x+7y=16.
  

• 10 слайд

• 11 слайд

  Решить уравнениe в целых числах:
  2) 9x – 18y = 5
  Решение.
  1) НОД(9,18)=9.
  5 не делится нацело на 9, в целых числах решений нет.
  Ответ: нет целых решений.
  

• 12 слайд

  Как имея монеты в 5 копеек и в 3 копейки заплатить кассиру в магазине 13 копеек?
  
  Решение.
  По условию задачи можно составить cледующее уравнение:
  5x+3y=13.
  1) НОД(5,3)=1, следовательно, целые решения уравнения имеются.
  2) 1=5·(-1)+3·2 – линейное разложение НОД(5,3).
  3) 1=5·(-1)+3·2
  

• 13 слайд

• 14 слайд

  Самостоятельная работа в парах
  1. Решить уравнения в целых числах:
  1) 3x – 4y = 1
  14x–46y=72
  
  2. Несколько детей собирали яблоки. Каждый мальчик собрал по 21 кг, а
  девочка по 15 кг. Всего они собрали 174 кг. Сколько мальчиков и сколько
  девочек собирали яблоки? Ответ: мальчиков 4, девочек 6.
  
  3. В мешке у нищенки Лисы Алисы не менее 250 купюр по 200 рублей и не
  менее 100 купюр по 500 рублей Определите число способов, с помощью
  которых она может этими купюрами разменять 50000 рублей (только без
  обмана!)
  
  4. У вас в кармане монеты достоинством только 7 копеек и 13 копеек, а вам
  надо уплатить 43 копейки. Как это сделать?
  

• 15 слайд

• 16 слайд

• 17 слайд

  Список литературы
  
  
  1. Детская энциклопедия “Педагогика”, Москва, 1972 г.
  2. Алгебра-8, Н.Я. Виленкин, ВО “Наука”, Новосибирск, 1992 г.
  3. Конкурсные задачи, основанные на теории чисел. В.Я. Галкин, Д.Ю. Сычугов.
  МГУ, ВМК, Москва, 2005г.
  4. Задачи повышенной трудности в курсе алгебры 7-9 классов. Н.П. Косрыкина. “Просвещение”, Москва, 1991г.
  5. Алгебра 7, Макарычев Ю.Н., “Просвещение”.
  
  
  

• 18 слайд

  Диофантовы уравнения n-ной степени
  В отличие от уравнений первой степени, алгоритмы решения диофантовых уравнений более высоких степеней в общем виде отсутствуют. Более того, существуют различные классы диофантовых уравнений, которые не имеют решений. Остановимся подробнее на частных случаях диофантовых уравнений степени > 2.
  Пример 11.
  а) (2x + y)(5x + 3y) = 7;
  б) xy = x + y + 3;
  в) x 2 = 14 + y 2 ;
  г) x 2 + y 2 = x + y + 2.
  

• 19 слайд

  Решение
  xy = x + y + 3
  Решение этих задач связано с идеей перебора. После преобразования уравнения (чаще всего разложение на множители) перебор сводится к ограниченному количеству пар. Например, уравнение xy = x + y + 3 после преобразования имеет вид (x - 1)(y - 1) = 4. Рассматривая разложение 4 в произведение двух целых множителей получаем ответ:
  (5; 2), (2; 5), (0;-3),(-3; 0), (3; 3), (-1;-1).
  

Краткое описание документа:

Список литературы:

1. Детская энциклопедия “Педагогика”, Москва, 1972 г.

2. Алгебра-8, Н.Я. Виленкин, ВО “Наука”, Новосибирск, 1992 г.

3. Конкурсные задачи, основанные на теории чисел. В.Я. Галкин, Д.Ю. Сычугов.

МГУ, ВМК, Москва, 2005г.

4. Задачи повышенной трудности в курсе алгебры 7-9 классов. Н.П. Косрыкина. “Просвещение”, Москва, 1991г.

5. Алгебра 7, Макарычев Ю.Н., “Просвещение”.