Тема Делимость и делители (множители)

Условия про НОД и НОК

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела делимость и делители (множители)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#105489

Докажите, что

a+-b+-c Н ОД(ab+1,bc+1,ca +1)≤ 3

для попарно различных $a,$ $b,$ $c.$

Подсказки к задаче

Подсказка 1:

В этой задаче выгодным ходом будет рассмотрение разностей чисел ab + 1, bc + 1, ca + 1, ведь они тоже будут делиться на нод.

Подсказка 2:

А если дополнительно учесть, что НОД взаимно прост с a, b и c? Кстати, почему?

Подсказка 3:

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

Показать доказательство

Так как наибольший общий делитель, назовем его $d,$ делит числа $ab+1,bc+1,ca+1,$ то $d$ делит и их разности, имеем:

Н ОД(ab+1,bc+ 1,ca +1)= НОД(b(a − c),c(b− a),a(c− b))

Так как $d$ делит $ab+ 1,$ то $d$ взаимнопросто с $a$ и $b,$ аналогично и с $c,$ тогда

НОД(b(a− c),c(b− a),a(c− b))= НОД(a− c,b− a,c − b)

Пусть $a> b>c.$ Положим $b= c+β,a= c+ α+ β,$ где $α,β >0.$ Наибольший общий делитель чисел не превосходит меньшего из них по модулю, тогда $α≥ d$ и $β ≥ d.$

Необходимо доказать, что $3c+2β+α≥ d, 3$ это уже очевидно ведь $2β+α-≥ d. 3$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#79760

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

Показать ответ и решение

Давайте докажем, что если числа $a$ и $b$ различны, то НОД $(a,b)≤ a+b 3$ . Пусть $a< b$ , тогда НОД $(a,b)≤a$ , а 2НОД $(a,b)≤ b$ (так как $b$ делится на НОД $(a,b)$ , но равно быть не может, так как числа не равны и $b$ большее число, значит, 2НОД $(a,b)≤ b$ ). Получили, что 3НОД $(a,b)≤a +b$ . Давайте для каждого ребра запишем полученную оценку и сложим все неравенства, каждая вершина используется в трех неравенствах, поэтому сумма всех НОДов меньше либо равна суммы всех чисел. Предположим, что эти суммы равны, тогда равенство достигается в каждом неравенстве, выше. То есть равенство возможно только при $b= 2a$ или $a =2b$ (для каждого ребра).

Не теряя общности пусть $a= 2b$ , но тогда: либо $c=b$ , тогда нашлись два равных числа, либо $c= 4b$ , но также $d =b$ или $d= 4b$ , то есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов меньше суммы всех чисел.

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 3#85451

Для любых натуральных $a,b$ и $c$ докажите неравенство

(a,b− 1)(b,c− 1)(c,a − 1)≤ ab+bc+ ca

(Как обычно, $(x,y)$ обозначает наибольший общий делитель чисел $x$ и $y.$ )

Показать доказательство

Заметим, что

ab+ bc+ ca> ab+bc+ ca− a− b− c+1 =abc− (a− 1)(b− 1)(c− 1)

Но эта разность делится на произведение НОДов. Действительно, $a$ делится на $(a,b− 1),b$ делится на $(b,c− 1)$ и $c$ делится на $(c,a− 1),$ следовательно $abc$ делится на произведение НОДов. Аналогично $(a− 1)(b− 1)(c− 1)$ делится на произведение НОДов, а тогда и разность делится. Но тогда эта разность не меньше, а $ab+bc+ ca$ больше произведения НОДов.

Ошибка.
Попробуйте повторить позже

Задача 4#96446

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

Н ОК(a,a +5)= НОК(b,b+5)

то $a= b.$

Подсказки к задаче

Подсказка 1

Можно свести задачу к работе с НОД с помощью равенства НОК(x,y) × НОД(x,y) = xy. Как связаны НОД(a,a+5) и НОД(b,b+5)?

Подсказка 2

Верно! Из уравнения следует, что они равны. Тогда на них можно сократить. Как теперь доказать, что a = b?

Показать доказательство

Из алгоритма Евклида следует, что $НОК(a,a +5)= --a(a+5)- = -a(a+5). НОД(a,a+5) НОД(a,5)$ Аналогичным образом получаем, что $НОК(b,b +5)= -b(b+5)-. НОД(b,5)$ Таким образом, имеем равенство

a(a+ 5) b(b+ 5) НОД-(a,5) = НОД-(b,5)

Из этого равенства следует, что $5|a⇔ 5|b.$ Действительно, если некоторое число $x$ делится на $5,$ то и $x+5$ делится на $5$ и $НОД(x,5)= 5.$ Тогда $x(x+55)$ делится на $5,$ поэтому в противном случае число в одной из частей равенства делится на $5,$ а в другой — нет. Таким образом $НОД(a,5)= НО Д(b,5).$ Наше равенство эквивалентно

a(a +5)= b(b+ 5)

Поскольку на промежутке $[− 2,5;+∞)$ функция $f(x)= x(x+ 5)$ строго возрастает (так как в точке $− 2,5$ находится вершина параболы), то наше равенство $f(a)=f(b)$ эквивалентно равенству $a =b.$

Ошибка.
Попробуйте повторить позже

Задача 5#96447

Существуют ли натуральные $a,b$ и $c,$ для которых выполняется равенство

НО К(a,b)=Н ОК(a+ c,b+ c)?

Подсказки к задаче

Подсказка 1

Попробуем пойти от противного. Тогда, если такое равенство верно для чисел a, b и c, то оно верно и для чисел a/d, b/d, c/d, где d = НОД(a,b,c). Тогда можно полагать, что НОД(a,b,c) = 1. В задаче должно выполняться равенство НОК(a,b) = НОК(a+c,b+c). Что можно сказать о НОДе a+c и b+c?

Подсказка 2

Верно! Если такое равенство выполняется, то мы получаем, что НОК(a+c,b+c) ≤ ab < (a+c)(b+c), поэтому d = НОД(a+c,b+c) > 1. А можно ли доказать, что a или b имеют общие простые делители с d?

Подсказка 3

Можно! Пусть m = НОК(a+c,b+c) = НОК(a,b). Тогда m | ab. Кроме того, d | m. Тогда d | ab, а потому какое-то из чисел a и b не взаимно просто с d. Не умаляя общности, можно считать, что НОД(a,d) = k > 1. Можно ли доказать, что тогда b и c не взаимно просты с k?

Подсказка 4

Конечно! Ведь c = (c + a) - a. Правая часть делится на k, поэтому правая тоже делится. Аналогично доказывается, что b делится на k. В чем противоречие?

Показать ответ и решение

Предположим противное. Можно считать, что $НОД(a,b,c)= 1,$ иначе можно сократить все числа на этот НОД, и равенство останется верным. Пусть $m =Н ОК(a+ c,b+ c)$ и $d= НО Д(a +c,b+c).$ Так как

НОК (a+ c,b +c)= НОК(a,b)≤ ab< (a +c)(b+ c)

поэтому $d> 1.$ Поскольку $m |ab$ и $d|m,$ то $d|ab.$ Тогда $(a,d)>1$ или $(b,d)> 1.$ Без ограничения общности будем считать, что $(a,d)= δ > 1.$ Таким образом, $c= (a+c)− a$ и $b=(b+ c)− b$ делятся на $δ.$ Выходит, что все три числа $a,b,c$ делятся на $δ >1.$ При этом $Н ОД(a,b,c)=1$ — противоречие.

Ответ:

Нет, не существуют

Ошибка.
Попробуйте повторить позже

Задача 6#100471

Пусть натуральные числа таковы, что $a <a < ...< a . 1 2 n$ Докажите, что тогда $НОК(a ,a ,...,a)≥ na . 1 2 n 1$

Подсказки к задаче

Подсказка 1

Пусть наш НОК равен a. А можно ли упорядочить отношения a к нашим числам?

Подсказка 2

Верно! Эти отношения упорядочатся в обратном порядке. Тогда a/b — наибольшее число, где b — наименьшее число нашего набора. А какое наименьшее значение может принимать дробь a/b?

Показать доказательство

Пусть $НОК(a ,a ,...,a)= a. 1 2 n$ Тогда $-a> -a >...> a- a1 a1 an$ — различные натуральные числа. Таким образом, $-a ≥n, a1$ то есть $a ≥na1.$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#68029

У Пети есть $n$ карточек с $n$ последовательными натуральными числами (на каждой карточке написано ровно одно число). Он выложил эти карточки в ряд в некотором порядке.

У каждых двух чисел на соседних карточках Петя нашёл наибольший общий делитель. При каком наибольшем $n$ все эти наибольшие общие делители могут оказаться различными числами?

