муниципальное бюджетное образовательное учреждение
гимназия № 35 Ленинского района города Ростова-на-Дону
Наибольший общий делитель
Выполнила: ученица 6 «в» класса
Федотова Екатерина
Учитель:
Ростов-на-Дону
2014г
Обзор литературы. Наибольший общий делитель.Наибольшее натуральное число, на которое делится каждое из данных чисел, называется наибольшим общим делителем этих чисел.
Дляобозначения наибольшего общего делителя двух натуральных чисел aи bиспользуют запись: НОД (a, b).
Аналогичное обозначение используется для обозначения наибольшего общего делителя трех и более чисел.
Наибольший общий делитель взаимно простых чисел равен единице.
Способы отыскания наибольшего общего делителя.Как отыскивать наибольший общий делитель? Рассмотрим следующие способы:
По определению; Способ перебора; Способ разложения на простые множители; Алгоритм Евклида.Способ отыскания наибольшего общего делителя по определению заключается в том, что нужно:
- выписать все делители каждого числа;
- выбрать одинаковые делители;
- выбрать наибольший из множества одинаковых делителей.
Для нахождения наибольшего общего делителя способом перебора выписывают множество делителей меньшего из чисел, а затем большие числа делят на элементы полученного множества, взятые в порядке убывания. Наибольший из элементов этого множества, на который будут делиться данные числа и является наибольшим общим делителем.
Данные два способа вполне понятны, только очень уж громоздки.
Есть другой способ отыскания наибольшего общего делителя – способ разложения чисел на простые множители. Что бы отыскать наибольший общий делитель этим способом надо разложить числа на простые множители и найти произведение тех из них, которые встречаются в разложении каждого из чисел.
Способ этот очень прост, понятен и удобен, но у него есть существенный недостаток: если данные числа велики, да еще и не очень легко раскладываются на множители, то задача отыскания наибольшего общего делителя становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убедимся, что НОД (a, b, . . .) = 1 (т. е. числа a, b,…окажутся взаимно простыми) и вроде бы вся работа проделана зря.
Евклид (см. Приложение 1) нашел замечательный способ отыскания наибольшего общего делителя без какой бы то ни было предварительной обработки чисел. Впоследствии этот способ стали называть алгоритмом Евклида. Вот его простейший вид. Пусть даны два натуральных числа. Если они равны, то их наибольшим делителем будет каждое из них. Если они не равны, то вычитаем из большего числа меньшее. Теперь рассмотрим вычитаемое и разность. Проделаем с ними ту же самую процедуру. Этот процесс будет продолжаться до тех пор, пока вычитаемое и разность не станут равны. Поскольку большее число в парах на каждом шаге уменьшается, но всегда не меньше единицы, то такой процесс не может продолжаться бесконечно, а закончится через несколько шагов. Другими словами, чтобы найти наибольший общий делитель двух натуральных чисел, нужно сначала большее число разделить на меньшее, затем второе число разделить на остаток от первого деления, потом первый остаток – на второй и т. д. Последний ненулевой остаток в этом процессе и будет наибольшим общим делителем данных чисел.
Удобство алгоритма Евклида становится особенно заметным, если применить хорошо продуманную форму записи, например такую:
a | b |
|
|
| … |
|
|
|
| … |
В этой табличке сначала записывают исходные числа aи b, делят в уме, записывая остатки справа 
, а неполные частные 
–внизу, пока процесс не закончится. Последний делитель и есть наибольший.
Алгоритм Евклида известен издавна. Ему уже более 2 тыс. лет. Этот алгоритм сформулирован в «Началах» Евклида, где из него выводятся свойства простых чисел, наименьшего общего кратного и др. Алгоритм Евклида имеет много применений. Например, он является средством для представления рационального числа в виде цепной дроби.
Практическая часть.
№ 1
Найти наибольший общий делитель чисел 1320 и 2016.
1320:1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 20, 22, 24, 30, 33, 40, 44, 55, 60, 66, 88, 110, 120 132, 165, 220, 264, 330, 440, 660, 1320.2016:1, 2, 3,4,6,7, 8, 9, 12, 14, 16, 18, 21, 24, 28, 32, 36, 42, 48, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016.
{1, 2, 3, 4, 6, 8, 12, 24}
НОД (1320, 2016) = 24.
1320: 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 20, 22, 24, 30, 33, 40, 44, 55, 60, 66, 88, 110, 120 132, 165, 220, 264, 330, 440, 660, 1320.
2016:1320 = 1 (ост. 696)
2016 : 660 = 3 (ост. 36)
2016 : 440 = 4 (ост. 256)
2016 : 330 = 6 (ост. 36)
2016 : 264 = 7 (ост. 168)
2016 : 220 = 9 (ост. 36)
2016 : 165 = 12 (ост. 36)
2016 : 132 = 15 (ост. 36)
2016 : 120 = 16 (ост. 96)
2016 : 110 = 18 (ост. 36)
2016 : 88 = 22 (ост. 80)
2018 :66 = 30 (ост. 36)
2016 : 60 = 33 (ост. 36)
2016 : 55 = 36 (ост. 36)
2016 : 44 = 45 (ост. 36)
2016 : 40 = 50 (ост. 16)
2016 : 33 = 61 (ост. 3)
2016 : 30 = 67 (ост. 6)
2016 :24 = 84 (ост. 0)
НОД (1320, 2016) = 24.
1320 5 2016 3
264 3 672 3
88 2 224 2
44 2 112 2
22 2 56 2
11 11 28 2
1 14 2
7 7
1
НОД (1320, 2016) = 
= 24.
а) 2016 – 1320 = 696
1320 – 696 = 624
696 – 624 = 72
624 – 72 = 552
552 – 72 = 480
480 – 72 = 408
408 – 72 = 336
336 – 72 = 264
264 – 72 = 192
192 – 72 = 120
120 – 72 = 48
72 – 48 = 24
48 – 24 = 24
24 – 24 = 0
НОД (1320, 2016) = 24.
б) 2016 1320
1320 1
1320 696
696 1
696 624
624 1
624 72
576 8
72 48
48 1
48 24
48 2
0
НОД (1320, 2016) = 24.
в)
2016 | 1320 | 696 | 624 | 72 | 48 | 24 | 0 |
1 | 1 | 1 | 8 | 1 | 2 |
НОД (1320, 2016) = 24.
№ 2
Найти наибольший общий делитель чисел 25 и 175.
25:1, 5, 25.175:1,5, 7, 25, 35, 175.
{1, 5, 25}
НОД (25, 175) = 25.
25: 1, 5, 25.
175 :25 = 7(ост. 0)
НОД (25, 175) = 25.
25 5 175 5
5 5 35 5
1 7 7
1
НОД (25, 175) = 
= 25.
а) 175 –25 = 150
150 – 25 = 125
125 – 25 = 100
100 – 25 = 75
75 – 25 = 50
50 – 25 = 25
25 – 25 = 0
НОД (25, 175) = 25.
б) 175 25
175 7
0
НОД (25, 175) = 25.
в)
175 | 25 | 0 |
7 |
НОД (25, 175) = 25.
№ 3
Найти наибольший общий делитель чисел 675 и 825.
675:1, 3, 5, 9, 15, 25, 27, 45, 75,135, 225, 675.825:1,3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825.
{1, 3, 5, 15,25, 75}
НОД (675, 825) = 75.
675:1, 3, 5, 9, 15, 25, 27, 45, 75, 135, 225, 675.
825:675 = 1 (ост. 150)
825 :225 = 3 (ост. 150)
825 :135 = 6 (ост. 15)
825 :75 = 11 (ост. 0)
НОД (675, 825) = 75.
675 5 825 5
135 5 165 5
27 3 33 3
9 3 11 11
3 3 1
1
НОД (675, 825) = 
= 75.
а) 825 – 675 = 150
675 – 150 = 525
525 – -150 = 375
375 – 150 = 225
225 – 150 = 75
150 – 75 = 75
75 – 75 = 0
НОД (675, 825) = 75.
б) 825 675
675 1
675 150
600 4
150 75
150 2
0
НОД (675, 825) = 75.
в)
825 | 675 | 150 | 75 | 0 |
1 | 4 | 2 |
НОД (675, 825) = 75.
Таким образом, можно сделать вывод, что первые три способа нахождения наибольшего общего делителя понятны, но работа с большими числами требует особой внимательности и задача отыскания наибольшего общего делителя становится очень трудоемкой. Алгоритм Евклида действительнопозволяет отыскать наибольший общий делительбез предварительной обработки чисел – достаточно знать правило деления натуральных чисел и таблицу умножения!
Приложение 1
Евклимд или Эвклимд (др.-греч.ЕὐклеЯдзт, от «добрая слава»[1], время расцвета — ок. 300г. Дон. э.)— древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Биографические сведения о Евклиде крайне скудны. Достоверным можно считать лишь то, что его научная деятельность протекала в Александрии в 3 в. дон. э.[2]
Евклид — первый математик Александрийской школы. Его главная работа «Начала» (Уфпйчеῖб, в латинизированной форме — «Элементы») содержит изложение ряда вопросов из нескольких разделов математики; в ней он подвёл итог предшествующему развитию Древнегреческой математики и создал фундамент дальнейшего развития математики. Из других сочинений по математике надо отметить «О делении фигур», сохранившееся в арабском переводе, 4 книги «Конические сечения», материал которых вошёл в произведение того же названия АполлонияПергского, а также «Поризмы», представление о которых можно получить из «Математического собрания» Паппа Александрийского. Евклид — автор работ по астрономии, оптике, музыке и др.
Список литературы
Retrieved 2011-12-04 Евклид // Математический энциклопедический словарь. — М: Сов. энциклопедия, 1988 За страницами учебника алгебры: книга для учащихся 7 – 9 кл. сред. шк. – М.: Просвещение, 1990. – 224. Энциклопедический словарь юного математика / Сост. . – М.: Педагогика, 1989. – 352. Я познаю мир: Детская энциклопедия: Математика / Сост. , , . – М.: АСТ, 1996. – 480. ru. wikipedia. org/wiki/Евклид