НОД и НОК

Локация Главная страница Карта сайта

Математика - это здорово!

Здесь представлены основные формулы, определения, теоремы и опорные примеры по  теме "Делимость". Дан алгоритм определения количества всех делителей числа. Продемонстрированы основные способы нахождения НОД и НОК: разложение на простые множители и последовательное деление (алгоритм Евклида). Разобраны примеры решения уравнений в целых числах.

Основные формулы, определения, теоремы и опорные примеры

Если натуральное число А делится на натуральное число В с остатком r , то это значит, что А=Вˑn+r, где А – делимое,  В – делитель, n-частное. Остаток может равняться 0, 1, 2, …, В – 1.

Если r  = 0, то говорят, что А кратно В или что А делится нацело на В, а число В является делителем числа А или что В делит А.

 Делители и кратные

18 делится на 3,      3 – делитель числа 18    18 – кратное числа 3

1, 2, 3, 6, 9, 18 – все делители числа 18.       0, 3, 6, 9, 12, 15, 18, …˗кратные числа 3

Натуральные числа бывают трех видов: имеющие только один делитель (такое число только одно – это 1), имеющие два делителя и имеющие более двух делителей. Если натуральное число   имеет только два делителя 1 и само число , то оно называется простым. Например, 19 делится без остатка только на 19 и на 1: 19/19=1 и 19/1 = 19. Ответ на вопрос, зачем нужно знать простые числа, также прост: чтобы не делать бесплодных попыток найти несуществующие делители.

Простые числа в пределах 100

Обратите внимание, что числа из каждого десятка расположены в одном столбике. Рекомендуется так их и запомнить постепенно. Сначала до 20, потом до 30, ...., 100. В последнем десятке только одно число 97.

 Если натуральное число   имеет более двух делителей, то оно называется составным. Например, 4, 6, 12 – составные числа. Число 1 не является ни простым, ни составным.  Чтобы распознать простое число, нужно проверить его делимость на все простые числа, квадрат которых не превосходит данное число. Делать это стоит, естественно, только в тех случаях, когда не видно сразу, что число составное. Алгоритм распознавания составного числа: чтобы показать, что данное число составное, достаточно представить его в виде произведения двух натуральных чисел, ни одно из которых не равно 1.

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

Пример 1. Найти все делители числа 50.

Решение. Заметим, что число 1 – делитель любого числа, в том числе и 50. Раскладываем 50 на простые множители: 50=2ˑ5². 2 и 5 -  простые делители 50. Перемножением же простых множителей по два и по три получаем остальные (составные) делители 50. Ответ: 1, 2, 5, 10, 25, 50.

Алгоритм определения количества всех делителей числа:

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

2) Увеличим на единицу показатель степени каждого простого множителя;

3) Перемножим увеличенные показатели всех простых множителей;

4) В результате получим количество всех делителей данного числа.

Так как 50=2ˑ5² , то количество делителей числа 50 равно (1+1)ˑ(2+1) = 6.

Общим делителем нескольких чисел называется число, на которое все данные числа делятся без остатка. Например, числа 25 и 35 имеют общие делители: 1 и 5. Среди всех общих делителей  всегда имеется наибольший.  Это число называется наибольшим общим делителем (НОД). Так, НОД(25; 35) = 5.

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

Первый способ – разложение на простые множители.

Пример 2. Найти НОД чисел 210, 1260 и 245.

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

210=2ˑ3ˑ5ˑ7; 1260=2²ˑ3²ˑ5ˑ7; 245=5ˑ7².  НОД (210, 1260, 245) =5ˑ7=35.

Ответ: НОД (210, 1260, 245) =35.

Второй способ – последовательное деление. Он называется еще алгоритмом Евклида. Чтобы найти НОД двух чисел, делят большее число на меньшее, и если получается остаток, не равный 0, то делят меньшее число на этот остаток; если снова получается остаток,не равный 0, то делят первый остаток на второй. Так продолжают делать до тех пор, пока в остатке не получится нуль. Последний делитель и есть НОД данных чисел.