Источники: Курчатов-2023, 11.5 (см. olimpiadakurchatov.ru)

Подсказки к задаче

Подсказка 1

НОД различных чисел обязательно не превосходит их разности, а в задаче даны n последовательных чисел и их НОДы различны. Что это означает?

Подсказка 2

НОДы принимают значения от 1 до n-1, а их как раз n-1 штука. Значит, все числа от 1 до n-1 встретятся в НОДах. Теперь рассмотрим чётные НОДы. Какое должно выполниться условие, чтобы их все получить?

Подсказка 3

Для этого все чётные числа должны стоять подряд(докажите это!). Теперь осталось рассмотреть то, как они появляются в порядке убывания (полезно отдельно рассмотреть два случая в зависимости от чётности n).

Показать ответ и решение

Пример. Возьмём числа $12,13,14,15,16$ и расставим их в следующем порядке:

13,15,12,16,14

Тогда НОДы будут $1,3,4,2.$

Оценка. Здесь и далее $(a,b)$ — это НОД $(a,b).$ Прежде всего отметим, что:

(a,b)= (a− b,b)≤|a− b|

То есть НОД двух соседних чисел не превосходит модуля их разности. Но модуль разности любых двух из $n$ последовательных натуральных чисел принимает значения от $1$ до $n− 1.$ Всего Петя получит как раз $n− 1$ пару соседних чисел. Значит, в качестве НОДов должны встретиться все числа от $1$ до $n− 1$ по одному разу.

Докажем, что четные числа могут стоять только подряд.

1.: Пусть $n$ четно: $n = 2k.$ Тогда произвольная пара чисел отличается на величину от $1$ до $2k− 1,$ то есть всего четных разностей $k− 1,$ а самих четных чисел — $k.$ Значит они должны стоять подряд.
2.: Пусть $n$ нечетно: $n = 2k +1.$ Тогда произвольная пара чисел отличается на величину от $1$ до $2k.$ всего четных разностей $k.$ Но заметим, что четных чисел на карточках может быть всего $k$ или $k +1.$ Если их $k,$ то мы получим максимум $k − 1$ четных разностей. Тогда их ровно $k+ 1$ и они должны стоят подряд.

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

Теперь снова рассмотрим случаи в зависимости от чётности $n.$

1.: $n =2k+ 1.$ Тогда, как мы уже знаем, чётных чисел $k+1.$ Пусть они $x,x+ 2,...,x+ 2k.$ НОД $2k$ можно получить только поставив рядом $x$ и $x +2k.$ Получить НОД $2k− 1$ можно или парой $x,x+ 2k − 1$ или $x+ 1,x +2k,$ поскольку наибольшая нечётая разность как раз $2k− 1,$ а НОД не может быть больше разности. Будем считать, что выбрана первая пара. Покажем, что так можно сделать без ограничения общности. Заменим все числа на противоположные, а потом добавим $xn!$ . От этого НОДы соседних чисел не поменяются (поскольку мы добавили $n!$ несколько раз, что в любом случае делится на НОД (ведь он не более $n− 1).$ Числа всё ещё натуральные и последовательные ( $xn!− (x+ n− 1)> 0).$ При этом теперь наибольшее число перешло в наименьшее, то есть выбор пары тоже сменился. Тогда посмотрим, как идут в другую сторону чётные элементы. Для НОДа $2k − 2$ рядом с $x+ 2k$ обязательно стоит $x+ 2,$ поскольку наибольшая из доступных на текущий момент разностей как раз $2k− 2,$ а НОД не может быть больше разности. Для НОДа $2k − 4$ далее стоит $x+ 2k− 4.$ Далее мы снова будем чередовать самое маленькое из оставшихся чётных чисел и самое большое. В итоге, придём к $x+ k$ или к $x+ k+ 1$ (в зависимости от чётности $k).$ Попробуем получить НОД $2k− 3.$ НОД нечётных чисел не более $k− 1,$ поскольку их максимальная разность $2k− 2$ (наименьшее — $x+ 1,$ наибольшее — $x+ 2k − 1).$ С крайним чётным числом разность не более чем $k.$ Для $k≥ 4,2k − 3> k,$ поэтому такого НОД не получится. Противоречие. Для $k =3$ получаем последовательность $x +5,x,x +6,x+ 2,x +4,x+ 1.$ Но $(x+ 6,x)$ и $(x +4,x+ 1)$ не могут одновременно делится на $3.$ Противоречие.
2.: $n =2k.$ Без ограничения общности будем считать $x$ чётным. Рядом с $x$ должно стоять $x +2k− 1,$ чтобы получить НОД $2k− 1.$ Аналогично, другим крайним элементом последовательности чётных будет $x+k$ или $x+ k− 1$ в зависимости от чётности $k.$ Тогда снова попробуем получить НОД $2k− 3.$ Для двух нечётных он снова не более $k− 1.$ С крайним чётным числом разность не более $k − 1,$ ведь максимальное нечётное $x +2k− 1$ уже занято с другой стороны, а наименьшее нечётное $x +1.$ Для $k≥ 3,$ получаем $2k− 3> k− 1.$ противоречие.

Ответ:

$5$

Ошибка.
Попробуйте повторить позже

Задача 8#68880

Пусть $a,b,c$ — взаимно простые в совокупности натуральные числа, и

( 2 2 2 n n n) Dn = a+ b+ c,a + b+ c ,a + b + c

Найдите все возможные значения $D , n$ где $n−$ натуральное число, кратное 3. Запись $(a,a ,a,...,a ) 1 2 3 k$ обозначает наибольший общий делитель целых чисел $a ,a,a ,...,a . 1 2 3 k$ Целые числа $a ,a,a ,...,a 1 2 3 k$ называются взаимно простыми в совокупности, если $(a ,a,a ,...,a )= 1. 1 2 3 k$

Источники: Иннополис-2023 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

А давайте для начала попробуем ручками проверить различные a, b, c - чтобы понять, каким вообще может быть D.

Подсказка 2

Пупупу… а теперь посмотрим внимательно на условие. Каким свойством обладают скобки вида: (aⁿ + bⁿ + cⁿ)?

Подсказка 3

Да, эти скобки симметричны! Если поменять какие-то две переменные местами, то выражение не изменится. А теперь, учитывая, что мы получили какие-то значения D - попробуйте перейти к симметрическим многочленам. К какому противоречию мы придём?

Подсказка 4

Верно, мы придём к тому, что существует какое-то просто p, которое делит произведение abc. Теперь нужно аккуратно доказать, что в таком случае простое p делит каждое из чисел a, b, c! Тогда, мы докажем, что возможны только D = {1, 2, 3, 6}.

Подсказка 5

Остаётся только привести пример чисел a, b, c для каждого возможного D!

Показать ответ и решение

Пусть $σ,σ ,σ 1 2 3$ — элементарные симметрические многочлены и $n n n sn = a + b + c.$ Воспользуемся формулой Ньютона

sk = σ1sk−1− σ2sk−2+ σ3sk−3

Докажем, что $D ∈ {1,2,3,6}. n$ Предположим, что существуют такие взаимно простые в совокупности $a,b,c$ , что $D n$ отличен от $1,2,3,6.$ Докажем, что тогда $σ ,σ,σ 1 2 3$ имеют общий делитель, больший 1. В самом деле, из формул Ньютона следует, что при разложении $s n$ через $σ ,σ ,σ 1 2 3$ моном, не содержащий $σ 1$ и $σ, 2$ с точностью до знака имеет вид $3σ n3. 3$ Поэтому если $D n$ делит $s = σ 1 1$ и $D n$ делит $2 s2 = σ1 − 2σ2,$ то $Dn$ делит $σ1,2σ2,3σ3.$

При $Dn,$ отличном от $1,2,3,6$ у чисел $σ1,σ2,σ3$ есть общий делитель, больший 1. Пусть $p$ — простой множитель, входящий в этот делитель. Тогда $p$ делит $abc,$ откуда (без ограничения общности) $p$ делит a. Но тогда $p$ делит $(ab+ bc+ ca)$ и $p$ делит $bc,$ т.е. (без ограничения общности) $p$ делит $b.$ Наконец, из того, что $p$ делит $(a+b+ c),$ получаем, что $p$ делит $c.$ Значит, $(a,b,c)≥ p,$ но по условию $(a,b,c)= 1$ — противоречие.

Итак, $Dn ∈ {1,2,3,6}.$ Набор $(1,1,2)$ реализует $Dn = 2,$ набор $(1,1,1)$ — $Dn = 3,$ набор $(1,4,7)$ — $Dn = 6.$ Для $Dn = 1$ возьмем простое число $p >3$ и положим $a =b =1, c =p− 2.$ Тогда $a+ b+c =p$ и $p$ не делит $2 2 2 2 a +b + c =p − 4p+ 6,$ откуда $Dn = 1.$

Ответ:

${1,2,3,6}$

Ошибка.
Попробуйте повторить позже

Задача 9#31296

Илья придумал три числа $a,b$ и $c,$ а затем посчитал НОД $(a,b),$ НОД $(a,c)$ и HOД $(b,c).$ У него получились такие результаты: $378,840,630.$ Докажите, что Илья где-то ошибся.

Подсказки к задаче

Подсказка 1

Так как речь идет о НОД чисел, то мы хотим получить какое-то противоречие с делимостью

Подсказка 2

Если НОД(a, b) делится на d, то и a и b должны делиться на d

Подсказка 3

Рассмотрите d = 5. НОД(a, c) делится на 5, НОД(b, c) делится на 5. Что из этого следует?

Показать доказательство

Предположим, что он нигде не ошибся. Заметим, что тогда $a$ и $b$ кратны $9$ (так как их НОД $=378$ кратен $9$ ) и $b$ и $c$ кратны $9$ (так как их НОД $= 630$ кратен $9$ ). Тогда $a$ и $c$ вместе кратны $9$ => их НОД должен быть кратен $9,$ однако $840$ не кратно $9.$ Противоречие.

Замечание. Также противоречие можно получить из-за делимости на $5.$ Из того, что два НОД делятся на $5,$ нетрудно вывести, что все три числа должны делиться на $5.$ Но третий НОД на $5$ не делится.

Ошибка.
Попробуйте повторить позже

Задача 10#34069

На доске написаны натуральные числа от 1 до 100, каждое по одному разу. Каждую минуту мальчик Лёша выбирает два числа $a$ и $b$ , написанных на доске, вычисляет НОД $2 2 2 2 (a +b + 2,a b +3)$ , пишет его на доску, а сами числа стирает. Через 99 минут на доске останется одно число. Докажите, что оно не может быть точным квадратом.

Показать ответ и решение

Как вообще можно доказать, что число не является квадратом? Если число не квадрат, то в его разложении есть простое число в нечетной степени. Но мы поступим тут немного наглее, докажем, что существует $p$ , такое что оставшееся число делится на $p$ , но не делится на $2 p$ . Посмотрим на число $3$ .

1) Если $. a,b..3$ , то НОД $. (a2+ b2+2,a2b2+ 3)⁄..3$ .

