Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

ИНСТИТУТ ФИЗИКО-МАТЕМАТИЧЕСКОГО И ИНФОРМАЦИОННО - ЭКОНОМИЧЕСКОГО ОБРАЗОВАНИЯ

КАФЕДРА АЛГЕБРЫ И МАТЕМАТИЧЕСКОГО АНАЛИЗА

Дипломная работа

Выполнил

Вишнякова Наталья Анатольевна

Научный руководитель:

Юрий Васильевич Сосновский

Новосибирск 2016

Содержание

Введение

Глава 1. Алгоритм Евклида

1.1 Теорема о делении с остатком

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

1.3 Свойства наибольшего общего делителядвух натуральных чисел

1.4 Алгоритм Евклида для трёх и более натуральных чисел

1.5 Наименьшее общее кратное

1.6 Нахождение наименьшего общего кратного трёх и более натуральных чисел

1.7 Решение диофантова уравнения первой степени

Глава 2. Факультатив «Алгоритм Евклида для целых чисел»

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

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

2.3 Занятие «Нахождение наибольшего общего делителядвух натуральных чисел по алгоритму Евклида»

2.4 Занятие «Наименьшее общее кратное»

Заключение

Литература

Введение

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

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

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

Для нахождения наибольшего общего делителя и наименьшего общего кратного современные школьные учебники по математике предлагают использовать каноническое разложение. В общем случае отыскание канонического разложения для отличного от единицы натурального числа очень трудоёмкий вычислительный процесс, который невозможен без знания хотя бы до определённых пределов таблицы простых чисел. Однако этот алгоритм хорош для натуральных чисел из промежутка [1; 100], которые восновном и используются в школе. Наверное, этим обстоятельством и объясняется выбор алгоритма нахождения наибольшего общего делителя на основе использования канонического разложения.

Несравнимо менее трудоёмкий алгоритм Евклида приводится далеко не во всех школьных учебниках, хотя у классика А. П. Киселёва он есть. Уже для натуральных чисел из промежутка [101; 1000] заметна разница в трудоёмкости для этих двух алгоритмов. В выпускной квалификационной работе эта разница иллюстрируется на примерах факультатива.

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

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

Цель исследования определила следующие задачи:

1) изучить теоретический материал по данной теме, включая вопросы о количестве делений в алгоритме Евклида;

2) разработать факультативный курс по данной теме, апробировать его и после апробации внести необходимые коррективы;

3) выяснить

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

б) заметна ли школьникам разница в трудоёмкости двух алгоритмов вычисления наибольшего общего делителя.

Глава 1. Алгоритм Евклида

1.1 Теорема о делении с остатком

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

N = {1, 2, 3,…} - множество натуральных чисел, ЈЪ= {0, 1, -1, 2, -2,…} - множество целых чисел.

Определение. Говорят, что целое числоа делится на ненулевое целое число в, если существует целое число с, такое, что а = в • с.

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

Пример. Так как 4 = 2 • 2, 6 = (-3)·(-2), то 4 2, 6 (-3).

Отметим, что знак числа не влияет на делимость целых чисел.Действительно, если для целого а и ненулевого целого ввыполняется условие а в , т.е. а = в·с , с є Z, то выполняются и условия:а (-в),

(-а) в, (-а) (-в), поскольку справедливы равенства: а = (-в) •(- с),

(-а) = в • (-с), (-а) = (-в) • с, и включение -сє ЈЪ.

Для краткости изложения будем считать, что везде в дальнейшем условие

а в означает справедливость равенства а = в·с, включений а, в, с є ЈЪи неравенства в ? 0.

Простейшие свойства делимости целых чисел соберём в теорему.

Теорема 1.Пусть а, в, с - ненулевые целые числа, тогда справедливы следующие свойства:

1) а а;

2) если а в и в с, то а с;

3) если а в, то ас в;

4) если а с, в с, то (а ± в)с;

5) если а в и в а, то а = ± в;

6) если а, в - натуральные числа и ав, то а ? в;

7) если а, в - натуральные числа и а в, ва, то а=в.

Доказательство. 1) Так как а = а•1 и 1ЃёЈЪ, то аа.