Пример 3. Найти НОД(391; 299).

Решение. Разделив число 391 на 299, получим в остатке 92. Разделив 299 на 92, получим в остатке 23. Разделив 92 на 23, получим в остатке 0. Следовательно, НОД(391; 299) = 23. Записи удобно расположить расположить так. Ответ: НОД(391; 299) = 23.

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

Два или несколько чисел, наибольший общий делитель которых равен единице, называются взаимно простыми. НОД (15; 22) =1, следовательно, 15 и 22 взаимно просты.

НОД (18; 15) = 3, следовательно, 18 и 15 не взаимно просты.

Если НОД (А; В) = 1, то дробь А/В несократимая.

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

Например, числа 12, 24, 36, …  являются общими кратными чисел 3 и 4.

Из всех общих кратных можно найти наименьшее.

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

Например, НОК (6; 15; 20) = 60, так как никакое натуральное число, меньшее 60, не делится на 6, 15 и 20 одновременно, а 60 делится на эти числа. Укажем два способа нахождения НОК.

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

Пример 4. Найти НОК(72; 108).

Решение. Разложим данные числа на множители:72 = 2³ˑ3², 108 = 2²ˑ3³.

Выпишем все множители числа 108 (это удобно, так 108 больше 72) и, добавив множитель 2, который еще дополнительно имеется в числе 72, получим НОК(72; 108) = 216. .

Ответ: НОК(72; 108) = 216.

Если большее из данных чисел делится на все остальные, то оно и будет наименьшим общим кратным этих чисел. Например, НОК(60; 120; 40) = 120.

Если никакая пара данных чисел не имеет общих множителей, то для нахождения НОК данных чисел их нужно перемножить. Например, НОК(7; 8; 11) =616.

Второй способ. Известно, что , НОК(a,b) = ab/НОД(a,b), т. е. НОК двух чисел равно произведению этих чисел, деленному на их НОД.

Пример 5. Найти НОК(360; 70).

Решение. Так как НОД (360; 70) = 10, то  НОК(360; 70) =25200:10=2520 .

Ответ: НОК(360; 70) = 2520.

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

Пример 6. Докажите, что два соседних натуральных числа n и n + 1 являются взаимно простыми.

Доказательство.В основе алгоритма Евклида лежит следующее соображение: любой общий делитель чисел a и b (a>b) делит также число a –  b. Верно и обратное: общий делитель чисел b и a – b делит число a. Значит, НОД(a,b) = НОД(b,a-b). Тогда  НОД(n,n+1) = НОД(n,1) = 1, т. е. n и n +1 взаимно просты, чтд.

Пример 7. Найдите все такие целые x и y, что  а) xy = 7; б) x²+xy =15 ; в) x² - y² = 9.

Решение.

а) Правая часть данного уравнения представляет число 7, а левая –  произведение двух множителей. Число 7 – простое, поэтому его можно представить в виде произведения двух целых множителей только следующими способами: 1ˑ7, 7ˑ1,  -1ˑ(-7), -7ˑ(-1).  Значит, xy = 7 при: 1) x = 1 и y= 7; 2) x= 7 и y= 1; 3) x= -1 и y = -7; 4) x= -7 и y = -1.

Ответ:(1;7),(7;1),(-1;-7),(-7:-1).

б) Разложим левую часть уравнения на множители. Получим: x(x+y) = 15. Простые множители числа 15 – это 3 и 5. Поэтому число 15 можно представить в виде произведения двух целых множителей только следующими способами: 1ˑ15,   15ˑ1, 3ˑ5, 5ˑ3,  -1ˑ(-15),   -15ˑ(-1), -3ˑ(-5), -5ˑ(-3). Значит, имеем систему и ответ.

в) Разложим левую часть уравнения на множители. Получим: (x-y)(x+y) = 9. Значит, имеем систему и ответ

