Как найти нод из нок. Общий делитель и кратное

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

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

Делитель целого числа 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. В результате получаем целое число, следовательно, диофантово уравнение разрешимо в целых коэффициентах.

Заключение

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

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

Числа, делящиеся без остатка на 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.

Второе число: b=

Разделитель разрядов Без разделителя пробел " ´

Результат:

Наибольший общий делитель НОД(a ,b )=6

Наименьшее общее кратное НОК(a ,b )=468

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

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

Целые числа a и b называются взаимно простыми , если они не имеют никаких общих делителей кроме +1 и −1.

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

Пусть даны два положительных числа a 1 и a 2 1). Требуется найти общий делитель этих чисел, т.е. найти такое число λ , которое делит числа a 1 и a 2 одновременно. Опишем алгоритм.

1) В данной статье под словом число будем понимать целое число.

Пусть a 1 ≥ a 2 , и пусть

где m 1 , a 3 некоторые целые числа, a 3 <a 2 (остаток от деления a 1 на a 2 должен быть меньше a 2).

Предположим, что λ делит a 1 и a 2 , тогда λ делит m 1 a 2 и λ делит a 1 −m 1 a 2 =a 3 (Утверждение 2 статьи "Делимость чисел. Признак делимости"). Отсюда следует, что всякий общий делитель a 1 и a 2 является общим делителем a 2 и a 3 . Справедливо и обратное, если λ общий делитель a 2 и a 3 , то m 1 a 2 и a 1 =m 1 a 2 +a 3 также делятся на λ . Следовательно общий делитель a 2 и a 3 есть также общий делитель a 1 и a 2 . Так как a 3 <a 2 ≤a 1 , то можно сказать, что решение задачи по нахождению общего делителя чисел a 1 и a 2 сведено к более простой задаче нахождения общего делителя чисел a 2 и a 3 .

Если a 3 ≠0, то можно разделить a 2 на a 3 . Тогда

,

где m 1 и a 4 некоторые целые числа, (a 4 остаток от деления a 2 на a 3 (a 4 <a 3)). Аналогичными рассуждениями мы приходим к выводу, что общие делители чисел a 3 и a 4 совпадают с общими делителями чисел a 2 и a 3 , и также с общими делителями a 1 и a 2 . Так как a 1 , a 2 , a 3 , a 4 , ... числа, постоянно убывающие, и так как существует конечное число целых чисел между a 2 и 0, то на каком то шаге n , остаток от деления a n на a n+1 будет равен нулю (a n+2 =0).

.

Каждый общий делитель λ чисел a 1 и a 2 также делитель чисел a 2 и a 3 , a 3 и a 4 , .... a n и a n+1 . Справедливо и обратное, общие делители чисел a n и a n+1 являются также делителями чисел a n−1 и a n , .... , a 2 и a 3 , a 1 и a 2 . Но общий делитель чисел a n и a n+1 является число a n+1 , т.к. a n и a n+1 без остатка делятся на a n+1 (вспомним, что a n+2 =0). Следовательно a n+1 является и делителем чисел a 1 и a 2 .

Отметим, что число a n+1 является наибольшим из делителей чисел a n и a n+1 , так как наибольший делитель a n+1 является сам a n+1 . Если a n+1 можно представить в виде произведения целых чисел, то эти числа также являются общими делителями чисел a 1 и a 2 . Число a n+1 называют наибольшим общим делителем чисел a 1 и a 2 .

Числа a 1 и a 2 могут быть как положительными, так и отрицательными числами. Если один из чисел равен нулю, то наибольший общий делитель этих чисел будет равен абсолютной величине другого числа. Наибольший общий делитель нулевых чисел не определен.

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

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

Найти наибольший общий делитель двух чисел 630 и 434.

• Шаг 1. Делим число 630 на 434. Остаток 196.
• Шаг 2. Делим число 434 на 196. Остаток 42.
• Шаг 3. Делим число 196 на 42. Остаток 28.
• Шаг 4. Делим число 42 на 28. Остаток 14.
• Шаг 5. Делим число 28 на 14. Остаток 0.