2) Так как а в и в с, то существуют целые числа в? и с?, такие, что а = вЃEв?; в = с•с?. Равенства а = в* в?= ( с•с?)в? =с(с?* в?) и включение с?· в?ЃёЈЪ показывают, что ас.

Свойства 3) и 4) доказываются аналогично свойству 2).

5) Так как а в, в а, то а =в·с, в = а ·d, с, dЃёЈЪ. Отсюда а = аdс. Поскольку а ? 0, то dс = 1. Так как с, dЃёЈЪ, то либо d = с = 1, либо d = с = -1. Значит, либо а = в, либо а = -в.

6) Если а в, то а = в·с, сЃёЈЪ. Так как а, вЃёN, то сЃёN. Значит с ? 1. Тогда

а = в·с ? в·1 =в.

7) Согласно свойству 6) из условий а в, в а и а, вЃёN имеем неравенства

а ? в и в ? а. Следовательно, а =в.

Сумма, разность и произведение целых чисел сами являются целыми числами. Однако для деления целых чисел это уже не так:

Теорема 2. Для всякого целогоа и всякого натурального числав существуют и единственные целые числа q и r, такие, что а = bq + r, 0 ? r<b.

Доказательство. Существование. Возьмём наибольшее кратное в q числа в, не превосходящее а. Тогда в q ? а, но b(q + 1)>а. Обозначим r = а -bq. Ясно, что q и r - целые числа. Так как bq ? а, то 0 = bq - bq ? а - bq= r. Так как b(q + 1)>а, то b = b(q + 1) - bq>а - bq = r, и существование целых чисел qи r, требуемых в теореме 2, доказано.

Единственность. Допустим, что справедливы два равенства а = bq + r,

а = bq? + r?,где q, q?, r, r?Ѓё ЈЪи 0 ? r, r?<b.

Если r < r?, то, вычитая из первого равенства второе, получим равенство

0 = b(q - q?) + (r - r?). Перепишем его в виде: r? - r = b(q- q?). Поскольку

r?>r, то (r? - r) - целое положительное число.Так как (r? -r) b и r? - r,

bЃёN, то r?- r ? b по теореме 1. 6. Цепочка неравенств r? - r? r?<b и неравенство r?- r ? b противоречат друг другу.

По аналогичной причине не может выполняться неравенство r>r?.Следовательно, r? = r и 0 = b(q - q?). Сокращая на b, получим: q - q? = 0, т.е. q = q?.

Примеры. 1. Разделим число 367 на 7 с остатком и получим равенство

367 =7·52 + 3.

2. Разделим число -415 на 13 и получим равенство

-415 =13·(-32) + 1.

3. Разделим число 344 на 2 и получим равенство 342 =172·2 +0.

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

наибольший общий делитель и его единственность

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

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

Для общего делителя используется обозначение: d- о. д. (,,…, ).

Приведём примеры общего делителя.

1. Общим делителем чисел 21 и 7 является число 7.

2. Общими делителями чисел 100 и 48 являются числа 1, 2, 4.

Определение. Натуральное число d называется наибольшим общим делителем натуральных чисел,,…, , если выполняются два условия:

1) d - о. д. (,,…, );

2) если d' - о. д. (,,…, ), то dd'.

Для наибольшего общего делителя чисел ,,…, используется обозначение d = н.о.д. (,,…, ).

Условие 2) из определения наибольшего общего делителя и теорема 1.6. обеспечивают нам то, что среди всех общих делителей мы возьмём наибольший.

Теорема 3:Если для натуральных чисел ,,…, существует наибольший общий делитель, то он единственен.

Доказательство. Допустим, что у чисел ,,…, существует два наибольших общих делителя d?и d?. Так как d? = н.о.д. (,,…, ), а d? -

о.д. (,,…, ), то d?d?. По аналогичной причине d?d?. Согласно теореме 1.7. имеем равенство d?= d?. Поскольку у натуральных чисел,,…, может быть несколько общих делителей, а наибольший общий делитель только один, то обозначения для общих делителей и наибольшего общего делителя оправданны.

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

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

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

Лемма 1. Если для натуральных чисел а, b выполняется условие а b, то н.о.д. (а,b) = b.

