НОД и НОК целых чисел

[Robot]

Немножко теории.
Целое число d называется общим делителем чисел a₁, a₂,.. a_k, если каждое из этих чисел делится на d. В дальнейшем мы будем говорить о натуральных делителях. Наибольший из общих делителей чисел a₁, a₂,.. a_k называется их наибольшим общим делителем и обозначается НОД (иногда (..,..)). Можно использовать и эквивалентное определение: Наибольшим общим делителем чисел a₁, a₂,.. a_k называется такой их общий делитель, который делится на любой другой их общий делитель.
Если НОД(a,b)=1, то числа а и b называются взаимно простыми. Такими например, являются 15 и 28. Аналогично если НОД( a₁, a₂,.. a_k)=1, то a₁, a₂,.. a_k взаимно просты. Если при этом НОД любой пары из них равен 1, то числа a₁, a₂,.. a_k называются попарно взаимно простыми. Например, числа 12, 15, 28 взаимно просты, но не попарно взаимно просты
Для нахождения НОД пары чисел можно использовать алгоритм Евклида (почитать о нем можно в книгах, рекомендуемых здесь Литература для подготовки к С6 ЕГЭ-2010 по математике (теория чисел) или просто погуглив). Кроме того, существует способ нахождения, использующий каноническое разложение натуральных чисел (см. здесь). Последний способ можно использовать для нахождения НОД нескольких чисел. В случае использования алгоритма Евклида придется использовать следующую формулу НОД(a,b,c)=НОД(НОД(a,b),c).
Полезно знать следующие свойства НОД
1) НОД(ka,kb)=k*НОД(a,b)
2)Если d - НОД(a,b), то числа a/d и b/d взаимно просты
3)Если d — наибольший общий делитель чисел а и b, то существуют такие целые числа х и у, что ах + by = d. Это равенство называется линейным представлением НОД чисел а и b.
(доказательство можно найти, например, в статье Болтянского и Левитаса по указанной выше ссылке).
Введем теперь понятие наименьшего общего кратного. Целое число m называется общим кратным чисел a₁, a₂,.. a_k, если m делится на каждое из этих чисел. В дальнейшем мы будем говорить о натуральных общих кратных. Наименьшее из общих кратных чисел a₁, a₂,.. a_k называется их наименьшим общим кратным и обозначается НОК (иногда [...,...]). Можно использовать и эквивалентное определение: Наименьшим общим кратным чисел a₁, a₂,.. a_k называется такое их общее кратное, на которое делится любое другое их общее кратное.
Полезны будут следующие свойства НОК
1) НОК(ka,kb)=k*НОК(a,b)
2)НОК(a,b)=ab/НОД(a,b). В частности, НОК взаимно простых чисел будет равно их произведению.
3)НОК(a,b,c)=НОК(НОК(a,b),c).
Найти НОК можно и через каноническое разложение чисел (см. здесь).

Следующая подборка задач с решениями на НОК и НОД любезно предоставлена  VEk (огромное ему спасибо!!!)
1. В магазин привезли меньше 600, но больше 500 тарелок. Когда стали раскладывать их десятками, то не хватило 3 тарелок до полного числа десятков, а когда стали раскладывать дюжинами (по 12 тарелок), то осталось 7 тарелок. Сколько тарелок привезли в магазин ?

Ответ и указание

Ответ: 547
Указание. Тарелок 10n+7 или 12m+7. Значит, убирая 7 тарелок получаем число, делящееся на НОК (10, 12) = 60. т.е. число тарелок записывается как 60k+7.
2. (UM.С6.1.) Найдите все пары натуральных чисел, наименьшее общее кратное которых равно 78, а наибольший общий делитель равен 13.

Ответ и указание

Ответ: 78 и 13 или 39 и 26
Указание. Искомые числа можно записать 13a и 13b, тогда 169ab=13*78, откуда ab=6. Так как a и b - натуральные, то либо a=1, b=6, либо a=2, b=3, или наоборот.
3. Найти наименьшее натуральное число, большее 1 и дающее при делении на 2, 3, 4, 5, 6 остаток, равный 1.

Ответ и указание

Ответ: 61.
Указание. Вычтем из искомого числа 1, тогда оно делится на 2, 3, 4. 5, 6, т.е.делится на (2,3,4,5,6)=60.
Возможно такое решение. Число 61, как легко видеть, удовлетворяет условиям задачи. Пусть x < 61 также удовлетворяет условиям задачи. Тогда 61 –x делится на 2, 3, 4, 5, 6 без остатка, т.е. делится на НОК(2,3,4,5,6)=60. Но тогда x=1. Противоречие с предположением. Значит, число 61 – наименьшее число, удовлетворяющее этим требованиям.
4. (UM.С6.2.) Найти все пары натуральных чисел, разность которых 66, а НОК равен 360

