НОД и НОК

Продолжаем изучать деление. В данном уроке мы рассмотрим такие понятия, как НОД и НОК.

НОД — это наибольший общий делитель.

НОК — это наименьшее общее кратное.

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

Наибольший общий делитель

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

Чтобы хорошо понять это определение, подставим вместо переменных a и b любые два числа. Например, вместо переменной a подставим число 12, а вместо переменной b — число 9. Теперь попробуем прочитать это определение:

Наибольшим общим делителем чисел 12 и 9 называется наибольшее число, на которое 12 и 9 делятся без остатка.

Из определения понятно, что речь идёт об общем делителе чисел 12 и 9. Причем делитель является наибольшим из всех существующих делителей. Этот наибольший общий делитель (НОД) нужно найти.

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

Второй и третий способы довольны просты и дают возможность быстро найти НОД. Рассмотрим все три способа. А какой применять на практике — выбирать вам.

Первый способ заключается в поиске всех возможных делителей двух чисел и в выборе наибольшего из них. Рассмотрим этот способ на следующем примере: найти наибольший общий делитель чисел 12 и 9.

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

12 : 1 = 12
(12 разделилось на 1 без остатка, значит 1 является делителем числа 12)

12 : 2 = 6
(12 разделилось на 2 без остатка, значит 2 является делителем числа 12)

12 : 3 = 4
(12 разделилось на 3 без остатка, значит 3 является делителем числа 12)

12 : 4 = 3
(12 разделилось на 4 без остатка, значит 4 является делителем числа 12)

12 : 5 = 2 (2 в остатке)
(12 не разделилось на 5 без остатка, значит 5 не является делителем числа 12)

12 : 6 = 2
(12 разделилось на 6 без остатка, значит 6 является делителем числа 12)

12 : 7 = 1 (5 в остатке)
(12 не разделилось на 7 без остатка, значит 7 не является делителем числа 12)

12 : 8 = 1 (4 в остатке)
(12 не разделилось на 8 без остатка, значит 8 не является делителем числа 12)

12 : 9 = 1 (3 в остатке)
(12 не разделилось на 9 без остатка, значит 9 не является делителем числа 12)

12 : 10 = 1 (2 в остатке)
(12 не разделилось на 10 без остатка, значит 10 не является делителем числа 12)

12 : 11 = 1 (1 в остатке)
(12 не разделилось на 11 без остатка, значит 11 не является делителем числа 12)

12 : 12 = 1
(12 разделилось на 12 без остатка, значит 12 является делителем числа 12)

Теперь найдём делители числа 9. Для этого проверим все делители от 1 до 9

9 : 1 = 9
(9 разделилось на 1 без остатка, значит 1 является делителем числа 9)

9 : 2 = 4 (1 в остатке)
(9 не разделилось на 2 без остатка, значит 2 не является делителем числа 9)

9 : 3 = 3
(9 разделилось на 3 без остатка, значит 3 является делителем числа 9)

9 : 4 = 2 (1 в остатке)
(9 не разделилось на 4 без остатка, значит 4 не является делителем числа 9)

9 : 5 = 1 (4 в остатке)
(9 не разделилось на 5 без остатка, значит 5 не является делителем числа 9)

9 : 6 = 1 (3 в остатке)
(9 не разделилось на 6 без остатка, значит 6 не является делителем числа 9)

9 : 7 = 1 (2 в остатке)
(9 не разделилось на 7 без остатка, значит 7 не является делителем числа 9)

9 : 8 = 1 (1 в остатке)
(9 не разделилось на 8 без остатка, значит 8 не является делителем числа 9)

9 : 9 = 1
(9 разделилось на 9 без остатка, значит 9 является делителем числа 9)

Теперь выпишем делители обоих чисел. Числа выделенные синим цветом и являются делителями. Их и выпишем:

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

Согласно определению, наибольшим общим делителем чисел 12 и 9, является число, на которое 12 и 9 делятся без остатка. Наибольшим и общим делителем чисел 12 и 9 является число 3

И число 12 и число 9 делятся на 3 без остатка:

12 : 3 = 4

9  : 3 = 3

Значит НОД (12 и 9) = 3

Второй способ нахождения НОД

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

Пример 1. Найти НОД чисел 24 и 18

Сначала разложим оба числа на простые множители:

Теперь перемножим их общие множители. Чтобы не запутаться, общие множители можно подчеркнуть.

Смотрим на разложение числа 24. Первый его множитель это 2. Ищем такой же множитель в разложении числа 18 и видим, что он там тоже есть. Подчеркиваем обе двойки:

Снова смотрим на разложение числа 24. Второй его множитель тоже 2. Ищем такой же множитель в разложении числа 18 и видим, что его там второй раз уже нет. Тогда ничего не подчёркиваем.

Следующая двойка в разложении числа 24 также отсутствует в разложении числа 18.

Переходим к последнему множителю в разложении числа 24. Это множитель 3. Ищем такой же множитель в разложении числа 18 и видим, что там он тоже есть. Подчеркиваем обе тройки:

Итак, общими множителями чисел 24 и 18 являются множители 2 и 3. Чтобы получить НОД, эти множители необходимо перемножить:

2 × 3 = 6

Значит НОД (24 и 18) = 6

Третий способ нахождения НОД

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

Пример 1. Найти НОД чисел 28 и 16.

В первую очередь, раскладываем числа 28 и 16 на простые множители:

Получили два разложения:  и 

Теперь из разложения первого числа вычеркнем множители, которые не входят в разложение второго числа. В разложение второго числа не входит семёрка. Её и вычеркнем из первого разложения:

Теперь перемножаем оставшиеся множители и получаем НОД:

Число 4 является наибольшим общим делителем чисел 28 и 16. Оба этих числа делятся на 4 без остатка:

28 : 4 = 7

16 : 4 = 4

 НОД (28 и 16) = 4

Пример 2. Найти НОД чисел 100 и 40

Раскладываем на множители число 100

Раскладываем на множители число 40

Получили два разложения: 2 × 2 × 5 × 5 и 2 × 2 × 2 × 5

Теперь из разложения первого числа вычеркнем множители, которые не входят в разложение второго числа. В разложение второго числа не входит одна пятерка (там только одна пятёрка). Её и вычеркнем из первого разложения

Перемножим оставшиеся числа:

Получили ответ 20. Значит число 20 является наибольшим общим делителем чисел 100 и 40. Эти два числа делятся на 20 без остатка:

100 : 20 = 5

40 : 20 = 2

 НОД (100 и 40) = 20.

Пример 3. Найти НОД чисел 72 и 128

Раскладываем на множители число 72

Раскладываем на множители число 128

Получили два разложения: 2 × 2 × 2 × 3 × 3 и 2 × 2 × 2 × 2 × 2 × 2 × 2.

Теперь из разложения первого числа вычеркнем множители, которые не входят в разложение второго числа. В разложение второго числа не входят две тройки (там их вообще нет). Их и вычеркнем из первого разложения:

Перемножим оставшиеся числа:

Получили ответ 8. Значит число 8 является наибольшим общим делителем чисел 72 и 128. Эти два числа делятся на 8 без остатка:

72 : 8 = 9

128 : 8 = 16

 НОД (72 и 128) = 8

Нахождение НОД для нескольких чисел

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

Например, найдём НОД для чисел 18,  24  и  36

Разложим на множители число 18

Разложим на множители число 24

Разложим на множители число 36

Получили три разложения:

Теперь найдём и подчеркнём общие множители:

Мы видим, что общие множители для чисел 18, 24 и 36 это множители 2 и 3. Эти множители входят во все три разложения. Перемножив эти множители, мы получим НОД, который ищем:

2 × 3 = 6

Получили ответ 6. Значит число 6 является наибольшим общим делителем чисел 18, 24 и 36. Эти три числа делятся на 6 без остатка:

18 : 6 = 3

24 : 6 = 4

36 : 6 = 6

 НОД (18, 24 и 36) = 6

Пример 2. Найти НОД для чисел 12, 24, 36 и 42

Разложим на простые множители каждое число. Затем найдём произведение общих простых множителей.

Разложим на множители число 12

Разложим на множители число 24

Разложим на множители число 36

Разложим на множители число 42

Получили четыре разложения:

Теперь найдём и подчеркнём общие множители:

Мы видим, что общие множители для чисел 12, 24, 36, и 42 это множители 2 и 3. Перемножив эти множители, мы получим НОД, который ищем:

2 × 3 = 6

Получили ответ 6. Значит число 6 является наибольшим общим делителем чисел 12, 24, 36 и 42. Эти числа делятся на 6 без остатка:

12 : 6 = 2

24 : 6 = 4

36 : 6 = 6

42 : 6 = 7

 НОД (12, 24 , 36 и 42) = 6

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

Из предыдущего урока мы знаем, что если какое-то число без остатка разделилось на другое, его называют кратным этого числа.

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

Определение. Наименьшее общее кратное (НОК) чисел a и b — это наименьшее число, которое кратно a и b. Другими словами, это такое маленькое число, которое делится без остатка на число a и число b.

Определение содержит две переменные a и b. Давайте подставим вместо этих переменных любые два числа. Например, вместо переменной a подставим число 9, а вместо переменной b подставим число 12. Теперь попробуем прочитать определение:

Наименьшее общее кратное (НОК) чисел 9 и 12 — это наименьшее число, которое кратно 9 и 12. Другими словами, это такое маленькое число, которое делится без остатка на число 9 и на число 12.

Из определения понятно, что наименьшее общее кратное это наименьшее число, которое делится без остатка на 9 и на 12. Это наименьшее общее кратное требуется найти.

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

В первую очередь, найдем первые кратные для числа 9. Чтобы найти кратные для 9, нужно эту девятку поочерёдно умножить на числа от 1 до 9. Получаемые ответы будут кратными для числа 9.

Итак, начнём. Кратные будем выделять синим цветом:

Теперь находим кратные для числа 12. Для этого поочерёдно умножим число 12 на все числа 1 до 12:

Теперь выпишем кратные обоих чисел:

Теперь найдём общие кратные обоих чисел. Найдя, сразу подчеркнём их:

Общими кратными для чисел 9 и 12 являются кратные 36 и 72. Наименьшим же из них является 36.

Значит наименьшее общее кратное для чисел 9 и 12 это число 36. Данное число делится на 9 и 12 без остатка:

36 : 9 = 4

36 : 12 = 3

НОК (9 и 12) = 36

Второй способ нахождения НОК

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

Применим данный способ для предыдущей задачи. Найдём НОК для чисел 9 и 12.

Разложим на множители число 9

Разложим на множители число 12

Выпишем первое разложение:

Теперь допишем множители из второго разложения, которых нет в первом разложении. В первом разложении нет двух двоек. Их и допишем:

Теперь перемножаем эти множители:

Получили ответ 36. Значит наименьшее общее кратное чисел 9 и 12 это число 36. Данное число делится на 9 и 12 без остатка:

36 : 9 = 4

36 : 12 = 3

НОК (9 и 12) = 36

Говоря простым языком, всё сводится к тому, чтобы организовать новое разложение куда входят оба разложения сразу. Разложением первого числа 9 являлись множители 3 и 3, а разложением второго числа 12 являлись множители 2, 2 и 3.

Наша задача состояла в том, чтобы организовать новое разложение куда входило бы разложение числа 9 и разложение числа 12 одновременно. Для этого мы выписали разложение первого числа и дописали туда множители из второго разложения, которых не было в первом разложении. В результате получили новое разложение 3 × 3 × 2 × 2. Нетрудно увидеть воочию, что в него одновременно входят разложение числа 9 и разложение числа 12

Пример 2. Найти НОК чисел 50 и 180

Разложим на множители число 50

Разложим на множители число 180

Выпишем первое разложение:

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

Теперь перемножаем эти множители:

Получили ответ 900. Значит наименьшее общее кратное чисел 50 и 180 это число 900. Данное число делится на 50 и 180 без остатка:

900 : 50 = 18

900 : 180 = 5

НОК (50 и 180) = 900

Пример 3. Найти НОК чисел 8, 15 и 33

Разложим на множители число 8

Разложим на множители число 15

Разложим на множители число 33

Выпишем первое разложение:

Теперь допишем множители из второго и третьего разложения, которых нет первом разложении. Допишем множители 3 и 5 из второго разложения, и множитель 11 из третьего разложения:

Теперь перемножаем эти множители:

Получили ответ 1320. Значит наименьшее общее кратное чисел 8, 15 и 33 это число 1320. Данное число делится на 8, 15 и 33 без остатка:

1320 : 8 = 165

1320 : 15 = 88

1320 : 33 = 40

НОК (8, 15 и 33) = 1320

Третий способ нахождения НОК

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

Данный способ разумнее использовать, когда одновременно нужно найти НОД и НОК двух чисел.

К примеру, пусть требуется найти НОД и НОК чисел 24 и 12. Сначала найдем НОД этих чисел:

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

Итак, перемножим числа 24 и 12

Разделим полученное число 288 на НОД чисел 24 и 12

Получили ответ 24. Значит наименьшее общее кратное чисел 24 и 12 равно 24

НОК (24 и 12) = 24

Пример 2. Найти НОД и НОК чисел 36 и 48

Найдем НОД чисел 36 и 48

Перемножим числа 36 и 48

Разделим 1728 на НОД чисел 36 и 48

Получили 144. Значит наименьшее общее кратное чисел 36 и 48 равно 144

НОК (36 и 48) = 144

Для проверки можно найти НОК обычным вторым способом, которым мы пользовались ранее. Если мы всё сделали правильно, то должны получить 144

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

Задания для самостоятельного решения

Задание 1. Найдите НОД чисел 12 и 16

Решение:

Задание 2. Найдите НОК чисел 12 и 16

Решение:

Задание 3. Найдите НОД чисел 40 и 32

Решение:

Задание 4. Найдите НОК чисел 40 и 32

Решение:

Задание 5. Найдите НОД чисел 54 и 86

Решение:

Задание 6. Найдите НОК чисел 54 и 86

Решение:

Задание 7. Найдите НОД чисел 98 и 35

Решение:

Задание 8. Найдите НОК чисел 98 и 35

Решение:

Задание 9. Найдите НОД чисел 112 и 82

Решение:

Задание 10. Найдите НОК чисел 112 и 82

Решение:

Задание 11. Найдите НОД чисел 24, 48, 64

Решение:

Задание 12. Найдите НОК чисел 24, 48, 64

Решение:

Задание 13.0 = 75$.

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

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

Основ­ная идея, на кото­рой осно­ван алго­ритм, состоит в том, что $НОД$ чисел $a$ и $b$ равен $НОД$ чисел $b$ и $a-b$. Отсюда сле­дуют, что если поде­лить $a$ на $b$ с остат­ком, т.е. пред­ста­вить в виде
$a = b \cdot q + r$, то $НОД(a, b) = НОД(b, r)$.

Опишем кра­си­вую геомет­ри­че­скую интер­пре­тацию алго­ритма, интер­ак­тив­ная реа­ли­за­ция кото­рой пред­ложена выше.

В прямо­уголь­нике с дли­нами сто­рон $a$ и $b$ закраши­ваем мак­симально возмож­ный квад­рат. В оставшемся прямо­уголь­нике снова закраши­ваем мак­симально возмож­ный квад­рат.
И так далее до тех пор, пока весь исход­ный прямо­уголь­ник не будет закрашен. Длина сто­роны самого маленького квад­рата и будет равна $НОД(a, b)$.

Более подробно геомет­ри­че­ская интер­пре­тация опи­сана ниже, а парал­лельно при­ве­дено арифме­ти­че­ское опи­са­ние алго­ритма Евклида.

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

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

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

Алгоритм нахождения НОД делением

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = 50
b = 130
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Алгоритм нахождения НОД вычитанием

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

Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = 50
b = 130
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция вычисления НОД

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a        
    print(a)

Блок-схема алгоритма Евклида

Примечание. В модуле math языка программирования Python есть функция gcd(), вычисляющая наибольший общий делитель двух чисел.

>>> import math
>>> math.gcd(30, 18)
6

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

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

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

Алгоритм нахождения НОД делением

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = 50
b = 130
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Алгоритм нахождения НОД вычитанием

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

Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = 50
b = 130
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция вычисления НОД

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a        
    print(a)

Блок-схема алгоритма Евклида

Примечание. В модуле math языка программирования Python есть функция gcd(), вычисляющая наибольший общий делитель двух чисел.

>>> import math
>>> math.gcd(30, 18)
6

Наибольший общий делитель (НОД): определение, примеры и свойства

Эта статья посвящена такому вопросу, как нахождение наибольшего общего делителя. Сначала мы объясним, что это такое, и приведем несколько примеров, введем определения наибольшего общего делителя 2, 3 и более чисел, после чего остановимся на общих свойствах данного понятия и докажем их.

Что такое общие делители

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

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

Определение 1

Общим делителем нескольких целых чисел будет такое число, которое может быть делителем каждого числа из указанного множества.

Пример 1

Вот примеры такого делителя: тройка будет общим делителем для чисел -12 и 9, поскольку верны равенства 9=3·3 и −12=3·(−4). У чисел 3 и -12 есть и другие общие делители, такие, как 1, −1 и −3. Возьмем другой пример. У четырех целых чисел 3, −11, −8 и 19 будет два общих делителя: 1 и -1.

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

Также отметим, что если у нас есть общий для нескольких чисел делитель b, то те же числа можно разделить и на противоположное число, то есть на -b.  В принципе, мы можем взять лишь положительные делители, тогда все общие делители также будут больше 0. Такой подход также можно использовать, однако совсем игнорировать отрицательные числа не следует.

Что такое наибольший общий делитель (НОД)

Согласно свойствам делимости, если b является делителем целого числа a, которое не равно 0, то модуль числа b не может быть больше, чем модуль a, следовательно, любое число, не равное 0, имеет конечное число делителей. Значит, число общих делителей нескольких целых чисел, хотя бы одно из которых отличается от нуля, также будет конечным, и из всего их множества мы всегда можем выделить самое большое число (ранее мы уже говорили о понятии наибольшего и наименьшего целого числа, советуем вам повторить данный материал).

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

Переходим к формулировке основного определения.

Определение 2

Наибольшим общим делителем нескольких чисел является самое большое целое число, которое делит все эти числа.

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

Пример 2

Какой можно привести пример НОД для двух целых чисел? Например, для 6 и -15 это будет 3. Обоснуем это. Сначала запишем все делители шести: ±6, ±3, ±1, а потом все делители пятнадцати: ±15, ±5, ±3 и ±1. После этого мы выбираем общие: это −3, −1, 1 и 3. Из них надо выбрать самое большое число. Это и будет 3.

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

Определение 3

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Для чисел a1, a2, …, an делитель удобно обозначать как НОД (a1, a2, …, an). Само значение делителя записывается как НОД (a1, a2, …, an) =b.

Пример 3

Приведем примеры наибольшего общего делителя нескольких целых чисел: 12, -8, 52, 16. Он будет равен четырем, значит, мы можем записать, что НОД (12, -8, 52, 16) =4.

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

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

Пример 4

Так, наибольший общий делитель чисел 60, 15 и -45 равен 15, поскольку пятнадцать делится не только на 60 и -45, но и на само себя, и большего делителя для всех этих чисел не существует.

Особый случай составляют взаимно простые числа. Они представляют собой целые числа с наибольшим общим делителем, равным 1.

Основные свойства НОД и алгоритм Евклида

У наибольшего общего делителя есть некоторые характерные свойства. Сформулируем их в виде теорем и докажем каждое из них.

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

Определение 4

Числа a и b имеют наибольший общий делитель, равный НОД для b и a, то есть НОД (a, b)=НОД (b, a). Перемена мест чисел не влияет на конечный результат.

Данное свойство следует из самого определения НОД и не нуждается в доказательствах.

Определение 5

Если число a можно разделить на число b, то множество общих делителей этих двух чисел будет аналогично множеству делителей числа b, то есть НОД (a, b)=b.

Докажем это утверждение.

Доказательство 1

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

Используя это свойство, мы можем найти наибольший общий делитель двух чисел, если одно из них можно разделить на другое. Такой делитель равен одному из этих двух чисел, на которое можно разделить второе число. К примеру, НОД (8, 24) =8, так как 24 есть число, кратное восьми.

Определение 6

Если верно равенство a=b·q+c (здесь все переменные являются целыми числами), то все общие делители двух чисел a и b будут такими же, как и у чисел b и c, то есть НОД (a, b)=НОД (b, c).

Нужна помощь преподавателя?

Опиши задание — и наши эксперты тебе помогут!

Описать задание

Доказательство 2

Попробуем доказать данное свойство. У нас изначально есть равенство a=b·q+c, и любой общий делитель a и b будет делить и c, что объясняется соответствующим свойством делимости. Поэтому любой общий делитель b и c будет делить a. Значит, множество общих делителей a и b совпадет с множеством делителей b и c, в том числе и наибольшие из них, значит, равенство НОД (a, b)=НОД (b, c) справедливо.

Определение 7

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

Перед тем, как сформулировать свойство, советуем вам повторить теорему, которую мы доказывали в статье о делении с остатком. Согласно ей, делимое число a можно представить в виде b·q+r, причем b здесь является делителем, q – некоторым целым числом (его также называют неполным частным), а r – остатком, который удовлетворяет условию 0≤r≤b.

Допустим, у нас есть два целых числа больше 0, для которых будут справедливы следующие равенства:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Эти равенства заканчиваются тогда, когда rk+1_{становится равен 0. Это случится обязательно, поскольку последовательность b> r1> r2> r3, … представляет собой ряд убывающих целых чисел, который может включать в себя только конечное их количество. Значит, rk является наибольшим общим делителем a и b, то есть, rk=НОД (a, b).}

В первую очередь нам надо доказать, что rk_{– это общий делитель чисел a и b, а после этого – то, что rk является не просто делителем, а именно наибольшим общим делителем двух данных чисел.}

Просмотрим список равенств, приведенный выше, снизу вверх. Согласно последнему равенству,
rk−1 можно разделить на rk. Исходя из этого факта, а также предыдущего доказанного свойства наибольшего общего делителя, можно утверждать, что rk−2 можно разделить на rk, так как
rk−1 делится на rk и rk_{делится на rk.}

Третье снизу равенство позволяет нам сделать вывод, что rk−3 можно разделить на rk, и т.д. Второе снизу – что b делится на rk, а первое – что a делится на rk. Из всего этого заключаем, что rk_{– общий делитель a и b.}

Теперь докажем, что rk=НОД (a, b). Что для этого нужно сделать? Показать, что любой общий делитель a и b будет делить rk. Обозначим его r0_.

Просмотрим тот же список равенств, но уже сверху вниз. Исходя из предыдущего свойства, можно заключить, что r1 делится на r0, значит, согласно второму равенству r2 делится на r0. Идем по всем равенствам вниз и из последнего делаем вывод, что rk делится на r0. Следовательно, rk=НОД (a, b).

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

Перейдем к другим свойствам.

Определение 8

Если a и b являются целыми числами, не равными 0, то должны существовать два других целых числа u0 и v0, при которых будет справедливым равенство НОД (a, b) =a·u0+b·v0.

Равенство, приведенное в формулировке свойства, является линейным представлением наибольшего общего делителя a и b. Оно носит название соотношения Безу, а числа u0 и v0 называются коэффициентами Безу.

Доказательство 3

Докажем данное свойство. Запишем последовательность равенств по алгоритму Евклида:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Первое равенство говорит нам о том, что r1=a−b·q1_. Обозначим 1=s1 и −q1=t1 и перепишем данное равенство в виде r1=s1·a+t1·b. Здесь числа s1 и t1 будут целыми. Второе равенство позволяет сделать вывод, что r2=b−r1·q2=b−(s1·a+t1·b) ·q2=−s1·q2·a+(1−t1·q2) ·b. Обозначим −s1·q2=s2 и 1−t1·q2=t2 и перепишем равенство как r2=s2·a+t2·b, где s2 и t2 также будут целыми. Это объясняется тем, что сумма целых чисел, их произведение и разность также представляют собой целые числа. Точно таким же образом получаем из третьего равенства r3=s3·a+t3·b, из следующего r4=s4·a+t4·b и т.д. В конце заключаем, что rk=sk·a+tk·b при целых sk и tk. Поскольку rk=НОД (a, b), обозначим sk=u0 и tk=v0, В итоге мы можем получить линейное представление НОД в требуемом виде: НОД (a, b) =a·u0+b·v0.

Определение 9

НОД (m·a, m·b) =m·НОД(a, b) при любом натуральном значении m.

Доказательство 4

Обосновать это свойство можно так. Умножим на число m обе стороны каждого равенства в алгоритме Евклида и получим, что НОД (m·a, m·b) =m·rk, а rk – это НОД (a, b). Значит, НОД (m·a, m·b) =m·НОД(a, b). Именно это свойство наибольшего общего делителя используется при нахождении НОД методом разложения на простые множители.

Определение 10