Доказательство. Так как аb и bb, то b - о.д. (а, b). Если d' - о.д. (а, b), то аd' и bd'. Для натурального числа b выполняютсявсе условия из определения н.о.д. (а,b). Значит b=н.о.д. (а, b).

Лемма 2. Если для натуральных чисел а, в выполняется равенство

а = bq + r, где q, r ЃёЈЪ и r>0, то н.о.д. (а, b) = н.о.д. (b, r).

Доказательство. Пусть d? = н.о.д. (а, b), d?= н.о.д. (b, r). Так как

d? - о.д. (а, b), то аd? и bd?, тогда r = (а - bq)d?, следовательно,

d? - о.д. (b, r). Так какd?= н.о.д. (b, r), то d?d?. По аналогичной причине

d?d?. Согласно теореме 1.7. справедливо равенство d? = d?.

Пусть теперь а, b - произвольные, натуральные числа. По теореме о делении с остатком можем записать:

a = bq? + r?, q?, r?ЃёЈЪ, 0<r?<b,

b= r?q?+ r?, q?, r?ЃёЈЪ, 0 <r?<r? (1)

= + , , ЃёЈЪ, 0<<,

= ,ЃёЈЪ.

Этот процесс называется алгоритмом Евклида. Заметим, что мы записали в последнем равенстве остаток, равный нулю.

Теорема 4. Наибольший общий делитель двух произвольных натуральных чисел равен последнему, отличному от нуля остатку, в алгоритме Евклида. Доказательство. Так как b >>…>>0, то не позднее чем через b шагов произойдёт деление нацело, как мы и записали в последнем равенстве алгоритма Евклида.

Поскольку а = b+ ,b = q?+ r?,…, = + ,=

то, согласно лемме 2 и лемме 1, справедливы равенства:

н.о.д. (а, b) = н.о.д. (b, r?) = … = н.о.д. (, ) = , и теорема 4 доказана.

Пример. Найдём н.о.д (1378, 24). Применим к числам 1378 и 24 алгоритм Евклида и получим равенства

1378 = 24 · 57 + 10,

24 = 10 · 2 + 4,

10 = 4 · 2 + 2,

4 = 2 · 2 + 0.

Так как наибольший общий делитель двух натуральных чисел равен последнему, отличному от нуля, остатку в алгоритме Евклида, то н.о.д. (1378, 24) = 2.

1.3 Свойства наибольшего общего делителядвух натуральных чисел

Теорема 5. Для любых трёх натуральных чисела, b, с справедливо равенство н.о.д. (ас, bс) = с · н.о.д. (а, b).

Доказательство. Умножим все равенства и неравенства в алгоритме Евклида (1) для чисел а, b на целое положительное число с и получим алгоритм Евклида для чисел ас, bс:

ас = bс · q? + r?c, q?, r?cєЈЪ, 0 <r?c<bc,

bс =r?с · q? + r?c, q?, r?cєЈЪ, 0 <r?c<r?c,

с =с · +c, ,c єЈЪ, 0 ? c <c,

с =с · , є ЈЪ.

Согласно теореме 4 справедливо равенство н.о.д. (ас, bс) = с =с · н.о.д. (а, b).

Теорема 6. Для любых натуральных чисела, в существуют такие целые u, v, что au + bv= н.о.д. (a, b).

Доказательство. Проведём индукцией по числу делений в алгоритме Евклида для чисел a, b. Если деление только одно, то a = bq?, q?єЈЪ. Тогда

a b и по лемме 1 н.о.д. (a, b) = b. Равенство a·0 + b·1 = b показывает, что можно взять u = 0, v = 1. Допустим, что целые u, vможно найти для любой пары натуральных чисел, для которой в алгоритме Евклида требуется n делений. Поскольку для натуральных чисел b, r? в алгоритме Евклида (1) требуется n делений и поскольку согласно теореме 4 справедливо равенство н.о.д. (b, r?) =, то по индукционному предположению существуют такие целые u?, v?, что bu? + r?v? = . Используя равенство r? = a - bq?, можно записать bu? + r?v? = bu?+(a - bq?) v?= a v?+ b(u? - q?v?) = = н.о.д. (a, b). Полагая,u = v? и v = u? - q?v? и получим требуемое равенство au + bv == н.о.д. (a, b).

