Энциклопедия 

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

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

Основные понятия

Делитель целого числа X - это другое целое число Y, на которое X разделяется без остатка. К примеру, делитель 4 - это 2, а 36 - 4, 6, 9. Кратное целого X - это такое число Y, которое делится на X без остатка. К примеру, 3 кратно 15, а 6 - 12.

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

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

Нахождение НОД

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

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

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

Нахождение НОК

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

НОК (X,Y) = X × Y / НОД(X,Y).

Например, если НОД(15,18) = 3, то НОК(15,18) = 15 × 18 / 3 = 90. Наиболее очевидный пример использования НОК - поиск общего знаменателя, который и является наименьшим общим кратным для заданных дробей.

Взаимно простые числа

Если у пары чисел нет общих делителей, то такая пара называется взаимно простой. НОД для таких пар всегда равен единице, а исходя из связи делителей и кратных, НОК для взаимно простых равен их произведению. К примеру, числа 25 и 28 взаимно просты, ведь у них нет общих делителей, а НОК(25, 28) = 700, что соответствует их произведению. Два любых неделимых числа всегда будут взаимно простыми.

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

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

Примеры из реальной жизни

Общий знаменатель дробей

Наименьшее общее кратное используется при поиске общего знаменателя нескольких дробей. Пусть в арифметической задаче требуется суммировать 5 дробей:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Для сложения дробей выражение необходимо привести к общему знаменателю, что сводится к задаче нахождения НОК. Для этого выберите в калькуляторе 5 чисел и введите значения знаменателей в соответствующие ячейки. Программа вычислит НОК (8, 9, 12, 15, 18) = 360. Теперь необходимо вычислить дополнительные множители для каждой дроби, которые определяются как соотношение НОК к знаменателю. Таким образом, дополнительные множители будут выглядеть как:

  • 360/8 = 45
  • 360/9 = 40
  • 360/12 = 30
  • 360/15 = 24
  • 360/18 = 20.

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

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Такие дроби мы можем легко суммировать и получить результат в виде 159/360. Сокращаем дробь на 3 и видим окончательный ответ - 53/120.

Решение линейных диофантовых уравнений

Линейные диофантовы уравнения - это выражения вида ax + by = d. Если отношение d / НОД(a, b) есть целое число, то уравнение разрешимо в целых числах. Давайте проверим пару уравнений на возможность целочисленного решения. Сначала проверим уравнение 150x + 8y = 37. При помощи калькулятора находим НОД (150,8) = 2. Делим 37/2 = 18,5. Число не целое, следовательно, уравнение не имеет целочисленных корней.

Проверим уравнение 1320x + 1760y = 10120. Используем калькулятор для нахождения НОД(1320, 1760) = 440. Разделим 10120/440 = 23. В результате получаем целое число, следовательно, диофантово уравнение разрешимо в целых коэффициентах.

Заключение

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

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

Найдём наибольший общий делитель чисел 24 и 35.
Делителями 24 будут числа 1, 2, 3, 4, 6, 8, 12, 24, а делителями 35 будут числа 1, 5, 7, 35.
Видим, что числа 24 и 35 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми .

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

Наибольший общий делитель (НОД) можно найти, не выписывая всех делителей данных чисел.

Разложим на множители числа 48 и 36, получим:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Из множителей, входящих в разложение первого из этих чисел, вычеркнем те, которые не входят в разложение второго числа (т. е. две двойки).
Остаются множители 2 * 2 * 3. Их произведение равно 12. Это число и является наибольшим общим делителем чисел 48 и 36. Так же находят наибольший общий делитель трёх и более чисел.

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

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

Если все данные числа делятся на одно из них, то это число и является наибольшим общим делителем данных чисел.
Например, наибольшим общим делителем чисел 15, 45, 75 и 180 будет число 15, так как на него делятся все остальные числа: 45, 75 и 180.

Наименьшее общее кратное (НОК)

Определение. Наименьшим общим кратным (НОК) натуральных чисел а и Ь называют наименьшее натуральное число, которое кратно и a, и b. Наименьшее общее кратное (НОК) чисел 75 и 60 можно найти и не выписывая подряд кратные этих чисел. Для этого разложим 75 и 60 на простые множители: 75 = 3 * 5 * 5, а 60 = 2 * 2 * 3 * 5.
Выпишем множители, входящие в разложение первого из этих чисел, и добавим к ним недостающие множители 2 и 2 из разложения второго числа (т.е. объединяем множители).
Получаем пять множителей 2 * 2 * 3 * 5 * 5, произведение которых равно 300. Это число является наименьшим общим кратным чисел 75 и 60.