Если у чисел a и b есть общий делитель p, то НОД (a:p, b:p)=НОД(a, b):p. В случае, когда p=НОД (a, b) получим НОД (a:НОД(a, b), b:НОД (a, b)=1, следовательно, числа a:НОД(a, b) и b:НОД (a, b) являются взаимно простыми.

Поскольку a=p·(a:p) и b=p·(b:p), то, основываясь на предыдущем свойстве, можно создать равенства вида НОД(a, b)=НОД(p·(a:p), p·(b:p))=p·НОД(a:p, b:p), среди которых и будет доказательство данного свойства. Это утверждение мы используем, когда приводим обыкновенные дроби к несократимому виду.

Определение 11

Наибольшим общим делителем a1, a2, …, ak будет число dk, которое можно найти, последовательно вычисляя НОД (a1, a2)=d2, НОД (d2, a3) =d3, НОД (d3, a4) =d4, …, НОД (dk-1, ak) =dk.

Это свойство полезно при нахождении наибольшего общего делителя трех и более чисел. С помощью него можно свести это действие к операциям с двумя числами. Его основой является следствие из алгоритма Евклида: если множество общих делителей a1, a2 и a3 совпадает с множеством d2 и a3, то оно совпадет и с делителями d3. Делители чисел a1, a2, a3 и a4 совпадут с делителями d3, значит, они совпадут и с делителями d4, и т.д. В конце мы получим, что общие делители чисел a1, a2, …, ak_{совпадут с делителями dk, а поскольку наибольшим делителем числа dkбудет само это число, то НОД (a1, a2, …, ak) =dk.}

Это все, что мы хотели бы рассказать о свойствах наибольшего общего делителя.

Электронный справочник по математике для школьников арифметика наибольший общий делитель взаимно простые числа алгоритм нахождения наибольшего общего делителя

Наибольший общий делитель. Взаимно простые числа

Содержание

Общий делитель нескольких натуральных чисел. Наибольший общий делитель. Взаимно простые числа

ОПРЕДЕЛЕНИЕ 1. Общим делителем нескольких натуральных чисел называют число, которое является делителем каждого из этих чисел.

ОПРЕДЕЛЕНИЕ 2. Самый большой из общих делителей называют наибольшим общим делителем (НОД).

ПРИМЕР 1. Общими делителями чисел   30 , 45   и   60   будут числа   1 , 3 , 5 , 15 .   Наибольшим общим делителем этих чисел будет

НОД ( 30 , 45 , 10) = 15 .

ОПРЕДЕЛЕНИЕ 3. Если наибольший общий делитель нескольких чисел равен   1 ,   то эти числа называют взаимно простыми.

ПРИМЕР 2. Числа   40   и   3   будут взаимно простыми числами, а числа   56   и   21   не являются взаимно простыми, поскольку у чисел   56   и   21   есть общий делитель  7 ,   который больше, чем   1.

ЗАМЕЧАНИЕ. Если числитель дроби и знаменатель дроби являются взаимно простыми числами, то такая дробь несократима.

Алгоритм нахождения наибольшего общего делителя

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

ПРИМЕР 3. Найти наибольший общий делитель чисел   100, 750   и   800 .

РЕШЕНИЕ. Разложим эти числа на простые множители:

Простой множитель   2   в первое разложение на множители входит в степени   2 ,   во второе разложение – в степени   1 ,   в третье разложение – в степени   5 .   Обозначим наименьшую из этих степеней буквой   a .   Очевидно, что   a = 1 .

      Простой множитель   3   в первое разложение на множители входит в степени   0   (другими словами, множитель   3   в первое разложение на множители вообще не входит), во второе разложение входит в степени   1 ,   в третье разложение – в степени   0 .   Обозначим наименьшую из этих степеней буквой   b .  Очевидно, что   b = 0 .

Простой множитель   5   в первое разложение на множители входит в степени   2 ,   во второе разложение – в степени   3 ,   в третье разложение – в степени   2 .   Обозначим наименьшую из этих степеней буквой   c .  Очевидно, что   c = 2 .

      Теперь рассмотрим число:

Это число и есть наибольший общий делитель чисел   100, 750   и   800 .

ОТВЕТ:   50 .

ЗАМЕЧАНИЕ. Чтобы сократить дробь, нужно её числитель и знаменатель разделить на их наибольший общий делитель.

НОД и НОК (Тамаркова)

НОД, НОД

НОД — это наибольший общий делитель.

НОК — это наименьшее общее кратное.

Определения:

1. Наибольшим общим делителем чисел a и b называется наибольшее число, на которое a и b делятся без остатка.
2. Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка

Способы нахождения НОД двух чисел:

1 способ (следует из определения): Метод полного перебора для нахождения наибольшего общего делителя (НОД)  натуральных чисел.

1. Выписываем все делители числа а;
2. Выписываем все делители числа b;
3. Выбираем среди них общие делители;
4. Среди общих делителей выбираем самое большое число – это и есть НОД(a, b).

2 способ : Метод перебора делителей меньшего числа для нахождения наибольшего общего делителя (НОД)  натуральных чисел.

1. Найти делители меньшего из данных чисел.
2. Найти, начиная с большего, тот из выписанных делителей, который является также делителем другого числа.
3. Записать найденное число – НОД.

3 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители.

1. Находим разложение чисел на простые множители.
2. Подчеркиваем общие числа.
3. Находим произведение подчеркнутых чисел у одного числа.
4. Записываем ответ.

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

1. Из большего числа вычитается меньшее.
2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.
3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания.
4. Переход к пункту 1.

Способы нахождения НОК двух чисел:

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

2 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители

1.  Разложить данные числа на простые множители.
2.  Выписать в строчку множители, входящие в разложение самого большого из чисел, а под ним — разложение остальных чисел.
3.  Подчеркнуть в разложении меньшего числа множители, которые не вошли в разложение бóльшего числа и добавить эти множители в разложение большего числа. 
4.  Полученное произведение записать в ответ. 

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

1. НОД(a, b) = НОД(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОД(a, 0) = |a|
5. НОД(a, к • a) = |a|, при любом к ∈ Z
6. НОД(a, НОД(b, с)) = НОД(НОД(a, b), c)

Свойства наименьшего общего кратного:

1. НОК(a, b) = НОК(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОК(a, НОК(b, с)) = НОК(НОК(a, b), c)

Наибольший общий коэффициент

Наибольшее число, которое делится точно на два или более числа.
Это «величайшая» штука для упрощения дробей!

Начнем с примера …

Наибольший общий множитель 12 и 16

1. Найдите все Факторы каждого числа,
2. Обведите Общие множители,
3. Выберите Самый большой из тех

Итак… что такое «Фактор»?

Факторы — это числа, которые мы можем умножить, чтобы получить другое число:

Число может иметь много факторов:

Факторы 12: 1, 2, 3, 4, 6 и 12 …

…
потому что 2 × 6 = 12, или 4 × 3 = 12, или 1 × 12 = 12.

(Прочтите, как найти все множители числа.В нашем случае отрицательные нам не нужны.)

Что такое «общий фактор»?

Допустим, мы вычислили множители двух чисел:

Пример: множители 12 и 30

Тогда общие множители — это те, которые встречаются в обоих
списки:

• Обратите внимание, что 1, 2, 3 и 6 появляются в обоих списках?
• Итак, общие множители для 12 и 30: 1, 2, 3 и 6

Это общий коэффициент , когда он является множителем двух (или более) чисел.

Вот еще один пример с тремя числами:

Пример: общие множители 15, 30 и 105

Общие для всех трех чисел множители: 1, 3, 5 и 15

Другими словами, общие множители из 15, 30 и 105 равны 1, 3, 5 и 15

Что такое «наибольший общий фактор»?

Это просто наибольших общих множителей.

В нашем предыдущем примере наибольший из общих множителей равен 15, поэтому наибольший общий множитель из 15, 30 и 105 равен 15

«Наибольший общий множитель» — это наибольший из общих множителей (двух или более чисел)

Почему это полезно?

Одна из самых полезных вещей — это когда мы хотим упростить дробь:

Пример: как упростить

12 30 ?

Ранее мы обнаружили, что общие множители 12 и 30 равны 1, 2, 3 и 6, поэтому наибольший общий множитель равен 6 .

Таким образом, наибольшее число , на которое мы можем разделить как 12, так и 30, равно 6 , например:

Наибольший общий множитель 12 и 30 равен 6 .

Итак, 12 30 можно упростить до 2 5

В поисках наибольшего общего фактора

Вот три способа:

1. Мы можем:

• найти все множители обоих чисел (использовать Калькулятор всех множителей),
• затем найдите те, которые общие для обоих, и
• , затем выберите наибольший .

Пример:

А
другой пример:

2 .Или мы можем найти простые множители и объединить общие:

3. Или иногда мы можем просто поиграть с коэффициентами , пока не обнаружим его:

Но в этом случае мы должны проверить, что мы нашли наибольший общий множитель .

Калькулятор наибольшего общего коэффициента

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

Другие названия

«Наибольший общий коэффициент» часто сокращается до « GCF » и также известен как:

• «Наибольший общий делитель (НОД)», или
• «Высший общий коэффициент (HCF)»

Наибольший общий делитель | Блестящая вики по математике и науке

НОД нескольких чисел можно вычислить, просто перечислив множители каждого числа и определив наибольшее общее.Хотя на практике это ужасно неэффективно, в особо небольших случаях это можно сделать вручную. Процесс можно разделить, используя метод пар факторов: как только определяется фактор aaa числа nnn, частное na \ frac {n} {a} an также обязательно является фактором. Например, поскольку 2 — это множитель 24, 242 = 12 \ frac {24} {2} = 12224 = 12 также является множителем.

Найдите наибольший общий делитель 30,36, 30, 36,30,36 и 24,24,24.

---

Делители каждого числа равны

30: 1,2,3,5,6,10,15,3036: 1,2,3,4,6,9,12,18,3624: 1,2,4,6,12,24
\ begin {выровнено}
30: & 1, 2, 3, 5, 6, 10, 15, 30 \\
36: & 1, 2, 3, 4, 6, 9, 12, 18, 36 \\
24: & 1, 2, 4, 6, 12, 24
\ end {выровнен}
30:36:24: 1,2,3,5,6,10,15,301,2,3,4,6,9,12,18,361,2,4,6,12,24

Наибольшее число, которое появляется в каждом списке, — 6, 6,6, так что это наибольший общий делитель:

.

gcd (30,36,24) = 6.□ \ gcd (30,36,24) = 6. \ _ \ Squaregcd (30,36,24) = 6. □

Когда числа велики, список факторов может быть чрезмерно длинным, что затрудняет описанный выше метод. Несколько более эффективный метод — сначала вычислить разложение на простые множители каждого числа в наборе. Результирующий НОД является произведением простых чисел, которые появляются в каждой факторизации, на наименьший показатель степени, видимый в факторизациях. Это сбивает с толку, поэтому давайте посмотрим на пример:

Вычислить gcd⁡ (4200,3780,3528) \ gcd (4200,3780,3528) gcd (4200,3780,3528).{\ min (\ alpha_k, \ beta_k)}. НОД (a, b) = p1min (α1, β1) p2min (α2, β2)… pkmin (αk, βk).

Аналогичная формула используется для нахождения НОД нескольких целых чисел путем взятия наименьшего показателя степени для каждого простого числа.

Отправьте свой ответ

Три золотые монеты весом 780 г, 840 г и 960 г нарезаны на мелкие кусочки одинакового веса.Если для перевозки одного куска золота требуется 2 человека, какое наименьшее количество людей потребуется для перевозки всех этих кусков?

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

Как рассчитать G.CD?

Существует несколько алгоритмов вычисления G.C.D (наибольшего общего делителя) между двумя числами. Самый простой и быстрый процесс состоит в том, чтобы разложить каждое из чисел на произведение простых множителей, это так, и мы последовательно делим каждое из чисел на простые числа, пока не получим частное, равное 1. Я собираюсь дать вам пример, чтобы вам было легче понять. Мы хотим вычислить G.C.D между 168 и 180. Начнем с факторизации каждого из чисел.2 х х 3 = 12 ‘. Таким образом, мы можем заключить, что наибольший общий делитель между 168 и 180 равен 12.

Для чего нужен G.C.D?

Есть несколько проблем, в которых полезно вычисление G.C.D. Предположим, у флориста 168 роз и 180 ромашек, и он хочет сформировать как можно больше гроздей, имея оба типа цветов и одинаковое количество цветов. В этой ситуации, зная, что G.C.D равно 12, достаточно сделать «168: 12 = 14» и «180: 12 = 15».Таким образом, можно сформировать 12 гроздей, по 14 роз и 15 ромашек в каждом.

Можем ли мы использовать G.C.D, чтобы сделать дробь несократимой?

Да, можно. Это тоже полезно делать. Предположим, что у нас есть дробь, составленная из предыдущих чисел, достаточно разделить числитель и знаменатель на G.C.D, чтобы сделать эту дробь несократимой. Таким образом, 168/180 = 14/15

Но, в конце концов, что такое G.C.D двух чисел?

Прежде всего, хочу подчеркнуть, что G.C.D рассчитывается не только между двумя числами. Мы можем вычислить G.C.D для 2, 3, 4 и более чисел! Таким образом, если у нас есть два натуральных числа, мы заверяем вас, что среди них будут общие делители. Если есть только общий делитель, это потому, что этот делитель соответствует числу 1, и в этой ситуации они называются относительно простыми числами. Но если у них несколько общих делителей, значит, G.C.D — самый большой из этих делителей.

Ознакомьтесь с нашим Списком вопросов, чтобы узнать немного больше о самых разных темах, связанных с математикой.Если у вас есть подходящий (математический) вопрос, ответ на который нелегко найти, отправьте нам электронное письмо с вопросом на странице «Контакты». Будем рады ответить. Если вы обнаружите какие-либо ошибки в наших ответах, не стесняйтесь обращаться к нам!

Нахождение наибольшего общего множителя методом списка

Наибольший общий делитель , также известный как GCF , двух чисел — это наибольшее число , которое может равномерно разделить данные два числа.

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

Два приведенных выше определения означают одно и то же.

Не запутайтесь, если вы встретите другие названия наиболее общего фактора. Все они имеют одинаковое значение. Альтернативные названия GCF:

• Наибольший общий делитель, сокращенно GCD

• Наибольший общий делитель, сокращенно HCF

---

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

---

Шаги по поиску наибольшего общего множителя

Шаг 1: Перечислите или запишите ВСЕ множители каждого числа.

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

Шаг 3: После определения общих факторов выберите или выберите число, которое имеет наибольшее значение.Это число будет, по сути, наибольшим общим фактором (GCF).

---

Примеры поиска наибольших общих факторов

ПРИМЕЧАНИЕ. Я решил сосредоточиться на поиске GCF двух чисел, потому что это наиболее частые проблемы, с которыми вы можете столкнуться при изучении GCF.

Пример 1 : Найдите наибольший общий множитель 12 и 18.

Эта задача проста, потому что задействованные числа относительно просты. Вы должны уметь найти все множители 12 и 18, используя метод радуги.В качестве альтернативы я перечислил все множители чисел от 1 до 100, чтобы вы могли использовать их по своему усмотрению.

Итак, вот все множители как 12, так и 18.

Множители числа 12 : 1, 2, 3, 4, 6, 12

Факторы 18 : 1, 2, 3, 6, 9, 18

После перечисления всех факторов каждого числа мы теперь определяем общие факторы. Как вы можете видеть ниже, общие множители 12 и 18 равны 1, 2, 3 и 6. Обратите внимание, что я определил общие множители, заключив их в «прямоугольник».

Так что же тогда GCF? Очевидно, что GCF — один из общих факторов. Общий фактор, имеющий наибольшее значение, на самом деле является наибольшим общим фактором. Следовательно, GCF для 12 и 18 равняется 6. Вот и все!

---

Пример 2 : Найдите наибольший общий множитель 64 и 96.

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

Итак, поехали. Давайте найдем полные множители 64 и 96.

◉ Полные множители 64: 1, 2, 4, 8, 16, 32 и 64.

◉ В то время как полные множители 96 — это 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48 и 96.

Ниже приведены списки факторов в вертикальном формате.

Следующим шагом будет сравнение списков факторов. Затем нарисуйте фигуру так, чтобы общий фактор находился внутри каждой фигуры. Здесь можно проявить творческий подход! Обратите внимание, что на иллюстрации ниже у нас есть шесть (6) общих множителей: 1, 2, 4, 8, 16 и 32.

Если посмотреть на общие множители, то наибольшее значение имеет 32. Следовательно, наибольший общий множитель 64 и 96 равен 32.

---

Пример 3 : Определите наибольший общий множитель 42 и 126.

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

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

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

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

Итак, 42 делит 126 равномерно? Ответ положительный! Следовательно, наибольший общий делитель 42 и 126 равен 42. Готово!

---

Пример 4 : Каков GCF для 71 и 223?

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

Итак, теперь, если вы внимательно изучите два числа, 71 и 223, вы легко поймете, что оба они являются простыми числами. Помните, что у простого числа есть ровно два делителя , которые равны 1 и самому себе. Другими словами, мы можем сказать, что простое число делится только на 1 и само себя.

Перечисление множителей 71 и 223:

Коэффициент 71: 1, 71

Факторы 223: 1, 223

Мы можем сделать вывод, что, поскольку 1 является общим множителем ТОЛЬКО для , это означает, что 1 также должна быть наибольшим общим множителем по умолчанию.Таким образом, {\ rm {gcf}} \ left ({71,223} \ right) = 1.

---

Пример 5 : Что такое GCF 72 и 84?

Во-первых, мы знаем, что оба числа не простые, на самом деле оба четные числа. Это означает, что у них есть общие множители, отличные от 1. Во-вторых, также очевидно, что меньшее число 72 не может равномерно делить большее число 84. Это оставляет нам возможность сделать вывод, что меньшее из двух чисел, 72, является НЕ наибольшим. общий фактор тоже.

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

Перечисляя все множители каждого числа, получаем:

Факторы 72 : 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

Факторы 84 : 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84

Сравнивая списки факторов, общие факторы для 72 и 84 равны 1, 2, 3, 4, 6 и 12.

Судя по диаграмме, 12 является наибольшим общим делителем 72 и 84. Готово!

---

Возможно, вас заинтересует:

Используйте простую факторизацию, чтобы найти GCF

Поиск LCM с использованием метода списка

Используйте простую факторизацию, чтобы найти LCM

Как найти наибольший общий делитель

Если вы считаете, что контент, доступный через Веб-сайт (как определено в наших Условиях обслуживания), нарушает одно
или несколько ваших авторских прав, сообщите нам об этом, отправив письменное уведомление («Уведомление о нарушении»), содержащее
в
информацию, описанную ниже, назначенному ниже агенту.Если репетиторы университета предпримут действия в ответ на
ан
Уведомление о нарушении, оно предпримет добросовестную попытку связаться со стороной, которая предоставила такой контент
средствами самого последнего адреса электронной почты, если таковой имеется, предоставленного такой стороной Varsity Tutors.

Ваше Уведомление о нарушении прав может быть отправлено стороне, предоставившей доступ к контенту, или третьим лицам, таким как
в виде
ChillingEffects.org.

Обратите внимание, что вы будете нести ответственность за ущерб (включая расходы и гонорары адвокатов), если вы существенно
искажать информацию о том, что продукт или действие нарушает ваши авторские права.Таким образом, если вы не уверены, что контент находится
на Веб-сайте или по ссылке с него нарушает ваши авторские права, вам следует сначала обратиться к юристу.

Чтобы отправить уведомление, выполните следующие действия:

Вы должны включить следующее:

Физическая или электронная подпись правообладателя или лица, уполномоченного действовать от их имени;
Идентификация авторских прав, которые, как утверждается, были нарушены;
Описание характера и точного местонахождения контента, который, по вашему мнению, нарушает ваши авторские права, в \
достаточно подробностей, чтобы позволить репетиторам университетских школ найти и точно идентифицировать этот контент; например нам требуется
а
ссылка на конкретный вопрос (а не только на название вопроса), который содержит содержание и описание
к какой конкретной части вопроса — изображению, ссылке, тексту и т. д. — относится ваша жалоба;
Ваше имя, адрес, номер телефона и адрес электронной почты; а также
Ваше заявление: (а) вы добросовестно считаете, что использование контента, который, по вашему мнению, нарушает
ваши авторские права не разрешены законом, владельцем авторских прав или его агентом; (б) что все
информация, содержащаяся в вашем Уведомлении о нарушении, является точной, и (c) под страхом наказания за лжесвидетельство, что вы
либо владелец авторских прав, либо лицо, уполномоченное действовать от их имени.

Отправьте жалобу нашему уполномоченному агенту по адресу:

Чарльз Кон
Varsity Tutors LLC
101 S. Hanley Rd, Suite 300
St. Louis, MO 63105

Или заполните форму ниже:

наибольший общий множитель и наименьшее общее кратное

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

Наибольший общий множитель и наименьшее общее кратное
GCF и LCM

Какие факторы участвуют в следующем сценарии?

У Гэри 20 мячей для настольного тенниса и 16 ракеток.Он хочет продавать упаковки обычных размеров, содержащие как лопатки, так и мячи. Какое наибольшее количество упаковок он может продать без остатков мячей или ракеток?

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

1 · 20 = 20 и 1 · 16 = 16	Одна упаковка с 20 мячами и 16 лопастями.
2 · 10 = 20 и 2 · 8 = 16	Две упаковки по 10 мячей и 8 лопастей.
4 · 5 = 20 и 4 · 4 = 16	Четыре упаковки по 5 мячей и 4 лопатки в каждой.

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

Пример:

Набор множителей 20: {1, 2, 4 , 5, 10, 20}

Набор множителей 16: {1, 2, 4 , 8, 16}

Из этих двух списков мы видим, что наибольший общий делитель 20 и 16 равен 4, поэтому Гэри сможет продать четыре упаковки, каждая из которых содержит четыре ракетки и пять мячей.

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

Определение наибольшего общего множителя (GCF) :

Наибольший общий делитель (GCF) двух натуральных чисел n и m — это наибольшее натуральное число k , которое является множителем как n , так и m . Мы обозначим это как GCF ( n , m ) = k .

Пример:

Связывая это определение с проблемой, которую мы решили на предыдущей странице, мы видим, что два числа n и m — это числа 20 и 16. Мы можем записать решение символически как GCF (20, 16) = 4. Это говорит о том, что «наибольший общий делитель 20 и 16 равен 4».

Число k в определении соответствует 4 в задаче. Это фактор наибольшей ценности, который разделяют как n, , так и m. Число k — наибольший общий множитель 20 и 16.

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

Пример: найдите GCF (20, 16).

Набор множителей 20 равен {1, 2, 4, 5, 10, 20}, а набор множителей 16 равен {1, 2, 4, 8, 16}.

{1, 2, 4, 5, 10, 20} ∩ {1, 2, 4, 8, 16} = {1, 2, 4}, имеющее наибольшее значение 4.

Итак, GCF (20, 16) = 4.

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

Пример: найти GCF (18, 24).

Набор множителей 18 равен {1, 2, 3, 6, 9, 18}
а набор множителей 24 равен {1, 2, 3, 4, 6, 8, 12, 24}.

{1, 2, 3, 6, 9, 18} ∩ {1, 2, 3, 4, 6, 8, 12, 24} = {1, 2, 3, 6}, которое имеет наибольшее значение 6.

ЗКФ (18, 24) = 6.

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

Пример: найти GCF (308, 1176).

Сначала мы находим факторизации чисел на простые множители.

308 = 2 ² · 7 · 11 и 1176 = 2 ³ · 3 · 7 ²

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

Мы видим, что 2 · 2 · 7 — множители, которые есть в обеих факторизациях.

Следовательно, GCF (308, 1176) = 2 · 2 · 7 = 28.

Далее, обратите внимание, что когда факторы сопоставлены, есть три фактора 2 из 1176, но есть только два фактора 2 из 308. Мы смогли сопоставить только меньшее количество 2.Это соответствует наименьшему показателю коэффициента 2.

Итак, чтобы получить ОКФ двух чисел, нам нужно только взять общие простые множители из простых множителей и сравнить их показатели. В каждом случае мы берем экспоненциальное выражение с наименьшим показателем степени и умножаем их вместе.

Пример: мы пересматриваем предыдущий пример, чтобы проиллюстрировать использование экспонент.

Найдите GCF (308, 1176).

Сначала мы находим факторизации чисел на простые множители.

308 = 2 ² · 7 · 11

1176 = 2 ³ · 3 · 7 ²

Для общих простых множителей наименьший показатель степени 2 равен 2, а наименьший показатель степени 7 равен 1. Итак, в этом случае мы имеем GCF (308, 1176) = 2 ² · 7 ¹ = 4 · 7 = 28.

Пример: найти GCF (4950, 7020)

4950 = 2 · 3 ² · 5 ² · 11

7020 = 2 ² · 3 ³ · 5 · 13

Общие простые множители — 2, 3 и 5.Наименьший показатель для 2 и 5 равен единице (2 ¹ = 2 и 5 ¹ = 5), а для 3 равен двум.

Таким образом, GCF (4950, 7020) = 2 · 3 ² · 5 = 90.

Пример: найти GCF (7920, 92664)

7920 = 2 ⁴ · 3 ² · 5 · 11

92664 = 2 ³ · 3 ⁴ · 11 · 13

Общие простые множители — 2, 3 и 11. Наименьший показатель степени для 2 равен 3 (2 ³ ), для 3 равен 2 (3 ² ), а для 11 равен 1 (11 ¹ ).

Таким образом, GCF (7920, 92664) = 2 ³ · 3 ² · 11 = 792.

Как мультипликаторы участвуют в следующем сценарии?

В станке две шестерни. Одна шестерня имеет 12 зубьев, а другая — 20 зубцов. Шестерни выровнены по отметке, проведенной от центра первой шестерни к центру второй шестерни. Какое наименьшее количество оборотов первой передачи необходимо для совмещения отметки?

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

Первая передача: 12, 24, 36, 48, 60 , 72, 84, 96, 108, 120 , 132, 144, 156, 168, 180 , 192,…

Вторая передача: 20, 40, 60 , 80, 100, 120 , 140, 160, 180 , 200, 220, 240 , 260, 280, 300 ,…

Обратите внимание, что мы перечисляем числа, кратные 12 и 20.Первая передача будет согласована со второй передачей после пяти оборотов. (Также обратите внимание, что вторая передача сделает три оборота.)

Ответ на этот вопрос был дан с использованием наименьшего общего кратного . Обратите внимание, что метка на первой передаче возвращается в исходное положение после каждого полного оборота. Это произойдет, когда она пройдет через 12 зубьев, 24 зуба, 36 зубцов и т. Д. Метка на второй шестерне вернется в исходное положение после того, как она совершит любое количество полных оборотов.Это произойдет, когда пройдет 20 зубов, 40 зубов, 60 зубов, 80 зубов и т. Д.

Обратите внимание, что 12, 24, 36,… кратны 12 и 20, 40, 60,… кратны 20.

Метка будет повторно выровнена только тогда, когда будет достигнуто значение, кратное 12 и 20. Отметка будет перестроена в первый раз, когда будет достигнуто первое такое кратное. Следовательно, мы ищем наименьшее общее кратное 12 и 20.

Определение наименьшего общего кратного (LCM) :

Наименьшее общее кратное (НОК) двух натуральных чисел n и m является наименьшим числом h , так что h кратно как n , так и m .Мы обозначим это как LCM ( n , m ) = h .

Пример:

Связывая это определение с проблемой, которую мы решили на предыдущей странице, мы видим, что два числа n и m — это числа 12 и 20. Мы можем записать решение символически как LCM (12, 20) = 60. Это говорит о том, что «наименьшее общее кратное 12 и 20 равно 60».

Число h в определении соответствует 60 в задаче.Он имеет наименьшее значение, если кратные значения разделяются как на n, так и на m. Число h — это наименьшее общее кратное 12 и 20.

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

Пример: найдите НОК (12, 20).

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

Набор кратных 12 равен A = {12, 24, 36, 48, 60, 72, 84, 96, 108, 120,…}

Набор кратных 20 равен B = {20, 40, 60, 80, 100, 120, 140, 160, 180,…}

A ∩ B = {60, 120, 180,…} с наименьшим значением 60.

НОК (12, 20) = 60.

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

Поскольку мы нашли наименьшее общее кратное 60 для проблемы с шестерней, теперь мы можем ответить на вопрос о проблеме с шестерней.Был задан вопрос, сколько оборотов нужно, чтобы выровнять отметку. Поскольку мы знаем, что первая шестерня должна пройти 60 зубцов и после каждых 12 она сделает один оборот, мы знаем, что она должна сделать 5 оборотов, прежде чем метки будут совмещены в первый раз (60 ÷ 12 = 5). (Также обратите внимание, что вторая шестерня должна сделать три оборота, чтобы 60 зубьев прошли отметку, 60 ÷ 20 = 3.)

Как и в случае с GCF, найти НОК больших чисел путем перечисления кратных не очень практично.Кроме того, как и в случае с GCF, мы можем использовать разложение на простые множители , чтобы помочь.

Пример: найти НОК (308,1176).

Мы снова перечисляем основные множители значений.

308 = 2 ² · 7 · 11

1176 = 2 ³ · 3 · 7 ²

Поскольку мы ищем кратные, каждое кратное 308 должно содержать 2 ² · 7 · 11 в качестве множителей, а каждое кратное 1176 должно содержать 2 ³ · 3 · 7 ² в качестве множителей.Это означает, что 2, 3, 7 и 11 должны быть простыми делителями в любом общем кратном. Для 2 и 7, которые присутствуют в обоих списках, нам нужна наибольшая степень этого простого числа в качестве множителя для создания НОК, поскольку 2 ³ автоматически кратно 2 ² . Таким образом, используя наибольшую степень каждого простого числа, LCM (308,1176) = 2 ³ · 3 · 7 ² · 11 = 12 936.

Шутка или цитата

Объекты не следует без надобности умножать.

— Вильгельм Оккам (1300-1439)

наибольших общих делителей

наибольших общих делителей

Определение. величайший
общий делитель двух целых чисел (не равных нулю) является наибольшим
целое число, которое делит их обоих.

Если a и b — целые числа (не оба 0), наибольший общий делитель
Обозначается a и b.

(Наибольший общий делитель иногда называют наибольшим общим делителем , или .
наивысший общий множитель .)

Вот несколько простых примеров:

Вы, вероятно, смогли сделать последние примеры, разложив на множители
числа в твоей голове. Например, чтобы найти, вы видите, что 2 — это
единственное целое число больше 1, которое делит как 4, так и 6.

Проблема с этим подходом в том, что он требует, чтобы вы
число. Однако, как только числа станут слишком большими — в настоящее время,
«слишком большой» означает «порядка нескольких сотен
digits long «— этот подход к поиску наиболее общих
делитель не работает.К счастью, евклидово число
алгоритм вычисляет наибольший общий делитель двух чисел
без факторизации чисел. Я расскажу об этом после того, как заявлю и
доказать некоторые элементарные свойства.

Предложение. Пусть a и b целые числа, а не оба одновременно
0.

(а).

(б).

(c) для любого целого k.

Доказательство. (a) Поскольку и, должны
быть не меньше 1.

(б) тогда и только тогда, когда; то есть а и иметь
те же факторы.Но это либо, либо, значит, и иметь
те же факторы. Точно так же у b и есть те же факторы. Следовательно,
x является общим множителем a и b тогда и только тогда, когда это общий множитель
из и. Следовательно, .

(c) Во-первых, если x является общим делителем a и b, то
а также . Тогда так. Таким образом, x является
общий фактор и b.

Аналогично, если x является общим делителем и b, то и. Следовательно,

Таким образом, x является общим делителем a и b.

Следовательно, эти два набора одинаковы:

Поскольку эти два набора одинаковы, их самые большие элементы одинаковы.Самый большой элемент первого набора равен, а самый большой
элемент второго набора есть. Следовательно,
.

Пример. Используйте свойство, чтобы
вычислить.

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

Итак, единственные положительные целые числа, которые делят 2, — это 1
и 2.Так что либо 1, либо 2. Но 2 и 996, очевидно, оба
делится на 2, поэтому. Следовательно, .

---

Пример. Докажи, что если, то.

Согласно части (c) предложения,

Но единственное положительное целое число, которое делит 1, — это 1.
Итак, а значит.

---

Определение. a и b — это
относительно простое если.

Например, 49 и 54 являются взаимно простыми числами, а 25 и 105 — нет.

Предложение. Если, то.

Доказательство. Предположим и. потом

Предположим, что и,. Тогда я могу найти e и f такие
что

Таким образом,

Это показывает, что это общий множитель m и n. Поскольку d — это
наибольший общий множитель,. Следовательно, ,
так (поскольку p было положительным целым числом).

Я доказал, что 1 — это , только положительный общий множитель
и б.Следовательно, 1 — это наибольший общий делитель a и b:

Евклидов алгоритм. Начните с пары
неотрицательные целые числа, не одновременно 0.

(Свойство абсолютного значения, о котором я говорил ранее, показывает, что нет
вред в предположении, что целые числа неотрицательны.)

1. Если одно из чисел равно 0, другое является наибольшим общим числом.
делитель пары. (Стоп.)

2. В противном случае примените алгоритм деления, чтобы написать, где.

3. Замените пару парой.

4. Переходите к шагу 1.

На каждом шаге оба элемента есть, и каждый проходит шаг 3
уменьшает второй элемент. Поскольку второй элемент всегда получает
меньше, но не может быть отрицательным, Well-Ordering подразумевает, что алгоритм
должен заканчиваться парой (на шаге 2) после конечного числа
шаги.

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

Исходная пара чисел и их наибольшее общее
делитель есть. Последняя пара чисел — и
. Таким образом, — словами, наибольший общий делитель равен
последний ненулевой остаток .

---

Пример. Используйте алгоритм Евклида, чтобы
вычислить.

Вот что говорит приведенный выше алгоритм. Вы начинаете с оригинала
числа. Думайте о них как о первых двух «остатках». В
на каждом шаге предпоследний остаток делится на последний
остаток. Вы остановитесь, когда получите остаток 0. Вот
подразделения:

(Начните с деления большего числа на меньшее, иначе
вы просто потеряете шаг.)

Это проще запомнить визуально, расставив вычисления
в таблице. Сравните числа выше с числами в следующих
Таблица:

(Следующий остаток равен 0, поэтому я не писал его.) Последовательные
остатки идут в столбец «а». Последовательные частные идут в
q-столбец.

Наибольший общий делитель — это последнее ненулевое число .
остаток , так.

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

---

Пример. Вычислить.

Я вижу это по таблице.

---

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

Пример. Вычислить.

---

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

Определение. Если x и y числа, линейная комбинация x и y (с целым числом
коэффициенты) — число вида

Например, показывает, что 29 является линейным
комбинация 10 и 9. показывает, что 7 — это
линейная комбинация 10 и 9.

Теорема. — наименьший положительный линейный
сочетание m и n. В частности, есть целые числа a и b
(не обязательно уникальный) такой, что

Например, я показал это выше.Теорема говорит, что
есть целые числа a и b такие, что

По факту,

Эта комбинация не уникальна. Например,

Позже мы обсудим, как найти числа, которые дают линейную
комбинация.

Перед доказательством теоремы я приведу несколько простых следствий.

Следствие. Набор всех линейных комбинаций
целых чисел m и n — это множество всех кратных.

Доказательство. С одной стороны,

Таким образом, каждая линейная комбинация m и n кратна.

С другой стороны,

То есть каждое кратное является линейной комбинацией m и
п.

Давайте посмотрим на некоторые конкретные цифры. У меня есть, так что
Теорема утверждает, что множество всех линейных комбинаций 42 и 105
— то есть набор всех чисел формы — это
набор всех кратных 21:

Обратите внимание, что наибольший общий делитель — наименьший положительный
элемент этого набора.

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

Следствие. Если и, то.

Доказательство.

Следовательно, а, значит.

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

Следствие. m и n взаимно просты, если и
только если

Доказательство. () Предположим, что m и
n относительно простые. Потом . По теореме

Следовательно,

( ) Предполагать

Поскольку и,

Единственное положительное целое число, которое делит 1, — это 1, поэтому.

Пример. Докажи, что если, то.

Я произведу линейную комбинацию, равную
1. Легко попробовать переключить цифру «3» и
«2» и отмените одно из них, чтобы получить условия с
n отменить. Фактически, это работает:

Примечание. Вы не всегда можете использовать такой метод «переключить и отрицать».
Уловка: иногда придумать линейную комбинацию — больше работы.
Есть и другие способы показать, что два числа относительно
основной.

---

Доказательство теоремы. Я использую евклидово
алгоритм. На каждом этапе алгоритма Евклида я заменяю старый
пара чисел с новой парой чисел. Доказательство пойдет это
способ.

(a) Первые два числа m и n являются линейными комбинациями m и n.

(b) На каждом шаге, если старые числа являются линейными комбинациями m и
п, значит, новые числа тоже.

(c) Согласно (a) и (b), последние два числа в алгоритме должны быть
линейные комбинации m и n.

(d) Последние два числа в алгоритме равны и 0. Следовательно,
является линейной комбинацией m и n.

Из этих четырех шагов все ясны, кроме второго. Итак, вот
доказательство шага (b).

Предположим, что мои старые числа такие, и предположим, что они
линейные комбинации m и n:

Чтобы выполнить алгоритм Евклида, я делю x на y:

Новые числа

Каждое из новых чисел представляет собой линейную комбинацию m и n.

Это доказывает шаг (b), и четыре шага выше показывают, что
линейная комбинация m и n. Затем я должен показать, что это
наименьшая положительная линейная комбинация m и n.

Предположим, что p — положительная линейная комбинация m и n:

и другие . Оба
эти числа положительные, так что. Поскольку меньше любого
положительная линейная комбинация m и n, должна быть
наименьшая положительная линейная комбинация m и n.

Другой способ доказать этот результат — дать алгоритм, который
составляет линейную комбинацию:
Расширенный алгоритм Евклида .

---

Контактная информация

Домашняя страница Брюса Икенаги

Авторские права 2019 Брюс Икенага

.