На шаге 5 остаток от деления равен 0. Следовательно наибольший общий делитель чисел 630 и 434 равен 14. Заметим, что числа 2 и 7 также являются делителями чисел 630 и 434.

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

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

Теорема 1. Если a 1 и a 2 взаимно простые числа, а λ какое то число, то любой общий делитель чисел λa 1 и a 2 является также общим делителем чисел λ и a 2 .

Доказательство. Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя чисел a 1 и a 2 (см. выше).

.

Из условия теоремы следует, что наибольшим общим делителем чисел a 1 и a 2 , и следовательно a n и a n+1 является 1. Т.е. a n+1 =1.

Умножим все эти равенства на λ , тогда

.

Пусть общий делитель a 1 λ и a 2 есть δ . Тогда δ входит множителем в a 1 λ , m 1 a 2 λ и в a 1 λ -m 1 a 2 λ =a 3 λ (см. "Делимость чисел",Утверждение 2). Далее δ входит множителем в a 2 λ и m 2 a 3 λ , и, следовательно, входит множителем в a 2 λ -m 2 a 3 λ =a 4 λ .

Рассуждая так мы убеждаемся, что δ входит множителем в a n−1 λ и m n−1 a n λ , и, следовательно, в a n−1 λ −m n−1 a n λ =a n+1 λ . Так как a n+1 =1, то δ входит множителем в λ . Следовательно число δ является общим делителем чисел λ и a 2 .

Рассмотрим частные случаи теоремы 1.

Следствие 1. Пусть a и c простые числа относительно b . Тогда их произведение ac является простым числом относительно b .

Действительно. Из теоремы 1 ac и b имеют тех же общих делителей, что и c и b . Но числа c и b взаимно простые, т.е. имеют единственный общий делитель 1. Тогда ac и b также имеют единственный общий делитель 1. Следовательно ac и b взаимно простые.

Следствие 2. Пусть a и b взаимно простые числа и пусть b делит ak . Тогда b делит и k .

Действительно. Из условия утверждения ak и b имеют общий делитель b . В силу теоремы 1, b должен быть общим делителем b и k . Следовательно b делит k .

Следствие 1 можно обобщить.

Следствие 3. 1. Пусть числа a 1 , a 2 , a 3 , ..., a m простые относительно числа b . Тогда a 1 a 2 , a 1 a 2 ·a 3 , ..., a 1 a 2 a 3 ···a m , произведение этих чисел простое относительно числа b .

2. Пусть имеем два ряда чисел

таких, что каждое число первого ряда простое по отношению каждого числа второго ряда. Тогда произведение

Требуется найти такие числа, которые делятся на каждое из этих чисел.

Если число делится на a 1 , то оно имеет вид sa 1 , где s какое-нибудь число. Если q есть наибольший общий делитель чисел a 1 и a 2 , то

где s 1 - некоторое целое число. Тогда

является наименьшим общим кратным чисел a 1 и a 2 .

a 1 и a 2 взаимно простые, то наименьшее общее кратное чисел a 1 и a 2:

Нужно найти наименьшее общее кратное этих чисел.

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

В частном случае, когда числа a 1 , a 2 , a 3 ,...,a m взаимно простые, то наименьшее общее кратное чисел a 1 , a 2 как было показано выше имеет вид (3). Далее, так как a 3 простое по отношению к числам a 1 , a 2 , тогда a 3 простое по отношению числа a 1 ·a 2 (Следствие 1). Значит наименьшее общее кратное чисел a 1 ,a 2 ,a 3 является число a 1 · a 2 ·a 3 . Рассуждая аналогичным образом мы приходим к следующим утверждениям.

Утверждение 1. Наименьшее общее кратное взаимно простых чисел a 1 , a 2 , a 3 ,...,a m равен их произведению a 1 ·a 2 ·a 3 ···a m .