2) Если $.. .. a.3,b⁄.3$ . Тогда $2 b$ дает остаток 1 при делении на $3$ ,
поэтому НОД $. (a2+ b2 +2,a2b2+ 3)..3$ .

3) Если $a,b⁄...3$ , то НОД $(a2+ b2+ 2,a2b2+ 3)⁄...3$ .

Мы нашли инвариант! Четность количества чисел, которые делятся на $3$ , не меняется. Изначально их было 33, значит, последнее число делится на 3. Покажем, что оно не делится на 9. То есть были в конце числа $a,b,$ мы их заменили на НОД $2 2 22 (a +b + 2,a b +3)$ , при этом этом так как последнее число делится на 3, то это могло быть только во 2-ом случае (только в этом случае НОД делится на 3). Но давайте заметим, что $a2b2+3$ точно не делится на 9 в этом случае, а значит, и НОД $. (a2+b2+ 2,a2b2+ 3)⁄..9$ . Таким образом, последнее число не квадрат.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 11#34147

Найдем НОД(504, 540).

Показать ответ и решение

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

$3 2 504= 2 ⋅3 ⋅7$

$2 3 540= 2 ⋅3 ⋅5$

Теперь представим, что мы уже нашли НОД и также разложили его на простые множители. Логично, что кроме 2, 3, 5 и 7 в его разложении ничего нового появиться не может (это же все-таки делитель). Рассмотрим внимательнее 5 и 7: если НОД кратен 5, то 504 кратно 5 (число же кратно своему делителю), а это неверно! Аналогично 540 не кратно 7, значит, НОД тоже не кратен 7.

Получается, НОД $x y (a,b)= 2 ⋅3$ . Оба числа кратны $2 2 2 ⋅3$ (просто возьмем наименьшую из степеней двойки и тройки в разложениях), значит, это общий делитель.

