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

Старт в науке

НОД ЦЕЛЫХ ЧИСЕЛ. АЛГОРИТМ ЕВКЛИДА

• Авторы
• Файлы работы
• Наградные документы

Шмакова А.Э. 1

---

1МОУ "СОШ №6 города Коряжмы"

Работа в формате PDF

457.5 KB

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

Диплом школьника

Введение 3

§1. Делимость целых чисел 5

§2. Наибольший общий делитель 6

§3. Алгоритм Евклида 7

§4. Теорема о линейном представлении наибольшего общего делителя 8

§5. Взаимно простые числа 9

§6. Диафантовы уравнения первой степени 9

§7. Примеры задач на делимость и алгоритм Евклида 10

§8. Исследование 11

Заключение 12

Список использованной литературы 13

Приложение 1 Задачи и упражнения по математике и информатике 15

Задачи и упражнения по математике 15

Задачи ЕГЭ по информатике на использование алгоритма Евклида 18

Приложение 2 Исследование 21

Результаты исследования 22

Тема «Делимость целых чисел» считается одной из наиболее важных тем в курсе школьной математики. Такие понятия как делимость целых чисел, НОД, простые и составные числа рассматриваются в начальной школе, среднем звене и в профильных классах старшей школы. Но сведения, которые мы получили, в основном только формулировки, без доказательств, следствий и некоторых теорем. Данная работа предполагает сформулировать теоретические подходы к темам: «Делимость целых чисел», «НОД целых чисел», «Алгоритм Евклида» и применение алгоритма Евклида. В этой работе я сформулирую основные леммы, теоремы, их следствия, связанные с данной темой. Особое место уделю методам решения задач, которые опираются на теоретический материал. В работе приведу примеры задач, которые встречались на математических олимпиадах разного уровня, а также на ЕГЭ в разделе самого сложного задания. Обращаем внимание, что с такими заданиями ученик может справиться, если владеет знаниями по теории указанной темы. Для написания данной исследовательской работы я изучила учебники по математике для 5 и 6 классов под редакцией Л. Г. Петерсона [8, 9], учебники алгебры для классов с углубленным изучением математики под редакцией Н. Я. Виленкина [2, 3]. Теорию по данной теме я изучала в учебных пособиях для студентов высших учебных заведений, например,в учебном пособии «Делимость целых чисел» для классов с углубленным изучением математики и студентов ВУЗов, автором которого является преподаватель Сыктывкарского государственного университета Яковлев Владимир Дмитриевич [12].

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

Актуальность темы: Понятие делимости целых чисел, наибольший общий делитель (НОД) чисел, Алгоритм Евклида встречаются на математических олимпиадах разного уровня по математике и информатике, а также на ЕГЭ в разделе самого сложного задания. В частности, Алгоритм Евклида является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также алгоритм используется при решении диафантовых уравнений, при построении непрерывных дробей, в методе Штурма и т.д. [14]

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

Задачи исследования:

1. Изучить литературу по данной теме (теоретический подход).

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

3. Составить на компьютере программу для нахождения делителей числа и программу алгоритм Евклида.

4. Исследовать результативность программ для нахождения делителей числа и алгоритма Евклида.

5. Сформулировать выводы исходя из результатов исследования.

Предмет: Алгоритм Евклида.

Объект:Способы нахождения наибольшего общего делителя.

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

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

Множество целых чисел принято обозначать буквой Z. Множество Z состоит из натуральных чисел N = {1,2,3,4,…}, числа 0 и множества целых отрицательных чисел {-1, -2,-3,…}.

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

Определение. Будем говорить, что целое число делится на целое число , если найдется такое целое число , что . Например, 111 делится на 3, т.к. 111= 337; делится на –7, так как 21 = (-7)(-3).

Для обозначения делимости на пользуются записью или . В последнем случае также говорят: “b делит a”, “b – делитель a” или “a кратно b”.

Рассмотрим некоторые простейшие свойства.

1. Число 0 делится на любое целое b, поскольку 0=, а 0 – целое число.