Утверждение 2. Любое число, которое делится на каждое из взаимно простых чисел a 1 , a 2 , a 3 ,...,a m делится также на их произведение a 1 ·a 2 ·a 3 ···a m .

1. Каждое натуральное число р ≠ 1 имеет по крайней мере два делителя: 1 и p .

Определение 6. Натуральное число р ≥ 1 называется простым, если оно не имеет делителей, отличных от 1 и р .

Например, числа 7, 13, 19 являются простыми, так как каждое из них делится только само на себя и на единицу.

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

Например, 12 – составное число, так как имеет делители: 1, 2, 3, 4, 6, 12.

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

I кл. – число 1 (один делитель);

II кл. – простые числа (два делителя);

III кл. – составные числа (более двух делителей).

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

IV кл. – число 0 (бесконечно много делителей).

Теорема 16. (О существовании простого делителя .) Если d ≠ 1 – наименьший делитель натурального числа n > 1, то d – простое число.

Доказательство. Будем рассуждать методом от противного. Предположим, что d – составное число. Тогда, по определению 7, d делится на 1, d и некоторое число t , где 1 < t < d . Следовательно, имеем и

, а по транзитивности отношения делимости это означает, что

. Получили противоречие с тем, что d – наименьший делитель числа п. Тем самым теорема доказана.

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

Теорема 17. Множество простых чисел бесконечно.

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

– все простые числа и других простых чисел нет. Рассмотрим число

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

I кл., так как п > 1;

II кл., так как п больше любого простого числа p i (i = 1, 2, ..., k ). Остается предположить, что

III кл., то есть n – составное число. Тогда, по теореме 16, п должно делиться хотя бы на одно из простых чисел p i (i = 1, 2, ..., k ). Пусть

, 1 ≤s ≤ k . Рассматривая равенство (10) замечаем, что в нем

,, а значит, по теореме 2 о делимости разности,

, что невозможно. Полученное противоречие доказывает теорему.

2. Поскольку множество простых чисел бесконечно, то самого большого простого числа нет. Однако математики старались и стараются до сих пор обнаружить простоту тех или иных больших чисел. К концу прошлого века наибольшим известным простым числом было 39-значное число 2 127 – 1. В 50-60-х годах нашего столетия с помощью ЭВМ было найдено несколько новых простых чисел-гигантов.

До конца 70-х годов наибольшим известным простым числом было число 2 11213 – 1, имеющее в десятичной записи 3376 знаков. В 1992 году англичане установили простоту числа, состоящего из 227832 знаков. Затем американцы в течение двух лет с помощью самых высокопроизводительных на то время ЭВМ анализировали более четверти миллиона больших чисел и открыли простое число 2 859433 – 1, которое содержит в записи 258716 знаков. Чтобы представить это число нагляднее, заметим, что для записи его через принтер понадобилось 8 больших газетных страниц. Это число является самым большим из известных нам простых чисел.

Некоторые пары простых чисел отличаются друг от друга лишь на 2 единицы. Например: 3 и 5; 11 и 13; 17 и 19; 29 и 31 и т.д. Такие пары простых чисел называют близнецами. Есть гипотеза о том, что существует бесконечно много пар близнецов.

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

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

Доказательство. Рассмотрим k последовательно идущих в натуральном ряду чисел:

(k + 1)! + 2; (k + 1)! + 3; (k + 1)! + 4; ... ; (k + 1)! + (k + 1).

Легко заметить, что все эти числа составные. Действительно, первое из них делится на 2, второе – на 3, третье (последнее) – на k + 1. Теорема доказана.

Для составления таблиц простых чисел существуют различные приемы. Наиболее известный из них – «решето Эратосфена» – был предложен в III в. до н.э. древнегреческим ученым Эратосфеном и состоит в следующем.

Пусть требуется составить таблицу простых чисел, не превосходящих п. Для определенности положим п = 50, хотя в любом случае рассуждения проводятся аналогично.

Выпишем все натуральные числа от 1 до 50 включительно. Затем вычеркнем из этого списка 1, так как 1, по определению, не является простым числом. Первое из оставшихся чисел – 2 – число простое. Выделим его, а все кратные ему числа (это четные числа) вычеркнем. Первое из оставшихся чисел – 3 – число простое. Выделим его, а все кратные ему числа вычеркнем. При этом некоторые из чисел окажутся вычеркнутыми ранее. Повторяя этот процесс, через конечное число шагов мы отсеем все составные числа, а простые окажутся выделенными.

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

Всвязи с описанным процессом возникает вопрос: на каком этапе можно прекратить вычисления и сделать вывод о том, что все оставшиеся числа будут простыми? Ответ на этот вопрос дает теорема итальянского математика Фибоначчи (1170-1228 гг.).

Теорема 19. Если натуральное число п не имеет простых делителей р ≤

, топ – простое число.

Доказательство. Рассуждая методом от противного, предположим, что условие теоремы выполнено, но п – составное число. Тогда п = ab , где 1 < a < п , 1 < b < п. Числа а и b не могут быть одновременно больше, чем

, так как тогда а b было бы больше, чем п . Пусть, например, а ≤

. Посколькуа > 1, то, по теореме 16, оно имеет простой делитель р , то есть

и

. Тогда, по транзитивности отношения делимости,

, гдер ≤ а ≤

. Но это противоречит условию теоремы, так как п не имеет простых делителей р ≤

. Теорема доказана.

Следует отметить тот факт, что многие математики предлагали ряд способов, рассчитанных на уменьшение объема выкладок при установлении простоты чисел. Примером служит теорема Софии Жермен (Франция, 1776-1831 гг.).

Теорема 20. Число п 4 + 4 при п > 1 всегда составное.

Доказательство. Преобразуем число п 4 + 4 тождественно: п 4 + 4 = п 4 + 4 + 4п 2 – 4п 2 = (п 4 + 4п 2 + 4) – 4п 2 = (п 2 + 2) 2 – 4п 2 = (п 2 + 2 – 2п )(п 2 + 2 + 2п ).

Очевидно, что число п 2 + 2n + 2 > 2 при любом натуральном п > l. Аналогично, п 2 – 2п + 2 > 2 при п 2 – 2п > 0, или (п – 2)п > 0. Так как п > 1, то п – 2 ≥ 0 и неравенство (п – 2)п ≥ 0 выполняется тождественно.

Итак, число п 4 + 4 представимо в виде произведения двух множителей, каждый из которых есть натуральное число, большее или равное 2. Следовательно, число п 4 + 4 составное и теорема доказана.

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

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

Доказательство проведем методом математической индукции по числу множителей. Сначала рассмотрим произведение двух множителей a 1 и a 2 . Пусть

. Здесь возможны два случая:

или

. Если

, то утверждение доказано. Если a 1 не делится на р , то НОД(a 1 ;р ) = 1, поскольку простое число взаимно просто со всеми не делящимися на него числами. Но если

и (a 1 ;p ) = 1, то, по теореме 12,

.

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

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

в виде двух множителей:

Но для двух множителей теорема доказана, и значит, одно из чисел – m или a k – должно делиться на р. Если

, то теорема доказана. Если

, то, по предположению индукции, хотя бы одно из чисел

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

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

Доказательство. Докажем сначала существование разложения. Доказательство проведем методом математической индукции.

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

Предположим, что разложение на простые множители существует для всех натуральных чисел п < k , где k – некоторое произвольно выбранное натуральное число. Докажем, что и для числа n = k существует такое разложение.

Если k – простое число, то для него существование разложения можно считать доказанным. Если же k – число составное, то его можно представить в виде произведения:

k = а · b , где a < k и b < k . (11)

По предположению индукции, для чисел а и b разложение существует, то есть

и

, (12)

где

– простые числа. Подставляя разложения (12) в равенство (11), получим разложение числаk в произведение простых множителей:

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

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

Для простого числа п = 2 указанное представление единственно.

Предположим, что для всех натуральных чисел п < k разложение на простые множители единственно. Докажем единственность разложения для числа n = k .

Пусть наряду с разложением (13) имеется второе разложение числа k :

, (14)

где

– простые числа.

Из равенств (13) и (14) получаем равенство

Левая часть равенства (15) делится на простое число р 1 . Следовательно, и правая часть тоже делится на р 1 . Согласно теореме 21, хотя бы один из множителей произведения

должен делиться нар 1 . Общность рассуждений не нарушится, если будем считать, что

. Так какq 1 – простое число и р 1 > 1, то q 1 = р 1 .

Так как числа

и

меньше, чемk , то, по предположению индукции, из равенства (16) следует, что р 2 = q 2 , , р 3 = q 3 , …, p s = q t , s = t . Таким образом, в равенстве (15)

p 1 = q 1 , р 2 = q 2 , …, p s = q t , (s = t ),

а значит, разложение числа k на простые множители единственно. Основная теорема арифметики доказана.

Согласно основной теореме арифметики, всякое составное натуральное число может быть представлено в виде произведения простых чисел. При этом среди простых множителей могут встречаться одинаковые. Пусть, например, р 1 встречается раз,р 2 – раз, ..., p k – раз. Тогда разложение числа п на простые множители можно записать в следующем виде:

, (17)

Определение 8. Представление составного числа п в виде (17), где простые числа

расположены в порядке возрастания

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

На практике каноническое разложение числа п находится следующим образом. Проверяем, делится ли число п на различные простые числа: 2, 3, 5, 7,... в порядке их возрастания. Как только встретится первое простое число р i , являющееся делителем числа п , то п следует разделить на р i , а частное снова испытывать на делимость простыми числами, причем испытания следует начинать с числа р i и т.д. Если при испытании окажется, что п не имеет простых делителей

, то, согласно теореме Фибоначчи (теорема 19), п – простое число.

Пример. Найти каноническое разложение числа 9702.

Процесс разложения числа на простые множители записывают обычно следующим образом:

Ответ: 9702 = 2 · 3 2 · 7 2 · 11.

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

,

,

в которых некоторые из чисел и могут быть нулями.

Несложно заметить, что

НОД(а ; b ) = , (18)

HOК(а ; b ) = . (19)

Справедливость этих равенств вытекает из теорем 7 и 14, соответственно. Формулы (18) и (19) легко обобщаются на случай п чисел. Если даны числа

, имеющие канонические разложения:

(20)

то НОД и НОК этих чисел представляются выражениями.

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

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

Наибольший общий делитель – это наибольшее натуральное число, на которое делятся без остатка числа a и b .

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

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

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

Пример: найдем НОД чисел 48 и 36. Для этого находим делители обоих чисел (рис.1):

Итак, 48 = 2 · 2 · 2· 2 · 3, а 36 = 2 · 2 · 3 · 3.

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

В столбце с вычеркнутыми числами остаются множители 2 · 2 · 3. Их произведение равно 12. Это число и является НОД чисел 48 и 36. То есть 12 - наибольшее общее число, на которое делятся 48 и 36.

Если НОД натуральных чисел равен 1, то эти числа называют взаимно простыми (например, числа 24 и 35).

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

Наименьшее общее кратное чисел a и b – это наименьшее натуральное число, которое делится на оба эти числа.

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

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

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

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

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

Пример: найдем НОК тех же чисел 48 и 36.

Как и в случае с НОД, сначала находим делители обоих чисел. Впрочем, мы уже нашли их в предыдущем примере (рис.3):

Из разложения второго числа вычеркиваем множители, которые входят в разложение первого числа (рис.4).

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

2 ∙ 2 ∙ 2 ∙ 2 ∙ 3 ∙ 3 = 144.

Число 144 – это и есть НОК чисел 48 и 36. То есть 144 – это минимальное число, которое делится без остатка и на 48, и на 36.