А вдруг это не НОД? То есть $x >2$ или $y > 2$ . Если же $x$ хотя бы 3, то 540 кратно как минимум $33$ , то есть тройки входит в разложении в хотя бы 3-ей степени. Но это не так. Аналогично получаем противоречие в случае $y ≥ 3$ . Получается, что $x ≤2$ и $y ≤ 2$ и НОД $≤ 22 ⋅32$ . Однако $22⋅32$ является общим делителем и, значит, он наибольший.

Ответ:

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#34148

Коля, Серёжа и Ваня регулярно ходят в кинотеатр: Коля бывал в нём каждый 6-й день, Серёжа — каждый 10-й, Ваня — каждый 12-й. Сегодня все ребята были в кино. Когда все трое встретятся в кино в следующий раз?

Подсказки к задаче

Подсказка 1

Для того, чтобы прочувствовать тот факт, который мы будем использовать для решения, начните выписывать дни, в которые Коля, Серёжа и Ваня ходят в кинотеатр независимо друг от друга и посмотрите, когда они совпадают, каким свойством обладают эти дни?

Подсказка 2

Правильно, если Коля ходит в дни, которые делятся на 6, а Серёжа в дни, которые делятся на 10, то они могут встретиться только в дни, которые делятся на 6 и на 10, остаётся только добавить в эту цепочку Ивана и радоваться победе!

Показать ответ и решение

Начнем нумеровать дни, начиная с завтрашнего (сегодняшний день — «нулевой»). Коля будет ходить в кино в те дни, номера которых делятся на 6, Сережа — в те дни, номера которых делятся на 10, Ваня — в те дни, номера которых делятся на 12. Чтобы они все вместе оказались в кино, номер дня должен делиться и на 6, и на 10, и на 12. Раньше всего это произойдет в день с номером НОК $(6,10,12)$ .

Найдем этот НОК:

$6= 2⋅3$

$10 =2⋅5$

$2 12 =2 ⋅3$

Для НОКа берем максимальные степени по всем имеющимся простым, то есть НОК $2 (6,10,12)= 2 ⋅3⋅5= 60$ .

Ответ: На 60-й день (считая, что сегодня - нулевой).

Ошибка.
Попробуйте повторить позже

Задача 13#34153

Про два натуральных числа $a$ и $b$ известно, что их НОК в $75$ раз больше, чем их НОД, и $a$ больше $b.$ Докажите, что $a$ больше, чем $8b.$

Подсказки к задаче

Подсказка 1

В условии идёт речь про НОД и НОК. Удобно "выделить" в числах a и b их НОД, представив в виде a=Ad, b=Bd, где d=НОД(a, b).

Подсказка 2

Мы хотим доказать, что А/В>8. В наших обозначениях отношение НОК(a, b) и НОД(a, b) - это АВ. Получается, АВ=75. Какими тогда могут быть А и В, учитывая НОД(А,В)=1?

Показать доказательство

Представим наши числа как $a= Ad >b= Bd,$ где $d= НО Д(a,b).$

Тогда $НОД(A,B)= 1$ и $Н ОК(a,b)=d ⋅Н ОК(A,B)= dAB.$

Так как по условию $Н ОК(a,b)= 75d$ , то $AB = 75$ .

Из взаимной простоты и $A > B$ следует $A= 25,B = 3$ или $A= 75,B = 1.$ В каждом из этих случаев $A >8B =⇒ a> 8b.$

Ошибка.
Попробуйте повторить позже

Задача 14#34155

Сколько существует пар натуральных чисел, у которых наименьшее общее кратное равно $5000$ ?

Показать ответ и решение

Замечание.

На реальных олимпиадах обычно в условии задачи указывают считать пары неупорядоченными, то есть считать одинаковыми пары $(a,b)$ и $(b,a)$ при $a⁄= b.$ В условии данной задачи этого указано не было. Однако жюри при проверке предлагается засчитывать как верные решения, учитывающие порядок чисел в паре, так и верные решения, рассматривающие только неупорядоченные пары.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим два случая