Ответ и указание

Ответ: 90 и 24
Указание. Пусть a-b=66,. Тогда, так как НОК(a,b)=360, то 360 делится на b+66 . Отсюда следует, что b делится на 6. Так как 360 делится на 5, а 66≡1(mod5) , то b≡4(mod5) . Из последних двух утверждений легко получить, что b=30m-6, m∈N . Тогда a=30(m+2), m∈N . Так как 360 делится на a, получаем, что m+2 – делитель 12, т.е. одно из чисел 3, 4, 6, 12. Простой перебор показывает, что подходит только одна пара.
5. На миллиметровой бумаге нарисован прямоугольник 272х204 мм (его стороны идут по линиям сетки). Проведем его диагональ и отметим все узлы сетки, которые на ней лежат. На сколько частей узлы делят диагональ?

Ответ и указание

Ответ. На 68 частей.
Указание. Разобьём каждую из двух смежных сторон прямоугольника на 68 одинаковых частей и через точки деления проведём прямые по линиям сетки. Тогда диагональ прямоугольника разобьётся узлами сетки на 68 одинаковых частей, служащих диагоналями прямоугольников размером 3 x4 мм. На диагонали каждого такого прямоугольника нет ни одного узла сетки.
6. (UM.С6.9) На клетчатой бумаге отмечен прямоугольник m x n с вершинами в узлах сетки клеток, причем m и n – взаимно простые числа и m < n, Диагональ этого прямоугольника не пересекает ровно 116 клеток этого прямоугольника. Найдите все возможные значения m и n.

Ответ и указание

Ответ: 2 x 117 или 3 x 59
Указание. Так как проведенная диагональ не проходит внутри прямоугольника через узлы сетки (в силу взаимной простоты m и n), то она пересекает (m-1)+(n-1) внутреннюю границу, при этом каждую клетку она пересекает ровно в 2-х точках. Значит всего диагональ пересекает m+n-1 клетку (каждая внутренняя точка пересечения принадлежит двум соседним клеткам и надо добавить еще одну граничную клетку). Поэтому получаем уравнение: mn-(m+n-1)=116, откуда (m-1)(n-1)=116 . Отсюда либо m=2, n=117, либо m=3, n=59, либо m=5, n=30 (последняя пара не удовлетворяет условию взаимной простоты m и n).
7. Найти натуральные числа a и b, если НОД(a, b)=6, а НОК(a, b) = 90

Ответ и указание

Ответ: (6; 90) или (18; 30)
Указание. Очевидно, что a=6m, b=6n, где НОД(m. n) = 1. Поэтому НОК(a, b) = 6mn= 90, откуда mn = 15. Значит, возможны варианты (m,n)=(1,15), (3, 5) и наоборот.
8. (UMC6.8) Натуральные числа a, b, с таковы, что НОК(a,b) = 60, НОК(a,c)=270. Найдите НОК (b,c).

Ответ и указание

Ответ: 108 или 540
Указание.
Другое решение данной задачи можно посмотреть здесь
9. (UMC6.11)Каким может быть НОД натуральных чисел m и n, если при увеличении числа m на 6, он увеличивается в 4 раза?

Ответ и указание

Ответ: 2 или 6

10. Пусть m и n - натуральные числа, причем m/n - правильная несократимая дробь. На какие натуральные числа можно сократить дробь

если известно, что она сократима?

Ответ и указание

Ответ: а) на 17; б) на 7.
Указание Сп.1. Воспользуемся спуском по алгоритму Евклида. Имеем:

По условию дробь сократима, а m, n – взаимно просты, поэтому единственным положительным НОД может быть число 17

11. (диагностическая работа 19.11.2010)Множество A состоит из натуральных чисел. Количество чисел в A больше 7. Наименьшее общее кратное всех чисел из A равно 210. Для любых двух чисел из А их наибольший общий делитель больше 1. Произведение всех чисел из А делится на 1920 и не является квадратом никакого целого числа. Найти числа, из которых состоит A.

Ответ и указание

Ответ: {6, 10, 14, 30, 42, 70, 105, 210}
Указание.
Разлагая 210 на множители получаем 210=2•3•5•7 , т.е. числа из А могут состоять только из указанных простых делителей и не более чем в первой степени. Всего делителей числа 210 – 16 (включая единицу, которая не может входить в множество A), чисел, содержащих один простой делитель в A нет (если какой-то простой делитель входит в А, то три других простых делителя и все их комбинации автоматом в А не входят, (НОД(x,y)>1, x, y∈ A) т.е. в А 8 чисел, содержащих простой делитель и все его комбинации с другими делителями. Но тогда произведение всех элементов A является полным квадратом. Противоречие).
. Значит, каждое число, содержащееся в A, является произведением как минимум двух простых делителей НОК, т.е. это числа (всего 11чисел)

Заметим, что в парах 2*3 и 5*7, 2*5 и 3*7, 2*7 и 3*5 в множестве A может содержаться только одно из чисел пары (НОД(x,y)>1, x, y∈ A), следовательно, в множестве A не более 8 чисел.
Разложим на множители число 1920=2⁷•3•5 . Так как произведение чисел из А делится на 1920, то в A должны входить все числа, делящиеся на 2 (их как раз 7). Значит, из приведенных выше пар из A исключаются пары 5*7, 3*7 и 3*5. Следовательно, множество A может состоять из 8 чисел

Проверка показывает, что произведение всех чисел из указанного множества не является полным квадратом. Значит, указанное множество чисел удовлетворяет всем условиям задачи, налагаемым на множество A.
Другой способ решения см здесь
Видеоурок Ольги Себедаш
12. Натуральные числа х и у таковы, что 3х - 10у = 88, а их наименьшее общее кратное НОК(х,у) связано с числом у условием НОК(х,у) - 5у = 380. Что это за числа?

Ответ и указание

Ответ: x=96, y=20.

Еще несколько задач.
13. Кудреватов Сборник задач по теории чисел

14. Найти наибольший общий делитель всех чисел вида: 7ⁿ⁺²+8²ⁿ⁺¹, где n - неотрицательное целое число (Болтянский, Левитас)
15. Существуют ли 6 последовательных натуральных чисел таких, что наименьшее общее кратное первых трех из них больше, чем наименьшее общее кратное трех следующих? problems.ru=79643
16. a и b - натуральные числа. Известно, что a²+b² делится на ab. Докажите, что a=b. problems.ru=98346
17.Сколько существует пар натуральных чисел, у которых наименьшее общее кратное (НОК) равно 2000? problems.ru=35071
18.Существует ли 100 натуральных чисел таких, что их сумма равна их наименьшему общему кратному? problems.ru=107607
19.Какое наибольшее значение может принимать наибольший общий делитель чисел a и b, если известно, что a•b = 600? problems.ru=60492
20.Натуральные числа a₁, a₂,..., a₄₉ удовлетворяют равенству a₁ + a₂ +...+ a₄₉ = 540.
Какое наибольшее значение может принимать их наибольший общий делитель? problems.ru=60493
21.Три натуральных числа таковы, что произведение любых двух из них делится на сумму этих двух чисел. Докажите, что эти три числа имеют общий делитель, больший единицы. problems.ru=110160
22. Имеется несколько чисел, каждое из которых меньше чем 1951. Общее наименьшее кратное любых двух из них больше чем 1951. Доказать, что сумма обратных величин этих чисел меньше 2. problems.ru=77934
23. Каков наибольший возможный общий делитель чисел 9m + 7n и 3m + 2n, если числа m и n не имеют общих делителей, кроме единицы? problems.ru=32111
P.S. Прошу прощения за возможные опечатки

@темы: Задачник, ЕГЭ, Теория чисел

Comments

[Гость]

14.

Рассмотрим первое число: 49*7^n + 8 *64^n: 3*19

Отсюда нужно проверить делимость на 3 и 19:

49*7^n + 8 *64^n = 11 * 7^n + 8 * 7^n = 19 * 7^n = 0 mod 19
49*7^n + 8 *64^n = 1^n + 2 * 1^n = 3 = 0 mod 3

Вот и все.

Trotil.

[Robot]

Ты даже ответ не дал((
Я бы начала с того, что при n=0 число равно 57. Покажем, что НОД всех чисел является 57, то есть каждое делится на 3*19 ну и т.д.
И потом желательно, где возможно, сравнений избегать.

[Гость]

СРавнения - это сокращенная запись свойств делимости по-школьному )
Trotil

[aalleexx]

Вот еще одна интересная задачка из этой же тематики

Вот мое решение

[Trotil]

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

[Robot]

aalleexx
Спасибо!
А откуда задачка?

Вот может сделать пост: интересные задачки, которые могут быть в С6?
И туда все складировать (только бы в известность всех поставить)
А ссылку я вставлю в эпиграф
Как такая идея?

[zholga]

Robot, идея хорошая.
Можно ещё сделать подборку задач по планиметрии, Vek уже предложил задачи на окружности, можно ещё на ортоцентр, да и вообще посмотреть задачи с несколькими вариантами ответов.

[aalleexx]

Robot ,

А откуда задачка?

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

[aalleexx]

Как такая идея?

по-моему, отличная мысль!

[VEk]

Robot Поддерживаю!

[Robot]

Ну, в общем, так, наверное, сделаю
Заголовок Сборник потенциальных задач С6 (или потенциальных слишком громко сказано?)
Там пока в большинстве будут ссылки, наверное. Вот aalleexx в комменты забросит свою задачу с решением
Потом ссылка на задачу Balance (мы разбирали, где числа Ф.)
Новые задачи с уже имеющимися решениями те, кто в теме - наше ядро, могут помещать в комменты (а я буду переносить в тело записи только условие).
Если задача не решена или под сомнением - то обычным образом выкладываем, решаем, потом условие и ссылку я переношу в эту запись.
Или даже можно только условие выложить в этой записи, если там все просто - для коллекции.
Просто обсуждение задач там неудобно будет вести, все перепутается. там просто Сборник
И для обычных пользователей - которые просто спрашивают о таких задачках (было уже как-то про квадраты цифр) - они обычным образом делают запись, там обсуждается как всегда, а я переношу условие и ссылку в этот пост.
Так?
Или что-то другое посоветуете.

[aalleexx]

Просто обсуждение задач там неудобно будет вести, все перепутается. там просто Сборник

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

[aalleexx]

Вот еще одна задачка из недавно попавшихся...

Пока сюда выложу, а когда будет тема, можно будет все вместе перенести.
P.S. Решение "топорное" - думаю, можно решить лучше.

[Гость]

6.

Пропущено уравнение

[VEk]

Гость Спасибо за внимательное прочтение. Там должно быть уравнение mn-(m+n-1)=116, откуда (m-1)(n-1)=116

[Гость]

Калькулятор для быстрого нахождения НОК и НОД allcalc.ru/node/148

[FirstAID]

2. (UM.С6.1.)

Почему

169ab=13*78,

[VEk]

FirstAID Так как ab=НОД(a,b)*НОК(a,b)

[FirstAID]

4. (UM.С6.2.) Найти все пары натуральных чисел, разность которых 66, а НОК равен 360

b=30m-6,

откуда это ?

[VEk]

FirstAID Надо было немного поработать и все получили бы. `b=4 ( mod 5) <=> b=5k+4`, `b = 0 (mod 6) <=> b=6m` . Значит, `6m=5k+4`. Решите это уравнение в целых числах и Вы получите `b=30n+24` или `b=30n_1-6`.

[FirstAID]

7. Найти натуральные числа a и b, если НОД(a, b)=6, а НОК(a, b) = 90

Поэтому НОК(a, b) = 6mn= 90,

Откуда это ?

[VEk]

FirstAID В указаниях к решению все понятно написано. Предыдущую фразу :

Очевидно, что a=6m, b=6n, где НОД(m. n) = 1.

надо тоже читать. И думать!

[Гость]

Чему равно произведение m*n натуральных чисел, удовлетворяющих условиям m+n=20, НОД(m;n)=5 ...

[Trotil]

Задача решается в уме за 3 секунды. Не шучу.

[Гость]

Пусть a-b=66,. Тогда, так как НОК(a,b)=360, то 360 делится на b+66 . Отсюда следует, что b делится на 6

почему именно на 6?
задача 4. (UM.С6.2.)

[VEk]

Гость Потому, что 360 и 66 делятся на 6

[Гость]

Не пойму этого действия.. Помогите советом пожалуйста.

`b=30n+24` или `b=30n_1-6`

[VEk]

Гость, Диофантово уравнение вида `ax+by=c` при НОД(a,b)=1 имеет решение `x=bt+x_0`, `y=-at+y_0`, где `(x_0;y_0)` - какое-либо частое решение уравнения. В данном случае таким частным решением является `m_0=4`, `k_0=4`.

[jujuo]

Помогите,пожалуйста!НОК 711,НОД 3.НАЙТИ ЧИСЛА.

[Дилетант]

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