Равенство из теоремы 6 очень полезно и в теории, и на практике. Кроме того, его аналог справедлив и для многочленов. Поэтому его называют не равенством, а тождеством Безу.

Используя тождество Безу, легко доказывается следующая теорема.

Теорема 7. Если произведение ab натуральных чисел a, b делится на натуральное число c и н.о.д. (a, c) = 1, то b c.

Доказательство. Поскольку н.о.д. (a, c) = 1, то согласно теореме 6, существуют такие целые u, v, что au + сv = 1. Умножая это равенство на b, получим abu + сbv = b. Так как ab c, c c, то abu и сbv делятся на c и, значит, b c.

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

Пример. Используя результаты пункта 2.3 можем записать равенства н.о.д. (18, -34) = н.о.д. (18, 34) = 2 · н.о.д. (9, 17) = 2 · 1 = 2.

1.4 Алгоритм Евклида для трёх и более натуральных чисел

Для трёх и более натуральных чисел справедливы аналоги лемм 1 и 2, которые позволяют распространить алгоритм Евклида на три и более натуральных числа.

Лемма 3. Если для натуральных чисел a, b, c справедливы условия a c,

b c, тон.о.д. (a, b, c) = c.

Доказательство. Так как a c, b c и c c, то c - о.д. (a, b, c). Пусть

d' - о.д. (a, b, c). Тогда a d', b d', c d'. Значит, для числа c выполняются все условия из определения н.о.д. (a, b, c). Поэтому c = н.о.д. (a, b, c).

Лемма 4. Если для натуральных чисел a, b, c справедливы равенства

a = cq? + r?, b = cq? + r?,

где q?, q?, r?, r? єЈЪ и 0 ? r?, r?<b, то н.о.д. (a, b, c) = н.о.д. (c, r?, r?).

Доказательство. Пусть d? = н.о.д. (a, b, c), d? = н.о.д. (c, r?, r?). Тогда

d? - о.д. (a, b, c)иad?, bd?, cd?. Посколькуr? = a - cq?, r? = b-cq?, то

r?d?, r?d?. Значитd? - о.д. (c, r?, r?). Посколькуd? = н.о.д. (c, r?, r?), то

d? d?. По аналогичной причине d? d?. Согласно теореме 1.7, справедливо равенство d?= d?.

Мы не будем формулировать соответствующие утверждения, а проясним алгоритм Евклида для трёх натуральных чисел примером вычисления

н.о.д. (294, 570, 135). Поскольку 570 = 135·4+30, 294 = 135·2+24, то

н.о.д. (294, 570, 135) = н.о.д. (135, 30, 24). Поскольку 135 = 24·5+15,

30 = 24·1+6, то н.о.д.(135, 30, 24) = н.о.д. (24, 15, 6). Поскольку 24 = 6·4,

15 = 6·2+3, то н.о.д. (24, 15, 6) = н.о.д. (0, 3, 6). Поскольку 0 = 3·0, 6 = 3·2, то н.о.д. (0, 3, 6) = 3.

Найдём н.о.д.(75; -250; - 435). Мы уже отмечали, что

н.о.д. (75; -250; - 435) = н.о.д. (75; 250; 435). Поскольку 435 = 75·3+60, 250=75·3+25, то н.о.д. (75; 250; 435) = н.о.д. (75, 60, 25). Поскольку

75 = 25·3+0 и 60 = 25·2+10, то н.о.д. (75, 60, 25) = н.о.д. (25, 10, 0) =

н.о.д. (25, 10). Поскольку 25 = 10 · 2 + 5, 10 = 5 · 2 + 0, то н.о.д. (25, 10) = 5.

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

Теорема 8. Для любых натуральных чисел a, b, c справедливо равенство

н.о.д. (a, b, c) = н.о.д. ( н.о.д. (a, b), c).

Доказательство. Обозначим через d = н.о.д. (a, b, c), d?= н.о.д. (a, b) и

d? = н.о.д. (d?, c). Поскольку d = н.о.д. (a, b, c), то a d, b d, c d. Значит,

d - о.д. (a, b). Так как d? = н.о.д. (a, b),то d? d. Значит, d - о.д. (d?, c). Так какd? = н.о.д. (d?, c), то d? d.

Поскольку d? = н.о.д. (d?, c), то d?d?и c d?. Поскольку d? = н.о.д. (a, b),то

a d? и b d?. Так как a d? и b d? и d? d?, то a d? и b d?,согласно теореме 1.2. Следовательно, d? - о.д. (a, b, c). Поскольку d = н.о.д. (a, b, c), то d d?.

Из условий d? d и d d? согласно теореме 1.7 получаем требуемое равенство d = d?.

Пример. Найдём н.о.д. (570, 294, 135), используя теорему 8. По теореме 8 можем записать н.о.д. (570, 294, 135) = н.о.д. (н.о.д. (570, 294), 135). Применим к числам 570 и 294 алгоритм Евклида

570 = 294·1+276

294 = 276·1+18

276 = 18·15+6

18 = 6·3 +0 и получим, что (570, 294) = 6. Применим к числам 135 и 6 алгоритм Евклида

135 = 6 · 22 + 3

6 = 3 · 2 + 0

И получим, что н.о.д. (135, 6) = 3. Следовательно н.о.д. (570, 294, 135) = 3.

алгоритм Евклида в приложениях

1.5 Наименьшее общее кратное

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

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

Определение. Натуральное число m называется общим кратным натуральных чисел,,…, , еслиmа?, mа?, …, m.

Общее кратное m чисел ,,…, обозначается следующим образом m - о.к. (,,…,

Определение. Натуральное число m называется наименьшим общим кратным натуральных чисел а?, а?,…, аk, если выполняются два условия:

1. m- о.к. (,,…, );

2. если m' - о.к. (,,…, ), то m' m.

Для наименьшего общего кратного используется обозначение

m=н.о.к. (а?, а?,…, аk).

Условие 2 из определения наименьшего общего кратного и теорема 1.6 обеспечивают нам, что среди всех общих кратных мы возьмём наименьшее.

Как и для наибольшего общего делителя докажем теорему.

Теорема 9. Если для натуральных чисел ,,…, существует наименьшее общее кратное, то оно единственное.

Доказательство. Пусть m? = н.о.к. (,,…, ) и m? = н.о.к. (,,…, ). Так как m?= н.о.к. (,,…, ), а m? -о.к. (,,…, ), то m?m?. По аналогичной причине m?m?. Согласно теореме 1.7, имеем равенство

m? = m?.

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

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

Теорема 10. Для любых двух натуральных чисел a, b справедливо равенство н.о.к. (a, b) =

Доказательство. Пусть d =н.о.д. (a, b), тогда ad, bd и a = da?, b = db?, где a?, b?? N. Согласно теореме 5, справедливы равенства d = н.о.д. (a, b) = =н.о.д. (da?, db?) = d · н.о.д. (a?, b?), откуда следует, что н.о.д. (a?, b?) = 1. Пустьm = . Так как m = = m = = a?b = = ab?, то ma и mb, т.е. m - о.к. (a, b). Пусть m' - о.к. (a, b), тогда m' a и m' b. С учётом первого условия можем записать m' = a · c, для некоторого c из N. Поскольку m' b, т.е. a?dcdb?, то a?c b?. Согласно теореме 7 из условий a?c b? и

н.о.д. (a?, b?) = 1, получаем, что c b?, т.е. c = b?c?, c?? N. В итоге можем записать, что m' = a?db?· c? = mc?. Значит, m' m и для натурального числа m выполняются оба условия из определения наименьшего общего кратного.

Пример. Найдём наименьшее общее кратное чисел 468 и 252.

Согласно теореме 10, наименьшее общее кратное двух чисел равно частному от деления их произведения на их наибольший общий делитель. Значит н.о.к. (468, 252) = (468·252)/36 = 468·7 = 3276.

1.6 Нахождение наименьшего общего кратного трёх и более натуральных чисел

Для наименьшего общего кратного трёх чисел справедлив аналог теоремы 8.

Теорема 11. Для любых натуральных чисел a, b, c справедливо равенство н.о.к.(a, b, c) = н.о.к. (н.о.к. (a, b), с).

Доказательство. Обозначим m = н.о.к. (a, b, c), m? = н.о.к. (a, b), m?= н.о.к. (m?, с). Поскольку m = н.о.к. (a, b, c), то ma, mb, mс и, значит,

m- о.к. (a, b). Поскольку m?= н.о.к. (a, b), то mm?. Значит m- о.к. (m?, с). Поскольку m?= н.о.к. (m?, с), то mm?.

Так как m? = н.о.к. (m?, с), то m?m? и m? с.

Поскольку m? = н.о.к. (a, b), то m?a и m?b. Поскольку m?m? и m?a,m?b, то m?a,m?b. Значит m? - о.к. (a, b, c). Так как m = н.о.к. (a, b, c), то m?m. С учётом теоремы 1.7 получаем требуемое равенство m = m?.

Пример. Найдём наименьшее общее кратное чисел 468, 252 и 40.

Так как н.о.к.(a, b, c) = н.о.к. (н.о.к. (a, b), с), то сначала нам нужно найти н.о.к. (468, 252). Из предыдущего примера мы знаем, что

н.о.к. (468, 252) = 3276. По алгоритму Евклида находим, что

н.о.д. (3276, 40) = 4. По формуле из теоремы 10 находим, что

н.о.к.(a, b, c) = н.о.к. (3276, 40) = = 32760.

Аналог теоремы 11справелив для четырёх и более натуральных чисел.

1.7 Решение диофантова уравнения первой степени

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

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

Рассмотрим, например, такую задачу.

На чашечных весах продавцу надо отвесить 1700 грамм конфет. Имеются гири по 200 и 500 грамм. Сколькими способами продавец может это сделать? Для ответа на этот вопрос достаточно решить уравнение 200х +500у = 1700 с двумя неизвестными х и у. Такие уравнения имеют бесконечное множество действительных решений. В частности, полученному уравнению удовлетворяет любая пара действительных чисел вида (x; ), xє R. Но для нашей практической задачи годятся только целые неотрицательные значения х и у. Поэтому приходим к постановке такой задачи.

Найти все целые неотрицательные решения уравнения 2х +5у = 17.

Ответ содержит уже не бесконечно много, а всего лишь две пары чисел (1;3) и (6; 1).

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

Теорема 12. Пусть ax + by = c - диофантово уравнение первой степени и

d = н.о.д. (a, b). Тогда

1) если cd, то диофантово уравнение ax + by = c не имеет целочисленных решений;

