Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2008_2009/8mat_0809/spec/list_12_alg_evklida.pdf Дата изменения: Sun Sep 2 20:56:15 2012 Дата индексирования: Tue Feb 5 07:49:49 2013 Кодировка: koi8-r Поисковые слова: чеюпэл мвнепдвфы

Гимназия 1543, 8 класс, 2008-2009.

В этом листке мы по-прежнему имеем дело только с целыми числами. Пусть даны два натуральных числа, a и b. Существуют ли у них общие делители | такие натуральные числа c, на которые делится как a, так и b, и много ли их? Одно такое число c всегда существует, это число 1. Бывает так, что этим дело и ограничивается | тогда говорят, что a и b взаимно простые числа. Например, 15 и 43 взаимно простые. Бывает, что общих делителей несколько. Наибольший из них называется наибольшим общим делителем чисел a и b и обозначается аббревиатурой Н ОД (a; b). Ясно, что два числа взаимно просты если и только если их наибольший общий делитель равен единице. 1) Найдите Н ОД (43; 1543), Н ОД (1255; 2008). Школьная практика предлагает пользоваться для нахождения НОД разложением на простые множители. Этот способ часто удобен, но у него есть большой недостаток: разложить большое число на множители чрезвычайно трудно. Попробуйте найти, например, Н ОД (54739; 205757). Есть сравнительно простой алгоритм нахождения наибольшего общего делителя двух чисел. Его приписывают Евклиду, одному из величайших математиков древности. Евклид жил в III-II в до н.э. в Александрии, а по другим источникам, в Дамаске. Оставил несколько сочинений, известных в латинсих и арабских переводах, наиболее значительное из которых | состоящие из 13-ти книг "Начала" ("Elements") | представляет собой систематическое изложение математики того времени. Алгоритм Евклида описан в VIII книге начал и принадлежит, по-видимому, Архиту Тарентскому. 2) Докажите, что, если a > b, то Н ОД (a; b) = Н ОД (b; a - b). 3) Докажите, что, если a = bk + r, то Н ОД (a; b) = Н ОД (b; r). На решении задачи 3) и основан алгоритм Евклида нахождения НОД. Большее число делят с остатком на меньшее и переходят к паре (меньшее число, остаток). С ней поступают так же, и так далее, пока в очередной паре большее число не разделится нацело на меньшее. Это самое меньшее число и будет искомым наибольшим общим делителем. 4) Почему алгоритм Евклида заканчивает работу и приводит к нужному результату? 5) Найдите Н ОД (54739; 205757). С понятием наибольшего общего делителя тесно связано понятие наименьшего общего кратного двух чисел. Для всяких двух чисел нетрудно найти их общее кратное | число, кратное им обоим. В качестве общего кратного для чисел a и b подойдёт, например, их произведение ab. Но иногда есть общие кратные, меньшие, чем ab. Самое маленькое называется наименьшим общим кратным чисел a и b и обозначается Н ОК (a; b). Для практического нахождения НОК можно использовать результат задачи 10.
b 6) Пусть Н ОД (a; b) = d. Докажите, что числа a и d взаимно просты. d 7) Вычислите а) Н ОД (12345678; 87654321), б) Н ОД (2n2 - 1; n + 1), в) Н ОД (111 : : : 11; 111 : : : 11) (в первом числе m, а во втором n единиц). 8) Коля берёт прямоугольный бумажный лист m в n см, отрезает от него квадрат и кидает его на пол. От оставшегося прямоугольника он снова отрезает квадрат, кидает на пол и так далее, до тех пор, пока это возможно. Что останется в руках у Коли, когда он закончит свою деятельность и приступит к уборке мусора? 9) Пусть u = Н ОК (a; b), а m | какое-то другое о бщее кратное a и b. Докажите, что u|m. (Подсказка: разделите m на u с остатком.) 10) Докажите, что Н ОД (a; b) · Н ОК (a; b) = ab. 11) На кольцевой линии метро 323 станции. Поезд-экспресс останавливается на каждой 57-ой станции (то есть, на 1-ой, 58-й, 115-й и т. д.). Сколько перегонов проедет поезд прежде чем снова впервые остановится на 1-ой станции? На скольких станциях он к этому моменту остановится? Сколько раз на каждой? 12) Задано натуральное число a. Какое наибольшее значение может принимать Н ОД (n2 + a; (n + 1)2 + a)? 13) Женя прыгает по железной дороге либо вперёд на 15 шпал, либо назад на 43 шпалы. Сможет ли Женя (ловко уворачиваясь от проходящих поездов) допрыгать от Москвы до Нижнего Новгорода? 14) Есть две банки, ёмкости которых равны 310 мл и 210 мл. Можно ли с помощью этих двух банок перелить из полной бочки достаточного о бъема в такую же пустую 3 л воды? 10 мл воды? 45 мл воды? 15) Фальшивомонетчик Билл печатает банкноты достоинством 17 долларов, а фальшивомонетчик Джим | банкноты достоинством 23 доллара. Джим задолжал Биллу 10 долларов. Как им расплатиться (у каждого есть только напечатанные им купюры)? Придумайте несколько спосо бов. Уравнения вида ax + by = c, возникающие при решении последних задач, называются линейными диофан. товыми уравнениями с двумя переменными. Очевидно, что если c . Н ОД (a; b), то уравнение неразрешимо.

Теория и разминка.

НОД и НОК. Алгоритм Евклида.

Листок 3.3, 24 ноября.

Задачи: