Немножко теории.
читать дальшеЦелое число d называется общим делителем чисел a1, a2,.. ak, если каждое из этих чисел делится на d. В дальнейшем мы будем говорить о натуральных делителях. Наибольший из общих делителей чисел a1, a2,.. ak называется их наибольшим общим делителем и обозначается НОД (иногда (..,..)). Можно использовать и эквивалентное определение: Наибольшим общим делителем чисел a1, a2,.. ak называется такой их общий делитель, который делится на любой другой их общий делитель.
Если НОД(a,b)=1, то числа а и b называются взаимно простыми. Такими например, являются 15 и 28. Аналогично если НОД( a1, a2,.. ak)=1, то a1, a2,.. ak взаимно просты. Если при этом НОД любой пары из них равен 1, то числа a1, a2,.. ak называются попарно взаимно простыми. Например, числа 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 называется общим кратным чисел a1, a2,.. ak, если m делится на каждое из этих чисел. В дальнейшем мы будем говорить о натуральных общих кратных. Наименьшее из общих кратных чисел a1, a2,.. ak называется их наименьшим общим кратным и обозначается НОК (иногда [...,...]). Можно использовать и эквивалентное определение: Наименьшим общим кратным чисел a1, a2,.. ak называется такое их общее кратное, на которое делится любое другое их общее кратное.
Полезны будут следующие свойства НОК
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=27•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. Найти наибольший общий делитель всех чисел вида: 7n+2+82n+1, где n - неотрицательное целое число (Болтянский, Левитас)
15. Существуют ли 6 последовательных натуральных чисел таких, что наименьшее общее кратное первых трех из них больше, чем наименьшее общее кратное трех следующих? problems.ru=79643
16. a и b - натуральные числа. Известно, что a2+b2 делится на 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.Натуральные числа a1, a2,..., a49 удовлетворяют равенству a1 + a2 +...+ a49 = 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. Прошу прощения за возможные опечатки
-
-
15.12.2012 в 03:02-
-
14.11.2013 в 17:09взарание спасибо
-
-
14.11.2013 в 17:22-
-
15.11.2013 в 19:35-
-
15.11.2013 в 19:36-
-
15.11.2013 в 19:40Инструкции для гостей pay.diary.ru/~eek/p48601521.htm
-
-
15.11.2013 в 19:53chto nado vvesti? (esli vvojy eek.diary.ru/ ili eek ili Не решается алгебра/высшая математика?.. ПОМОЖЕМ!
programma pishet chto "Неверно введен домашний каталог") tak chto nyjno?
-
-
15.11.2013 в 19:58Имя tort свободно, можете подобрать что-то еще простое и не занятое другими
-
-
15.11.2013 в 20:01-
-
15.11.2013 в 20:03-
-
29.12.2013 в 15:21-
-
29.12.2013 в 15:24О чем идет речь? Где вы вводите этот адрес?
-
-
29.12.2013 в 19:23-
-
29.12.2013 в 19:57В этом поле нужно указать настоящий адрес своей электронной почты
-
-
18.11.2015 в 17:39Существуют ли такие а и б, что НОК (а, б)= НОК (а+2015, б+2016)
-
-
18.11.2015 в 21:55Здесь вашу просьбу не увидят.
Нужно вступить в сообщество и создать свой топик с этой задачей.