2) если cd, то диофантово уравнение имеет бесконечно много целочисленных решений, которые находятся по формулам x = x?+ ,

y = y?- ,

где t -произвольное целое число, а x?, y?- какое-то частное решение диофантова уравнения ax + by = c.

Доказательство. Так как d = н.о.д. (a, b), то ad, bd, т.е. a = da?, b = db?,

a?, b?єЈЪ. Согласно теореме 5, можем записать цепочку равенств

d = н.о.д. (a, b) = н.о.д. (da?, db?) = d·н.о.д. (a?, b?). Откуда, сокращая на d, получаем равенство н.о.д. (a?, b?) = 1.

Если c d и x?, y?- целочисленное решение диофантова уравнения, то справедливо равенство ax?+ by? = c или da?x? + db?y?= c. Тогда cd согласно теореме 1.4, что противоречит условию.

Пусть теперь cd, т.е. c = dc?, c?єЈЪ. Тогда обе части диофантова уравнения ax + by = c можно сократить на d и получить равносильное диофантово уравнение a?x+ b?y = c? с условием н.о.д. (a?, b?) = 1. Согласно теореме 6, существуют такие целые u, v, что a?u+ b?v = 1. Умножая это равенство на dc?, получим равенство da?(uc?) + db?(vc?) = dc?, которое показывает, что uc?, vc? - целочисленное решение диофантова уравнения

ax + by = c, т.е. в этом случае диофантово уравнение имеет целочисленные решения.

Пусть x?, y?- одно из этих решений (частное решение) диофантова уравнения ax + by = c. Вычисления ax + by = a(x? + ) + b(y? - ) =

ax?+ by? +da?b?t - d?a?t = ax?+ by? = cпоказывают, что, имея одно частное решение диофантова уравнения ax + by = c, при помощи формул из теоремы 12, мы можем получить бесконечно много целочисленных решений этого уравнения.

Возьмём произвольное решение x?, y? диофантова уравнения ax + by = c и покажем, что оно задаётся формулами из теоремы 12. Так как x?, y? и x?, y? - решения уравнения ax + by = c, то справедливы равенства ax? + by? = c и

ax?+ by? = c. Вычитая из первого равенства второе, получим

a(x? - x?) + b(y? - y?)=0, откудаa(x? - x?) =b(y? - y?), или da?(x? - x?) =

=db?(y? - y?) и значит a?(x? - x?) = b?(y? - y?). Поскольку a?(x? - x?)b? и

н.о.д. (a?, b?) = 1, то (x? - x?)b?, согласно теореме 7, т.е. x? - x? = b?t, tєЈЪ. Значит x? = x?+ b?t = x? + ,tєЈЪ. Подставляя это выражение в равенство a?(x? - x?) = b?(y? - y?), получим b?(y? - y?)= a?(x?+ b?t - x?) = a?b?t. Откуда y? - y?= a?t или y?= y?- a?t = y?- ,tєЈЪ. Мы видим, что произвольное целочисленное решение диофантова уравнения ax + by = c действительно задаётся формулами из теоремы 12.

Пример. Решим в целых числах диофантово уравнение 54х + 37у= 3.

Применяя к числам 54, 37 алгоритмЕвклида:

54=371+17,

37 = 172+3,

17 = 35+2,

3 = 21+1,

2 = 1·2 + 0.

Получим, что н.о.д. (54, 37) = 1. Поскольку 31, то, согласно теореме 12, диофантово уравнение имеет бесконечно много целочисленных решений. Чтобы задать эти решения формулами, надо знать хотя бы одно частное решение диофантова уравнения.

Найдём тождество Безу, выражая остатки из равенств алгоритма Евклида и подставляя их поочерёдно, начиная снизу, в выражение для последнего ненулевого остатка:

1 = 3 - 2·1 =3 - (17-35)·1 = 17· (-1) + 36 = 17·(-1) + (37- 172) 6 =

376+17(-13) = 376 + (54- 371) (- 13) = 54(- 13) + 3719.

Умножая тождество Безу 54(- 13) + 3719 = 1 на 3, получим тождество

54·(-39) + 37 · 57 = 3, которое показывает, что x?= -39, y? = 57 являются частным решением диофантова уравнения 54х + 37у= 3.

Согласно теореме 12, все решения диофантова уравнения задаются формулами

x = -39 += -39 + 37t

y= 57 -= 57 - 54t,tєЈЪ.

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

оценка Ламе количества делений в алгоритме Евклида

Приведём оценку количества делений в алгоритме Евклида, полученную Ламе в 1845 году.

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

Доказательство. Пусть a; b- натуральные числа, причём b ? a и натуральное число b записывается m цифрами в десятичной системе счисления. Покажем, что алгоритм Евклида, применённый к числам a, b, выполнит не более 5m делений с остатком.

Пусть r?=a,r?=b,аr?,…, - последовательность всех нулевых остатков в алгоритме Евклида. Тогда=+, 0?<, i=1,2,…,n-1и

=н.о.д. (a,b). Методом математической индукции докажем справедливость неравенств ?лi, где , i=1,2,…,n-1.

Так как и- натуральные числа, удовлетворяющие неравенству

<, то при i=1 справедливы неравенства ? +1?2?л и основание индукции установлено. Допустим, что неравенство ?лi установлено для всех i=1,2,…,k и докажем его для i=k+1. Поскольку л- корень уравнения xІ - x - 1 = 0, то с учётом индукционного предположения справедливы следующие выкладки =+?+?лk+лk-1=лk+1и индукционный переход выполнен.

Поскольку 10m>b и b=r1 ? лn-1, то с учётом неравенства л>101/5?1,58 получаем неравенстваm > (n-1)lgл >. Откуда уже получается требуемая оценка n < 5m+1.

другая оценка количества делений в алгоритме Евклида

Приведём другую оценку количества делений в алгоритме Евклида и сравним её с оценкой Ламе. Материалы этого пункта мне сообщил Сосновский Ю. В.

Лемма 5. Пусть для натуральных чисел a,b справедливы равенства

a = bq? + r?