Хотя бы одно из чисел равно 5000.
Тогда другое число может быть любым делителем числа 5000. Поскольку $5000 =23⋅54$ , оно имеет $(3+1)⋅(4+ 1)= 20$ делителей. Таким образом, в этом случае имеется 20 пар без учёта порядка в паре и $2⋅20− 1 =39$ упорядоченных пар (так как среди 20 в одной паре числа совпадают и пара не поменяется при их перестановке).
Ни одно из двух чисел $a,b$ не равно 5000.
Тогда в разложении одного из этих чисел $a,b$ на простые сомножители должен присутствовать множитель $3 2$ , а в разложении другого — множитель $4 5.$ Без учёта порядка в паре $(a,b)$ положим
$a= 23⋅5m, b= 2n⋅54,$
где $m ∈ {0,1,2,3},$ и независимо от этого $n ∈{0,1,2}.$ Таким образом, в этом случае имеется $4 ⋅3 =12$ неупорядоченных пар (и соответственно 24 упорядоченные пары, поскольку в каждой из 12 пар числа различны).

_________________________________________________________________________________________________________________________________________________________________________________

Итак, есть $20+12 =32$ пары без учёта порядка и $39+ 24= 63$ пары с учётом порядка.

Ответ: 32 неупорядоченные пары, 63 упорядоченные пары

Ошибка.
Попробуйте повторить позже

Задача 15#34156

Можно ли вместо звездочек вставить в выражение

НОК (∗,∗,∗)− НОК (∗,∗,∗)= 2009

в некотором порядке шесть последовательных натуральных чисел так, чтобы равенство стало верным?

Подсказки к задаче

Подсказка 1

Среди шести последовательных чисел ровно три четных и три нечетных. Могут ли четные числа оказаться в разных НОКах?

Подсказка 2

Верно, не могут! Тогда оба нока четны, и их разность не равна 2009. Тогда все четные числа в одном НОКе, а в другом — нечетные. А можно ли теперь применить делимость не на 2, а на какое-то другое небольшое число?

Подсказка 3

Верно! Делимость на 3 нам поможет: среди трех последовательных четных чисел есть делящееся на 3. А верно ли аналогичное утверждение о трех последовательных нечетных?

Показать ответ и решение

Предположим, что можно. Среди $6$ последовательных чисел ровно $3$ четных. Тогда если четные числа есть и в первом НОКе, и во втором, то оба НОКа четные и их разность тоже четная (явно не $2009).$ Значит, в одном НОКе все три четных числа, а в другом — все три нечетные.

Заметим, что среди трех четных последовательных чисел обязательно есть число, кратное $3$ (так как все три числа дают разные остатки при делении на $3).$ Аналогично, среди нечетных есть число, кратное $3.$ Тогда оба НОКа кратны $3$ и их разность также кратна $3.$ Противоречие, так как $2009$ не кратно трем. Значит, наше предположение неверно.

Ответ:

Нет, нельзя

Ошибка.
Попробуйте повторить позже

Задача 16#35107

Докажите, что $НО Д(a,b)⋅НОК(a,b)= ab$ .

Показать ответ и решение

Подумаем, как вообще устроены НОД и НОК. Если разложить каждое из чисел $a$ и $b$ на простые множители, то в НОД каждый из простых множителей идет в минимальной из двух степеней, а в НОК — в максимальной. А так как $x +y =max(x,y)+ min(x,y)$ , то каждое простое число входит в левое и правое произведения в одинаковой степени, поэтому два произведения равны.

Ответ:

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#35108

Два натуральных числа $a$ и $b$ друг на друга не делятся, при этом $НОД(a,b)= 50$ , а $Н ОК(a,b)= 1000$ . Найдите эти числа.

Показать ответ и решение

Так как НОК чисел равен 1000, то в разложении на простые множители чисел $a$ и $b$ присутствуют только 2 и 5 не более чем в 3-й степени. При этом, так как НОД равен 50, то по две пятерки и по одной двойке в числах точно должны быть.

Далее, в одном из чисел, пусть $a$ , присутствует $3 5$ . Так как числа друг на друга не делятся, то в другом числе $b$ пятерка только во второй степени, зато в него входит $3 2$ . Тогда, чтобы НОД двух чисел был равен 50, в число $a$ двойка входить лишь в первой степени. В итоге получили числа $a= 200$ , $b=250$ , или наоборот.

Ответ: 200 и 250

Ошибка.
Попробуйте повторить позже

Задача 18#35114

Докажите равенство

abc =Н ОК(a,b,c)⋅НО Д(ab,ac,bc)

Подсказки к задаче

Подсказка 1

