Найти нод

Запомните!

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

Любое натуральное число всегда делится на 1 и на само себя.

Число 2 — наименьшее простое число. Это единственное чётное простое число, остальные простые числа — нечётные.

Простых чисел много, и первое среди них — число 2. Однако нет последнего простого числа. В разделе «Для учёбы» вы можете скачать таблицу простых чисел до 997.

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например:

  • число 12 делится на 1, на 2, на 3, на 4, на 6, на 12;
  • число 36 делится на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.

Числа, на которые число делится нацело (для 12 это 1, 2, 3, 4, 6 и 12) называются делителями числа.

Запомните!

Делитель натурального числа a — это такое натуральное число, которое делит данное число «a» без остатка.

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

Обратите внимание, что числа 12 и 36 имеют общие делители. Это числа: 1, 2, 3, 4, 6, 12. Наибольший из делителей этих чисел — 12.

Общий делитель двух данных чисел «a» и «b» — это число, на которое делятся без остатка оба данных числа «a» и «b».

Запомните!

Наибольший общий делитель (НОД) двух данных чисел «a» и «b» — это наибольшее число, на которое оба числа «a» и «b» делятся без остатка.

Кратко наибольший общий делитель чисел «a» и «b» записывают так:
НОД (a; b).

Пример: НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример.

Д (7) = {1, 7}
Д (9) = {1, 9}
НОД (7; 9) = 1

Числа 7 и 9 имеют только один общий делитель — число 1. Такие числа называют взаимно простыми числами.

Запомните!

Взаимно простые числа — это натуральные числа, которые имеют только один общий делитель — число 1. Их НОД равен 1.

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

Чтобы найти НОД двух или более натуральных чисел нужно:

  1. разложить делители чисел на простые множители;

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа — делитель. Далее в левом столбце записываем значения частных.

Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

  1. Подчёркиваем одинаковые простые множители в обоих числах.
    28 = 2 · 2 · 7
    64 = 2 · 2 · 2 · 2 · 2 · 2
  2. Находим произведение одинаковых простых множителей и записать ответ;
    НОД (28; 64) = 2 · 2 = 4
    Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».

Первый способ записи НОД

Найти НОД 48 и 36.

Как найти НОД

  • Нахождение путём разложения на множители
  • Алгоритм Евклида

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

Нахождение путём разложения на множители

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

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

Пример 1. Найдём НОД (84, 90).

Пример 2. Найдём НОД (15, 28).

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

Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

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

Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно, НОД (27, 9) = 9.

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

  1. Из двух данных чисел большее число делят на меньшее.
  2. Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
  3. Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
  4. Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
  5. Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.

Пример 2. Найдём наибольший общий делитель чисел 140 и 96:

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

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

Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа – 48:

Эта статья посвящена такому вопросу, как нахождение наибольшего общего делителя. Сначала мы объясним, что это такое, и приведем несколько примеров, введем определения наибольшего общего делителя 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

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

Пример 3

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

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

Пример 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 Слишком сложно? Не парься, мы поможем разобраться и подарим скидку 10% на любую работу Опиши задание Доказательство 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 Определение 11

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

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

Всё ещё сложно? Наши эксперты помогут разобраться

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *