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

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

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

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

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

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

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

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

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

Задача 1#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$ , то есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов меньше суммы всех чисел.

Ответ:

Нет

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

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

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

Задача 2#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$ больше произведения НОДов.

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

Задача 3#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.$

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

Задача 4#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$ — противоречие.

Ответ:

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

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

Задача 5#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.$

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

Задача 6#68029

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

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

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

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

Подсказка 1

Вот пусть у нас все эти НОДы - n-1 различных чисел. У нас сами числа так-то расположены очень плотно: идут подряд, то есть самое маленькое меньше самого большого всего на n. Тогда как удобно было бы оценить НОД двух чисел?

Подсказка 2

Например, через разность: НОД(a, b) = НОД(b, a-b) ≤ |a-b|. А еще мы знаем, что разность двух наших чисел точно не больше чем n-1....Теперь что можно сказать про все НОДы?

Подсказка 3

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

Подсказка 4

Попробуйте доказать, что все чётные числа должны идти подряд, и тогда задачка решится окончательно)

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

Пример. Возьмём числа $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$

Курсы

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

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

Задача 7#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}$

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

Задача 8#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$ не делится.

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

Задача 9#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$ . Таким образом, последнее число не квадрат.

Ответ:

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

Задача 10#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$ является общим делителем и, значит, он наибольший.

Ответ:

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

Задача 11#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-й день (считая, что сегодня - нулевой).

Интенсивы

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

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

Задача 12#34149

Найдите пару натуральных чисел, если известно, что
1) их НОД равен $56$ , a НОК — 112;
2) НОД равен $18$ , a НОК — 630.

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

1) Разложим НОД и НОК на простые множители: $56 =23⋅7$ , $112= 24⋅7$ . Вспомним, что в НОД простые множители входят в минимальной из двух степеней вхождения, а в НОК — в максимальной. Значит, в оба числа 7 входит ровно в первой степени, а двойка в одно число входит в 3 степени, а в другое в 4. Следовательно, это числа $3 2 ⋅7= 56$ и $4 2 ⋅7= 112$ .

2) Разложим НОД и НОК на простые множители: $2 18= 2⋅3$ , $2 630= 2⋅3 ⋅5⋅7$ . Вспомним, что в НОД простые множители входят в минимальной из двух степеней вхождения, а в НОК — в максимальной. Значит, в оба числа двойка входит ровно в первой степени, тройка — ровно во второй, а 5 и 7 входят только в одно число (причем в первой степени). Тогда 5 и 7 могут вместе входить в одно число, а могут входить в разные. Получаем два варианта: $2 2⋅3 = 18$ и $2 2⋅3 ⋅5⋅7=630$ , $2 2⋅3 ⋅5= 90$ и $2 2⋅3 ⋅7= 126$ .

Ответ: 1) (56, 112). 2) (18, 630), (90, 126).

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

Задача 13#34150

Может ли наибольший общий делитель двух натуральных чисел быть больше их разности?

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

Предположим, что существуют такие два натуральных числа $a$ и $b$ ( $a≥b$ , что $Nod(a,b)> a− b$ . Если $a= b$ , то это неравенство верно (слева стоит натуральное число, а справа — 0). Если же $a> b$ , то их разность должна тоже делиться на их НОД, так как $a= Nod(a,b)⋅x$ , $b= Nod(a,b)⋅y$ , а $a− b= Nod(a,b)⋅(x − y)$ , где $x− y$ — натуральное число. Значит, $a− b≥ Nod(a,b)$ — противоречие с предположением.

Ответ: Только если эти числа равны.

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

Задача 14#34151

Пусть $a$ и $b$ - натуральные числа. Докажите, что

--ab---- НОК (a,b)= НОД(a,b)

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

Рассмотрим степень каждого простого числа, входящего в разложение $a$ или $b$ . Пусть $p$ входит в $a$ в степени $x$ , а в $b$ в степени $y$ ( $x,y ≥0$ ). Тогда $p$ входит в $Nod(a,b)$ в минимальной степени из $x$ и $y$ , а в $Nok(a,b)$ в максимальной степени из $x$ и $y$ . Тогда в их произведение $Nod(a,b)⋅Nok (a,b)$ $p$ входит в степени $x+y$ (так как одна из степеней максимальная из двух, а вторая автоматически минимальная). То есть степени вхождения $p$ в числа $ab$ и $Nod(a,b)⋅Nok(a,b)$ равны. Пройдемся так по всем простым из $a$ и $b$ . Из этого будет следовать, что разложения чисел $ab$ и $Nod(a,b)⋅Nok(a,b)$ — одинаковые, а значит, и $Н ОК(a,b)⋅НОД(a,b)= ab$ .

Ответ:

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

Задача 15#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.$

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

Задача 16#34154

Жители острова Невезения, как и мы с вами, делят сутки на несколько часов, час на несколько минут, а минуту на несколько секунд. Но у них в сутках 77 минут, а в часе 91 секунда. Сколько секунд в сутках на острове Невезения? (В часе больше одной минуты)

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

По условию:

$77 =(кол- во минут в часе)×(кол- во часов в сутках)$

$91 =(кол- во минут в часе)×(кол- во секунд в минуте)$

Тогда и 77, и 91 делится на (кол-во минут в часе). Следовательно, и НОД(77, 91) = 7 делится на (кол-во минут в часе). Так как (кол-во минут в часе) > 1, то (кол-во минут в часе) может равняться только 7.

Значит, (кол-во часов в сутках) = 11, (кол-во секунд в минуте) = 13, а секунд в сутках $(кол- во часов в сутках)× (кол- во м инут в часе)× (кол- во секунд в м ин&#x$ .

Ответ: 1001

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

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

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

Задача 17#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 упорядоченные пары

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

Задача 18#34156

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

Ответ:

Нет, нельзя

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

Задача 19#35107

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

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

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

Ответ:

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

Задача 20#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

Предыдущий раздел

Следующий раздел