Так же находят наименьшее общее кратное для трёх и более чисел.

Чтобы найти наименьшее общее кратное нескольких натуральных чисел, надо:
1) разложить их на простые множители;
2) выписать множители, входящие в разложение одного из чисел;
3) добавить к ним недостающие множители из разложений остальных чисел;
4) найти произведение получившихся множителей.

Заметим, что если одно из данных чисел делится на все остальные числа, то это число и является наименьшим общим кратным данных чисел.
Например, наименьшим общим кратным чисел 12, 15, 20 и 60 будет число 60, так как оно делится на все данные числа.

Пифагор (VI в. до н. э.) и его ученики изучали вопрос о делимости чисел. Число, равное сумме всех его делителей (без самого числа), они называли совершенным числом. Например, числа 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) совершенные. Следующие совершенные числа - 496, 8128, 33 550 336. Пифагорейцы знали только первые три совершенных числа. Четвёртое - 8128 - стало известно в I в. н. э. Пятое - 33 550 336 - было найдено в XV в. К 1983 г. было известно уже 27 совершенных чисел. Но до сих пор учёные не знают, есть ли нечётные совершенные числа, есть ли самое большое совершенное число.
Интерес древних математиков к простым числам связан с тем, что любое число либо простое, либо может быть представлено в виде произведения простых чисел, т. е. простые числа - это как бы кирпичики, из которых строятся остальные натуральные числа.
Вы, наверное, обратили внимание, что простые числа в ряду натуральных чисел встречаются неравномерно - в одних частях ряда их больше, в других - меньше. Но чем дальше мы продвигаемся по числовому ряду, тем реже встречаются простые числа. Возникает вопрос: существует ли последнее (самое большое) простое число? Древнегреческий математик Евклид (III в. до н. э.) в своей книге «начала», бывшей на протяжении двух тысяч лет основным учебником математики, доказал, что простых чисел бесконечно много, т. е. за каждым простым числом есть ещё большее простое число.
Для отыскания простых чисел другой греческий математик того же времени Эратосфен придумал такой способ. Он записывал все числа от 1 до какого-то числа, а потом вычёркивал единицу, которая не является ни простым, ни составным числом, затем вычёркивал через одно все числа, идущие после 2 (числа, кратные 2, т. е. 4, 6, 8 и т. д.). Первым оставшимся числом после 2 было 3. Далее вычёркивались через два все числа, идущие после 3 (числа, кратные 3, т. е. 6, 9, 12 и т. д.). в конце концов оставались невычеркнутыми только простые числа.

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

Чтобы найти наибольший общий делитель нескольких чисел необходимо:

  • определить множители, общие для обоих чисел;
  • найти произведение общих множителей.

Пример нахождения НОД:

Найдем НОД чисел 315 и 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Выпишем множители, общие для обоих чисел:

3. Найдем произведение общих множителей:

НОД(315; 245) = 5 * 7 = 35.

Ответ: НОД(315; 245) = 35.

Нахождение НОК

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

Чтобы найти наименьшее общее кратное нескольких чисел необходимо:

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

Пример нахождения НОК:

Найдем НОК чисел 236 и 328:

1. Разложим числа на простые множители:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Выпишем множители, входящие в разложение одного из чисел и допишем к ним недостающие множители из разложения второго числа:

2; 2; 59; 2; 41.

3. Найдем произведение получившихся множителей:

НОК(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Ответ: НОК(236; 328) = 19352.

Для нахождения НОД (наибольшего общего делителя) двух чисел необходимо:

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

3. Найти произведение общих простых множителей.

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

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

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

3. Вычислить произведение полученных множителей.

Признаки делимости натуральных чисел.

Числа, делящиеся без остатка на 2, называются четными .

Числа, которые не делятся без остатка на 2, называются нечетными .

Признак делимости на 2

Если запись натурального числа оканчивается четной цифрой, то это число делится без остатка на 2, а если запись числа оканчивается нечетной цифрой, то это число не делится без остатка на 2.

Например, числа 6 0 , 30 8 , 8 4 делятся без остатка на 2, а числа 5 1 , 8 5 , 16 7 не делятся без остатка на 2.

Признак делимости на 3

Если сумма цифр числа делится на 3, то и число делится на 3; если сумма цифр числа не делится на 3, то и число не делится на 3.

Например, выясним, делится ли на 3 число 2772825. Для этого подсчитаем сумму цифр этого числа: 2+7+7+2+8+2+5 = 33 - делится на 3. Значит, число 2772825 делится на 3.

Признак делимости на 5

Если запись натурального числа оканчивается цифрой 0 или 5, то это число делится без остатка на 5. Если же запись числа оканчивается иной цифрой, то число без остатка на 5 не делится.

Например, числа 1 5 , 3 0 , 176 5 , 47530 0 делятся без остатка на 5, а числа 1 7 , 37 8 , 9 1 не делятся.

Признак делимости на 9

Если сумма цифр числа делится на 9, то и число делится на 9; если сумма цифр числа не делится на 9, то и число не делится на 9.

Например, выясним, делится ли на 9 число 5402070. Для этого подсчитаем сумму цифр этого числа: 5+4+0+2+0+7+0 = 16 - не делится на 9. Значит, число 5402070 не делится на 9.

Признак делимости на 10

Если запись натурального числа оканчивается цифрой 0, то это число делится без остатка на 10. Если запись натурального числа оканчивается другой цифрой, то оно не делится без остатка на 10.

Например, числа 4 0 , 17 0 , 1409 0 делятся без остатка на 10, а числа 1 7 , 9 3 , 1430 7 - не делятся.

Правило нахождения наибольшего общего делителя (НОД).

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

2) из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел;

3) найти произведение оставшихся множителей.

Пример. Найдем НОД (48;36). Воспользуемся правилом.

1. Разложим числа 48 и 36 на простые множители.

48 = 2 · 2 · 2 · 2 · 3

36 = 2 · 2 · 3 · 3

2. Из множителей, входящих в разложение числа 48 вычеркнем те, которые не входят в разложение числа 36.

48 = 2 · 2 · 2 · 2 · 3

Остаются множители 2, 2 и 3.

3. Перемножим оставшиеся множители и получим 12. Это число и является наибольшим общим делителем чисел 48 и 36.

НОД (48;36) = 2 · 2 · 3 = 12.

Правило нахождения наименьшего общего кратного (НОК).

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

1) разложить их на простые множители;

2) выписать множители, входящие в разложение одного из чисел;

3) добавить к ним недостающие множители из разложений остальных чисел;

4) найти произведение получившихся множителей.

Пример. Найдем НОК (75;60). Воспользуемся правилом.

1. Разложим числа 75 и 60 на простые множители.

75 = 3 · 5 · 5

60 = 2 · 2 · 3 · 3

2. Выпишем множители, входящие в разложение числа 75: 3, 5, 5.

НОК (75;60) = 3 · 5 · 5 · …

3. Добавим к ним недостающие множители из разложения числа 60, т.е. 2, 2.

НОК (75;60) = 3 · 5 · 5 · 2 · 2

4. Найдем произведение получившихся множителей

НОК (75;60) = 3 · 5 · 5 · 2 · 2 = 300.

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

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

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

Наибольший общий делитель двух целых чисел – это наибольшее целое число, делящее два данных целых числа.

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

Приведем пример наибольшего общего делителя (НОД) двух целых чисел. Наибольший общий делитель чисел 6 и −15 равен 3 . Обоснуем это. Запишем все делители числа шесть: ±6 , ±3 , ±1 , а делителями числа −15 являются числа ±15 , ±5 , ±3 и ±1 . Теперь можно найти все общие делители чисел 6 и −15 , это числа −3 , −1 , 1 и 3 . Так как −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

Определение наибольшего общего делителя трех и большего количества целых чисел аналогично определению НОД двух чисел.

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

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

Наибольший общий делитель n целых чисел a 1 , a 2 , …, a n мы будем обозначать как НОД(a 1 , a 2 , …, a n) . Если найдено значение b наибольшего общего делителя этих чисел, то можно записать НОД(a 1 , a 2 , …, a n)=b .

В качестве примера приведем НОД четырех целых чисел −8 , 52 , 16 и −12 , он равен 4 , то есть, НОД(−8, 52, 16, −12)=4 . Это можно проверить, записав все делители данных чисел, выбрав из них общие и определив наибольший общий делитель.

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

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