b = r?q?+ r?, где q?, q?, r?, r? ЃёN и b>r?>r?> 0. Тогда b>2r?.

Доказательство. Пусть r?<. Тогда b>2r? и лемма 5 доказана. Пусть поэтому r? ?. Тогда r? >r? ?. Цепочка равенств и неравенств b = r?q?+ r? ? r? + r? >+=b приводит к противоречию, значит случай r? ? невозможен.

Теорема 14. Количество делений с остатком в алгоритме Евклида, необходимое для вычисления наибольшего общего делителя натуральных чисел a,b, где b<a, не превосходит 2 log?b + 1.

Доказательство применим к натуральным числам a,b алгоритм Евклида и получим:

a = bq? + r?,

b = r?q?+ r?,

r?=r?q?+ r?,

r?=r?q?+ r?,

=+ ,

=,

где r?, r?,…, rn-1 и q?, q?, …, qn - натуральные числа, причём b>r?>r?>rn-1 >0.

Допустим, что число n-1чётное. Согласно лемме 5 справедливы неравенства b>2r?>2Іr?>…>. Логарифмируя это неравенство, получим log?b>log?= log?+log?. Поскольку- натуральное число, то log?b> и значит n< 2log?b+1.

Теперь предположим, что число n -2 является чётным. Согласно предыдущему, справедливо неравенство log?b>+log?. Поскольку = и - натуральное число, большее 1, то ? 2. Поэтому можем записать log?b>+ 1 = log?b>и значитn<2log?b +1.

Глава 2. Факультатив «Алгоритм Евклида для целых чисел»

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

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

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

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

Нам стало интересно, каким способом ведётся нахождение наибольшего общего делителя и наименьшего общего кратного в школьном курсе математики. Для этого были просмотрены учебники математики Н. Я. Виленкина, Л. Г. Петерсон, С. М. Никольского, И. Ф. Шарыгина, И. М. Зубаревой и других авторов.

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

для нахождения н.о.д. (325, 250) разложим числа 325 и 250 в произведение простых чисел

325 5 250 5

65 5 50 5

13 13 10 5

1 2 2

1

и получим 325 = 5 ·5 · 13, 250 = 5 ·5 ·5 · 2. Зная разложение чисел 325 и 250 на простые множители, легко находим, что н.о.д. (325, 250) = 25.

Хотя жизнь не стоит на месте и школьное образование в целом далеко ушло вперёд, однако классические школьные учебники А. П. Киселёва конца XIX - первой трети XX веков остаются непревзойдёнными по полноте, доступности и строгости изложения материала. В «Систематическом курсе арифметики» А. П. Киселёва 1902 года издания приводятся оба способа вычисления наибольшего общего делителя, причём для обоснования алгоритма Евклида фактически используются леммы 1 и 2 из §2 главы I. Для подтверждения этих слов процитируем А. П. Киселёва:

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

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

Этот способ рассмотрен нами выше.

Второй способ: нахождение общего наибольшего делителя посредством последовательного деления.

Этот способ, применяемый к двум числам, основан на следующих двух утверждениях:

1. Если большее из двух данных чисел делится на меньшее, то меньшее из них есть общий наибольший делитель.

Пример. Возьмём два числа: 54 и 18, из которых большее делится на меньшее. Так как 54 делится на 18 и 18 делится на 18, то 18 - общий делитель чисел 54 и 18. Этот делитель является в то же время и наибольшим, потому что 18 не может делиться на число, большее 18.

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

Отметим, что для разложения чисел на простые множители желательно иметь под руками таблицу простых чисел на достаточно большом промежутке, например, на промежутке [1; 1000], как в современных школьных учебниках или на промежутке [1; 6000], такая таблица приводится у Киселёва. И даже при наличии этой таблицы процесс разложения на простые множители всё равно остаётся очень трудоёмким. А без таблицы отношение количества делений с остатком в алгоритме Евклида и в алгоритме разложения на простые множители приблизительно равно . Используя в факультативе оба алгоритма, мы надеемся, что на числах, больших тысячи, ученики почувствуют эту разницу.

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

программа факультатива «Алгоритм Евклида для целых чисел»

Пояснительная записка

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

Занятия проводятся в форме лекций, семинаров, практикумов по решению задач, конференций.

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

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

...