Для док-ва давайте воспользуемся основной теоремой арифметики, которая утверждает, что любое число больше 1 может быть разложено в произведение степеней простых единственным, с точностью до перестановки множителей, способом. Тогда нам остаётся только доказать, почему в обеих частях каждое простое число входит в одинаковой степени, так давайте распишем a, b, c в виде произведения степеней простых чисел и докажем, что в обеих частях они совпадают

Подсказка 2

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

Показать доказательство

Рассмотрим все простые числа, на которые делится хотя бы одно из чисел $a,b,c$ . Докажем, что оно входит в одинаковой степени в правую и левую часть. Проделав такие рассуждения для всех простых чисел, получим требуемое утверждение. Рассмотрим произвольное такое простое $p$ Обозначим через $x,y,z$ степени вхождения $p$ в числа $a,b,c$ соответственно. Заметим, что степень вхождения $p$ в число $НОК(a,b,c)$ равна наибольшему из чисел $x,y,z$ , а степень вхождения $p$ в $Н ОД(ab,ac,bc)$ — сумме 2 самых маленьких чисел из $x,y,z$ . Тогда суммарная степень вхождения $p$ в правую часть равна $x+ y+ z$ , что в точности равно степени вхождения $p$ в левую часть.

Ошибка.
Попробуйте повторить позже

Задача 19#97945

Ваня загадал два натуральных числа, произведение которых равняется $7200.$ Какое наибольшее значение может принимать НОД этих чисел?

Источники: ВСОШ - 2022, школьный этап, 9 класс

Показать ответ и решение

Поскольку каждое из этих чисел делится на их НОД, то их произведение делится на квадрат этого НОД. Наибольший точный квадрат, на который делится число $5 2 2 7200= 2 ⋅3 ⋅5 ,$ это $( 2 )2 3600= 2 ⋅3⋅5$ , поэтому НОД двух искомых чисел не превосходит 60. При этом НОД может равняться 60, если искомые два числа это 60 и 120.

Ответ: 60

Ошибка.
Попробуйте повторить позже

Задача 20#44071

Найдите наибольшее значение выражения

(5n− 18)НОД-(n-+9,n+-2) F = НОК(n+ 9,n +2)

на множестве натуральных чисел. При каком $n$ оно достигается?

Подсказки к задаче

Подсказка 1

Числа n+2 и n+9 это же достаточно близкие числа, при этом их разность равна 7. Что тогда можно сказать про их НОД?

Подсказка 2

Да, их НОД либо равен 1, либо равен 7. Обозначим его за d. Какая замена тогда просится, если у нас есть НОК и НОД одних и тех же чисел?

Подсказка 3

Ну конечно, замена НОК(a,b)=ab/НОД(a,b). Тогда наше выражение принимает понятный вид. Осталось исследовать функцию, которая получается делением нашего выражения на d^2 и понять, где она принимает максимальное значение.

Подсказка 4

Да! В точке 12. А что еще принимает максимальное значение в точке 12? Поймите это и получите ответ!

Показать ответ и решение

Обозначим $d= НОД (n +9,n+ 2).$ Так как $n+ 9$ и $n+ 2$ делятся на $d,$ то их разность $(n +9)− (n +2)= 7$ делится на $d.$ Тогда $d =1$ или $d= 7.$

Как известно, $НОК(a,b)⋅НО Д(a,b)= a⋅b,$ откуда выражение из условия принимает вид

(5n− 18)⋅d2 F (n)= (n+-2)(n+-9)

Поскольку $d$ может принимать значения только двух констант: $1$ или $7,$ то нам достаточно будет максимизировать функцию

G (x)= ---5x-− 18-, x> 0 (x+ 2)(x+ 9)

Эта функция определена уже при всех действительных $x$ , потом учтём, что у нас было натуральное $n$ . Для максимизации посмотрим на её производную:

′ 5(x2+-11x+-18)−-(5x−-18)(2x+-11)- (x-− 12)(5x+-24) G(x)= (x +9)2(x+ 2)2 =− (x+ 2)2(x+9)2

Производная при $x> 0$ имеет ровно одну точку экстремума $x =12$ (это кстати натуральное число), которая является точкой максимума, потому является глобальным максимумом при $x> 0.$ А ещё удачным образом при $n= 12$ имеем $d =7$ — также принимает максимальное значение, потому при $n = 12$ достигает максимума и функция $F.$ Равен этот максимум

--5⋅12−-18-- F(12)= (12+9)(12+ 2) ⋅49= 7

Ответ:

$7$ при $n= 12$