2. Любое целое число a делится на 1, -1, a, -a, так как и числа 1, -1, a и (-а) – целые.

3. На 0 делится только 0. В самом деле, если некоторое целое a делится на 0, то найдется такое целое число с, что , последнее же равенство выполняется лишь при.

Отметим, что поскольку равенство выполняется для произвольного числа c, то хоть 0 делится на 0, частное, тем не менее, не определено.

Теорема 1. Пусть и  целые числа.и, то и .

Доказательство. Поскольку целые числа делятся на b, то найдутся такие целые , что . Тогда и . Но сумма и разность чисел m₁ и m₂ – целое число, следовательно, и .

Замечание. Теорема легко обобщается на случай n чисел, а именно: если целые числа делятся на b, то их сумма и разность также делятся на b.

Теорема 2. Пусть a делится на b. Тогда для любого целого k число также делится на b. (Приложение 1, упражнение 1)[2, 3, 6, 7, 8, 9]

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

Аналогично определяется наибольший общий делитель в случае большего количества чисел. Приведем несколько примеров. Так, наибольший делитель чисел 10 и -8 равен 2, чисел 0 и 4 равен 4, а чисел 2 и 7 равен 1. Наибольший общий делитель чисел 15,18,30 равен 3.Наибольший общий делитель чисел a и b обозначается НОД(a;b) или просто (а,b).

Перечислим некоторые простейшие свойства.

1. Для любого целого числа a(а, 1) = 1.

2. Для любого натурального числа а(а,0) = а

3. Пусть целое число bделится на а, причем a натуральное число. Тогда (a, b) = а.

Введем далее некоторые обозначения.

Пусть D_a– множество всех делителей числа a, D_a,b=D_aDb, – множество всех общих делителей чисел а и b. Тогда, для нахождения чисел a и b достаточно найти максимальный элемент множества D_a,b

Например, пустьа= 6, b = 8. Тогда D₆ = {±1, ±2, ±3, ±6}, D₈ = {±1,±2,±4,±8}, D_a,b= {±1,±2}. Следовательно, (8,6) = 2.(Приложение 1, упражнение 2)[2, 6, 12]

Теорема 1. Пусть а и b– целыечисла, b> 0. Тогда, если а=bq+ r, где q– целое число, а 0 ≤ rr₂>r₃>….>r_n-1>rn, то найдется такое n, что r_n+1=0. Тем самым, процесс давления с остатком на n-ом шаге заканчивается, в результате чего получили данную систему.

Теорема 2.Последний нулевой остаток rn в системе (*) есть наибольший общий делитель a и b.

Доказательство. Согласно теореме 1 имеем:.Но, согласно последнему равенству в системе (*),число rn_-1делится на rn,следовательно, каждый общий делитель чиселrn_-1и rn есть делитель rn, т.е. . Таким образом, , поэтому .

Следствие 1.Пусть a и b – целые числа, d=(a,b). Тогда множество общих делителей чисел a и b совпадает с множеством делителей числа d, то есть .

Следствие 3. Если d=(a,b), то .

(Приложение 1, упражнения 3, 4, 5, 6, 7)[12]

Пусть даны целые числа a и b, из которых, по крайней мере, одно отлично от нуля. Рассмотрим далее множество всех целых чисел вида ax+by, где x и y – произвольные целые числа, обозначим это множество буквой А. А={ax+by, где x, y}.

Так как , то числа a, bA. Аналогично, -a, -bA. Кроме того, .

Лемма. Если целые числа v,uA, причем v>0, то остаток от деления числа u на v также принадлежит множеству A.

Теорема. Пусть а и b – целые числа, причем, по крайней мере, одно из них не равно нулю; A={ax+by, где х, у Z}. Тогда наименьшее положительное число множества А равно наибольшему общему делителю чисел a и b.

Следствие. Множество А состоит из тех и только тех целых чисел, которые делятся на d=(a,b).(Приложение 1, упражнение 8) [6, 12]

Целые числа a и b называются взаимно простыми, если их наибольший общий делитель равен 1. Целые числа a₁, a₂, a₃, .., an называются взаимно простыми, если (a₁, a₂, a₃, .. ,an) = 1, и попарно взаимно простыми, если для всех i ≠ j числа a_i и a_j взаимно простые.