Свойства наибольшего общего делителя, алгоритм Евклида

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

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

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

    Это свойство НОД напрямую следует из определения наибольшего общего делителя.

    Если a делится на b , то множество общих делителей чисел a и b совпадает со множеством делителей числа b , в частности, НОД(a, b)=b .

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

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

    Если a=b·q+c , где a , b , c и q – целые числа, то множество общих делителей чисел a и b совпадает со множеством общих делителей чисел b и c , в частности, НОД(a, b)=НОД(b, c) .

    Обоснуем это свойство НОД.

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

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

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

    Итак, пусть для двух ненулевых целых положительных чисел a и b справедлив ряд равенств

    заканчивающийся, когда r k+1 =0 (что неизбежно, так как b>r 1 >r 2 >r 3 , … - ряд убывающих целых чисел, и этот ряд не может содержать более чем конечное число положительных чисел), тогда r k – это наибольший общий делитель чисел a и b , то есть, r k =НОД(a, b) .

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

    Докажем сначала, что r k является общим делителем чисел a и b , после чего покажем, что r k не просто делитель, а наибольший общий делитель чисел a и b .

    Будем двигаться по записанным равенствам снизу вверх. Из последнего равенства можно сказать, что r k−1 делится на r k . Учитывая этот факт, а также предыдущее свойство НОД, предпоследнее равенство r k−2 =r k−1 ·q k +r k позволяет утверждать, что r k−2 делится на r k , так как и r k−1 делится на r k и r k делится на r k . По аналогии из третьего снизу равенства заключаем, что r k−3 делится на r k . И так далее. Из второго равенства получаем, что b делится на r k , а из первого равенства получаем, что a делится на r k . Следовательно, r k является общим делителем чисел a и b .

    Осталось доказать, что r k =НОД(a, b) . Для достаточно показать, что любой общий делитель чисел a и b (обозначим его r 0 ) делит r k .

    Будем двигаться по исходным равенствам сверху вниз. В силу предыдущего свойства из первого равенства следует, что r 1 делится на r 0 . Тогда из второго равенства получаем, что r 2 делится на r 0 . И так далее. Из последнего равенства получаем, что r k делится на r 0 . Таким образом, r k =НОД(a, b) .

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

    Пусть a и b – целые числа, одновременно не равные нулю, тогда существуют такие целые числа u 0 и v 0 , то справедливо равенство НОД(a, b)=a·u 0 +b·v 0 . Последнее равенство представляет собой линейное представление наибольшего общего делителя чисел a и b , это равенство называют соотношением Безу, а числа u 0 и v 0 – коэффициентами Безу.

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

    По алгоритму Евклида мы можем записать следующие равенства

    Из первого равенства имеем r 1 =a−b·q 1 , и, обозначив 1=s 1 и −q 1 =t 1 , это равенство примет вид r 1 =s 1 ·a+t 1 ·b , причем числа s 1 и t 1 - целые. Тогда из второго равенства получим r 2 =b−r 1 ·q 2 = b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b . Обозначив −s 1 ·q 2 =s 2 и 1−t 1 ·q 2 =t 2 , последнее равенство можно записать в виде r 2 =s 2 ·a+t 2 ·b , причем s 2 и t 2 – целые числа (так как сумма, разность и произведение целых чисел является целым числом). Аналогично из третьего равенства получим r 3 =s 3 ·a+t 3 ·b , из четвертого r 4 =s 4 ·a+t 4 ·b , и так далее. Наконец, r k =s k ·a+t k ·b , где s k и t k - целые. Так как r k =НОД(a, b) , и, обозначив s k =u 0 и t k =v 0 , получим линейное представление НОД требуемого вида: НОД(a, b)=a·u 0 +b·v 0 .

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

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

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

    Пусть p – любой общий делитель чисел a и b , тогда НОД(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) , откуда и следует доказываемое равенство.

    Только что доказанное свойство наибольшего общего делителя лежит в основе .

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

    Наибольший общий делитель чисел a 1 , a 2 , …, a k равен числу d k , которое находится при последовательном вычислении НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k-1 , a k)=d k .

    Доказательство базируется на следствии из алгоритма Евклида. Общие делители чисел a 1 и a 2 совпадают с делителями d 2 . Тогда общие делители чисел a 1 , a 2 и a 3 совпадают с общими делителями чисел d 2 и a 3 , следовательно, совпадают с делителями d 3 . Общие делители чисел a 1 , a 2 , a 3 и a 4 совпадают с общими делителями d 3 и a 4 , следовательно, совпадают с делителями d 4 . И так далее. Наконец, общие делители чисел a 1 , a 2 , …, a k совпадают с делителями d k . А так как наибольшим делителем числа d k является само число d k , то НОД(a 1 , a 2 , …, a k)=d k .

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

Список литературы.

  • Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
  • Виноградов И.М. Основы теории чисел.
  • Михелович Ш.Х. Теория чисел.
  • Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.