Задачи на делимость

1. В магазине фундук продают в пачках по 105 г., а фисташки в пачках по 120 г. Какое наименьшее количество пачек орехов надо купить, чтобы фундука и фисташек было поровну (по массе)? Решение

2. Сколько чисел от 1 до 100, у которых в разложении на простые множители число 3 входит нечётное число раз? Решение

3. Число 899 представили в виде произведения двух натуральных чисел. Чему равна сумма этих двух множителей? Решение

4. После урока о простых числах семиклассник Сережа поделился с учителей гипотезой: если число P простое, то число 2P + 1 тоже простое. Верна эта гипотеза или нет? Если нет, то какое наименьшее число P можно привести в качестве контрпримера? Решение

 5. В доме у сороконожки 30 ящиков с носками. Всего 199 носков. В некоторых ящиках лежит по N носков, а в остальных — по 5 носков. Чему равно N? Решение

6. Маша проверяет, какие натуральные числа от 1 до 100 имеют ровно 3 делителя. Сколько таких чисел должна обнаружить Маша? Решение

7. В ряд выписано N чисел, каждое следующее число на 6 больше предыдущего. Любые два выписанных числа взаимно простые. При каком наибольшем N такое возможно? Решение

 8. Число 90000 представили в виде произведения двух натуральных чисел. Сумма этих множителей равна 1923. Найдите меньший из этих множителей. Решение

9. Какое наибольшее количество цифр может быть в числе, в котором среди любых двух соседних цифр одна из них делится на другую и никакие цифры не повторяются? Решение

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

11. Произведение возрастов троих людей из семьи равно 2020. Какой может быть сумма их возрастов, если известно, что самому старому человеку на земле было 146 лет, а в этой семье всем больше года? Ответ Решение

12. Васенька вырезал из клетчатой бумаги 3 фигуры, состоящие из целых клеток, первая состоит из 24 клеток, вторая — из 120, третья — из 126. Затем каждую фигуру он порезал по границам клеток на части, при этом все получившиеся части (в том числе от разных фигур) оказались равными. Какое минимальное количество частей могло получиться у Васеньки? Решение

13. Гриша в каждой вершине куба записал натуральное число, большее 1. Любые два числа, расположенные на концах одного ребра, — взаимно простые. Какое наименьшее значение может иметь сумма чисел, записанных Гришей? Решение

14. Гриша в каждой вершине куба записал натуральное число. Среди этих чисел нет равных, а любые два числа, расположенные на концах одного ребра, взаимно простые. Какое наименьшее значение может иметь сумма чисел, записанных Гришей? Решение

15. Данила несколько дней гостил у бабушки. Каждый из этих дней он решал задачи, причём каждый день больше, чем в предыдущий. В последний день он решил в 3 раза больше задач, чем в первый. Если перемножить его каждодневные результаты, то получится 810. Сколько всего задач решил Данила за эти дни? Решение

16. Олег перемножил 2020 подряд идущих натуральных чисел (не обязательно начиная с 1) и получил число S. Затем число S разложили на простые множители. В какой минимальной степени в этом разложении число 3? Решение

17. Барон Мюнхгаузен рассказал своему слуге, что во время путешествия перепрыгнул реку шириной 7 метров. Тот рассказал другому слуге о реке шириной 14 метров. Дальше каждый слуга, передавая эту новость, увеличивал ширину реки в 2 раза или 3 раза. В итоге один из слуг пересказал Барону рассказ о реке шириной 108864 метров. Сколько слуг передавали эту новость? Решение

18. Про некоторое натуральное число сделали 5 утверждений:

(1) «оно делится на 15»,

(2) «оно делится на 25»,

(3) «оно делится на 33»,

(4) «оно делится на 55»,

(5) «оно делится на 165».

Известно, что четыре утверждения верны, а одно — нет. Какое из этих утверждений неверно?Решение