Отметим, что если d=(a,b), то и числа и взаимно простые.

Лемма. Для того, чтобы числа a и b были взаимно простыми, необходимо и достаточно, чтобы для некоторых целых чисел х₀, у₀ выполнялось равенство ax₀+bx₀=1.

Рассмотрим уравнение ax+by=c, где a, b, c – целые числа, хотя бы одно из чисел a и b отлично от нуля. Поставим следующую задачу: найти все пары целых чисел x иy, удовлетворяющих данному уравнению. Заметим, что такого рода уравнения, в которых требуется найти все целые решения, обычно называются диафантовыми уравнениями.

Итак, пусть дано уравнение ax + by = c. Рассмотрим . Тогда , где числа a₁ и b₁ взаимно простые. В этом случае исходное уравнение имеет вид . Теперь если данное уравнение имеет решение в целых числах и, то c делится наd, в противном случае уравнение в целых числах решений не имеет. Если же , где c₁–целоечисло, то исходное уравнение сводится к уравнению , где =1.Таким образом, задача свелась к решению при взаимно простых и .

Теорема. Уравнение , где целые числа, причем , имеет решение в целых числах. При этом, если пара целых чисел удовлетворяют данному условию, то все остальные решения уравнения задаются равенствами .

Доказательство (Приложение). (Приложение 1, упражнения 9, 10, 11, 12, 13)

1. Найти НОД (763, 337).

Решение: 3;

. НОД (763, 337)=1. Ответ: 1.

1. Для каждого натурального n найдите НОД (2n+1; 9n+4).

Решение: НОД (2n+1; 9n+4)=НОД (9n+4;2n+1)=НОД (2n+1; n)=НОД (n;1)=1.Ответ: 1.

1. Решите систему .

Решение: НОД(x;y)=30; тогда Рассмотрим

или ; или .

Ответ:

1. Найдите все натуральные n, при которых дробь сократима.

Решение: Пусть ,

тогда .

Если d=1, то дробь несократима.

Пусть d=5, тогда

Ответ: дробь сократима при

1. Решить уравнение в целых числах: .

Решение: Заметим, что НОД (5;3)=1. .

Тогда

1. Решить уравнение в целых числах .

Решение: Заметим, что НОД(71, 109)=1. Рассмотрим уравнение . Частное решение последнего уравнения .

Умножим обе части последнего равенства на 20:

; .

Тогда общее решение.

Мною совместно с одноклассницей Кристиной Свиридовой под руководством учителя информатики былисоставлены блок-схемы (Приложение 2, рис. 1, рис. 2) и компьютерные программы в среде КуМир Делители числа и Алгоритм Евклида (Приложение 2,рис. 3, рис. 4), которые мы использовали для проведения бинарного урока математики-информатики по теме «Алгоритм Евклида» в своем 7б классе с углубленным изучением математики в 2013‑2014 учебном году.

На уроке было предложено ученикам: 1) провести вычисления для нахождения НОД чисел письменно с использованием известного им алгоритма с разложением на множители и с использованием алгоритма Евклида; 2) найти делители предложенных чисел с помощью программы Делители числа, найти НОД чисел и подсчитать суммарное количество операций, произведенных компьютером для нахождения всех делителей двух чисел; 3) провести проверку своих вычислений с помощью компьютерной программы Алгоритм Евклида, узнать количество операций для нахождения НОД двух чисел.

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

Таким образом, мы доказали нашу гипотезу о том, что Алгоритм Евклида позволяет быстрее и за меньшее число шагов находить НОД двух чисел с помощью компьютера, т.е. является более эффективным способом нахождения НОД.

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

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

1. Н. Б. Алфутова, А.В. Устинов. Алгебра и теория чисел. Сборник задач для математической школы – М.: МЦНМО, 2002.

2. Н. Я. Виленкин, С. Г. Сурвилло, А. С. Симонов, А. И. Кудрявцев. Алгебра : учеб. для учащихся 8кл. с углубл. изучением математики / под ред. Н. Я. Виленкина. – 8-е изд. – М. : Просвещение, 2007.

3. Н. Я. Виленкин, С. Г. Сурвилло, А. С. Симонов, А. И. Кудрявцев. Алгебра : учеб. для учащихся 9 кл. с углубл. изучением математики /под ред. Н. Я. Виленкина. – 8-е изд. –М. : Просвещение, 2007. – 367 с.: ил. – ISBN 978-5-09-017285-1.

4. М. Л. Галицкий, А. М. Гольдман, Л. И. Звавич. Сборник задач по алгебре: Учеб.пособие для 8-9кл. с углубл. изучением математики. 7-е изд. – М.: Просвещение, 2001. – 271 с.: ил. – ISBN 5-09-010227-9.

5. С. С. Крылов, Т. Е. Чуркина. ЕГЭ. Информатика и ИКТ : типовые экзаменационные варианты : 10 вариантов. – М. : Издательство «Национальное образование», 2016. – 192 с. – (ЕГЭ. ФИПИ – школе).

6. Ю. Н. Макарычев, Н. Г. Миндюк. Алгебра: Доп. главы к шк. учеб. 8кл. с углубл. изуч. математики. Под ред. Г.В. Дорофеева. – М.: Просвещение, 1996.

7. Ю. Н. Макарычев, Н. Г. Миндюк. Алгебра: Доп. главы к шк. учеб. 9кл. с углубл. изуч. математики. Под ред. Г. В. Дорофеева. – М.: Просвещение, 1997.

8. Л. Г. Петерсон, Г. В. Дорофеев. Математика. 5 класс. Ч.1,2, 3. – М.: Баллас. С-Инфо, 1998, 1999, 2000, 2003.

9. Л. Г. Петерсон, Г. В. Дорофеев. Математика. 6 класс. Ч.1, 2, 3. – М.: Баллас. С-Инфо, 1998, 1999, 2000, 2003.

10. И. Г. Семакин, Л. А. Залогова, С. В. Русаков, Л. В. Шестакова. Информатика и ИКТ : учебник для 9 класса. 5-е изд. – М. : БИНОМ. Лаборатория знаний, 2012. – 341 с. : ил.

11. И. Ф. Шарыгин. Факультативный курс по математике: Решение задач: Учеб. пособие для 7-9кл. сред. шк. /– М.: Просвещение, 1991.

12. В.Д. Яковлев. Делимость целых чисел. – г. Сыктывкар.

13. https://ru.wikipedia.org/wiki/%C5%E2%EA%EB%E8%E4

14. https://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C5%E2%EA%EB%E8%E4%E0

1. Докажите утверждения:

2. Найдите наибольший общий делитель чисел:

3. Для каждого натурального n найдите:

4. Найдите все натуральные n, при которых дроби сократимы:

5. Найдите все натуральные числа x и y, удовлетворяющие системе:

6. Нечетные числа a и b таковы, что a– b = 64. Найдите наибольший общий делитель чисел a и b.

7. Сумма 10 натуральных чисел равна 1001. Найдите максимальное значение их общего делителя.

8. Найдите наибольший делитель всех чисел вида , где .

9. Найдите линейное представление наибольшего общего делителя чисел.

10. Найдите хотя бы одно решение уравнения в целых числах:

11. Решите уравнения в целых числах

12. Имеются контейнеры массой 132кг и 160кг. Нужно загрузить ими грузовик грузоподъёмностью 5т. Как это можно делать?

13.Найдите наименьше натуральное n такое, что n кратно 19, а n+2 кратно 82.

14.Найдите все трёхзначные числа, которые при делении на 37 дают остаток 2, а при делении на 11 – остаток5.

15.Найдите наименьшее натуральное число, которое делится на 47, а при делении на 43 даёт в остатке 20.

16.Найдите наименьшее натуральное число, которое при делении на 1997 даёт в остатке 97, а при делении на 1998 – остаток98.

17.Найдите трёхзначное число, которое при делении на 7, 11 и 13 даёт соответственно остатки 5,9 и 11.

Ответы к задачам:3. а) 1; б) 1; в) 1; д) 1. 4. а) несократимо; б) несократимо; в) сократимо на 5, n=5k3, k. 5. б) x=24(6n+1) и y=24(6n-5);x=24(6n+5) и y=24(6n-1). 6. 1. 7. 91. 8. 57 (доказать, что . 9. а) ; б) . 10. а) х=-16, у=9; б) х=2, у=1. 11. б) ; в) . 12. 10 контейнеров – 132 кг и 23 кг – 160 кг. 13. 1064. 14. 335; 742. Указание: .

Теорема. Уравнение , где целые числа, причем , имеет решение в целых числах. При этом, если пара целых чисел удовлетворяют данному условию, то все остальные решения уравнения задаются равенствами .

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

Рассмотрим далее произвольное решение данного уравнения. Пусть пара чисел xи yудовлетворяет равенству. Кроме того, получим, что . Вычитая из первого равенства второе, получим: или . Поскольку правая часть последнего равенства делится на b, то и число кратно . Но взаимно простые числа, поэтому на делится число . Таким образом, найдется такое целое , что . Подставляя его в равенство , получим, что .

Окончательно имеем, что любое решение уравнения выражается формулами: , где  некоторое решение данного уравнения.

Верно и наоборот, а именно: если пара целых чисел удовлетворяют уравнению , то для каждого целого t пара чисел также являются решениями данного уравнения. В самом деле, .

1. Ниже записан алгоритм. После выполнения алгоритма было напечатано 3 числа. Первые два напечатанных числа – это числа 9 и 81. Какое наибольшее число может быть напечатано третьим?[5]

var x, y, z: integer; r, a, b: integer;

begin

readln(x, у);

if у > x then begin

z:= x; x:= у; у:= z;

end;

a:= x; b:= y;

while b > 0 do begin

r:= a mod b; a:= b; b:= r;

end;

writeln(a); writeln(x); write(у);

end.

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

if у > x then begin

z:= x; x:= у; у:= z;

end;

затем исходные значения копируются в переменные a и b и с ними выполняется следующий алгоритм

while b > 0 do begin

r:= a mod b; a:= b; b:= r;

end;

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

Делаем вывод, что это классический Алгоритм Евклида, который служит для вычисления наибольшего общего делителя (НОД) двух чисел; это делитель в результате оказывается в переменной a.

Смотрим, что выводится на экран: сначала значение переменной a (наибольший общий делитель исходных чисел, НОД(x,y)), затем значение x (большее из исходных чисел) и значение y (меньшее из исходных чисел).

По условию первое число – 9, второе – 81, поэтому третье число должно быть меньше, чем 81, и НОД(81,y) = 9.

Наибольшее число, которое меньше 81 и делится на 9, равно 72 (обратите внимание, что исходные числа не могут быть равны, потому что в этом случае их НОД был бы равен 81). Ответ: 72.

1. Ниже записан алгоритм. Получив на вход число х, этот алгоритм печатает число М. Известно, что х>40. Укажите наименьшее такое (т.е. большее 40) число х, при вводе которого алгоритм печатает 5. [5]

Var x, L, M: integer;

Begin

Readln(x);

L:=x; M:=5;

If L mod 2 = 0 then M:= 24;

While LM do

If L>M Then L:=L-M else M:=M-L;

writeln(M);

End.

Решение: Здесь сначала вводится число х, которое запоминается в переменной L. Первоначально переменной М присваивается значение 5. Затем проверяется значение переменной L на четность, и, если L четное, то М присваивается значение 24.

If L mod 2 = 0 then M:= 24;

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

While LM do

If L>M Then L:=L-M else M:=M-L;

Алгоритм Евклида служит для вычисления наибольшего общего делителя (НОД) двух чисел. Так как в данной программе одно из чисел первоначально равно 5 (M:=5)и на экран выводится М, равное 5, то значит, второе число в переменной L первоначально тоже должно делиться на 5. Наименьшее число, большее 40, которое делится на 5 – число 45.

Ответ: 45.