Тема ТЕОРИЯ ЧИСЕЛ

Делимость и делители (множители) → .01 Условия про НОД и НОК

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

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

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

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

Подтемы раздела теория чисел

Разделы подтемы Делимость и делители (множители)

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

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

Оценки для доказательства делимости

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

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

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

Задача 21#44071Максимум баллов за задание: 7

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

(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$

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

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

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

Задача 22#61648Максимум баллов за задание: 7

Сколько существует пар натуральных чисел $(a,b)$ , у которых $НО К(a,b)= 23 ⋅32⋅5⋅72 = 17640$ , а $НОД(a,b)= 12$ ? (пары неупорядоченные, то есть $(a,b)$ и ( $b,a)$ считайте одинаковыми)

Среди всех таких пар укажите ту, для которой $a +b$ принимает минимально возможное значение, и найдите это значение.

Источники: Росатом - 2021, 11.3, комплект 1 (см. olymp.mephi.ru)

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

Подсказка 1

Вспомним основную теорему арифметики - из нее следует, что НОК и НОД это взятие соответственно максимума и минимума по степеням простых множителей в наших двух числах. У наших чисел всего максимум 4 вида простых множителей -2,3,5,7. Попробуйте с этим знанием понять, какие степени этих множителей могут быть в наших числах.

Подсказка 2

Например, в 12 двойка входит во 2 степени, а в 17640 в 3. Тогда получаем min(степень 2 в первом числе, степень 2 во втором числе}= 2,max = 3. Попробуйте применить аналогичное рассуждение к остальным делителям и посчитать количество вариантов!

Подсказка 3

Подумаем о минимальной сумме: Мы знаем, что из основной теоремы арифметики следует, что a⋅b= НОК (a,b)⋅НОД(a,b)= 12⋅17640! Тогда мы знаем произведение чисел. Давайте попробуем понять, когда сумма двух чисел минимальна, если произведение фиксировано!

Подсказка 4

Это происходит, когда числа максимально близки друг к другу! Например, 4*5 = 20 = 10*2, то 4+5 < 2+10. Для того, чтобы строго это доказать, можем обратить к производной этого выражения. Осталось подобрать числа, которые будут максимально близки, при этом давать в произведении 12*17640! И проверку не забыть :)

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

Из основной теоремы арифметики следует, что $НО К$ и $НО Д$ двух чисел можно рассматривать как взятие соответственно максимума и минимума по степеням простых множителей в этих двух числах. Пусть $a2,a3,a5,a7$ — степени соответствующих простых в числе $a$ . Пусть $b2,b3,b5,b7$ — степени соответствующих простых в числе $b$ .

Поскольку $2 12= 2 ⋅3$ , то получаем $min{a2,b2}= 2,max{a2,b2}= 3$ , то есть для степеней двоек есть два случая $(a2,b2)= (2,3),(3,2)$ , которые мы считаем одним. Для степеней троек аналогично получаем $(a3,b3)= (1,2),(2,1)$ , для остальных действуем полностью аналогично. В итоге получается $4 2$ случаев. В условии написано, что пары $(a,b)$ неупорядоченные, т.е. $(a,b) =(b,a)$ , поэтому общее число пар должно быть уменьшено вдвое.

Для поиска наименьшей суммы приведём два способа:

Первый способ.

Из основной теоремы арифметики следует, что $a⋅b= НОК (a,b)⋅Н ОД(a,b)= 12⋅17640$ . По неравенству о средних при фиксированном произведении чисел их сумма тем больше, чем больше одно число отличается от другого (сумма вида $x+ 1764x0⋅12$ , производная которой равна $1− 1764x0⋅212$ возрастает при $√------- √---- x> 17640 ⋅12= 12 1470$ ). Поэтому нам нужно найти максимально близкое значение к корню из этого произведения. $12$ это общий НОД, так что остаётся составить из имеющихся множителей ближайшее к $√---- 1470≈ 38$ число.

a′ = 2⋅3⋅5= 30→ b′ =49→ a1+ b1 = 79→ a+ b= 12 ⋅79= 948

Второй способ.

Просто сделаем полный перебор для этих восьми пар, чтобы быстро посчитать и забрать свои баллы за задачу

2 1 0 0 3 2 1 2 22 ⋅31⋅50⋅72+23⋅32⋅51⋅70= 12 +17640 =17652 2 ⋅3 ⋅5 ⋅7 +2 ⋅3 ⋅5 ⋅7 = 588+ 360= 948 22 ⋅31⋅51⋅70+23⋅32⋅50⋅72 = 60 +3528= 3588 22 ⋅31⋅51⋅72+23⋅32⋅50⋅70 = 2940+ 72= 3012 22 ⋅32⋅50⋅70+23⋅31⋅51⋅72 = 36 +5880= 5916 22 ⋅32⋅50⋅72+23⋅31⋅51⋅70 = 1764+ 120 =1884 22 ⋅32⋅51⋅70+23⋅31⋅50⋅72 = 180+ 1176 =1356 22 ⋅32⋅51⋅72+23⋅31⋅50⋅70 = 8820+ 24= 8844

Осталось выбрать наименьшую сумму и выписать ответ.

Ответ:

$8$ пар, наименьшее значение суммы равно $948$

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

Задача 23#80975Максимум баллов за задание: 7

Про натуральные числа $a,b,c$ известно, что $a+ b+ НОД(a,b)= b+ c+ НОД(b,c)= a+ c+Н ОД(a,c).$ Верно ли, что какие-то два числа равны?

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

Первое решение. Предположим, что все числа разные. Без ограничения общности можно считать, что $a< b< c.$ Заметим, что $(a,b)≤ b− a,$ то есть $a+ b+ (a,b)≤2b.$ С другой стороны $b+ c+(b,c)> 2b,$ поэтому равенство невозможно.

Второе решение. Предположим, что все числа различны. Пусть $(a,b)$ — наибольший из трёх НОДов, при этом $b >a.$ Из второго равенства получаем $(a,c)− (b,c)= b− a ≥(a,b).$ Что противоречит максимальности.

Ответ:

Верно

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

Задача 24#97949Максимум баллов за задание: 7

Олег выписал на доску несколько составных натуральных чисел, меньших $1500.$ Оказалось, что наибольший общий делитель любых двух из них равен $1.$ Какое наибольшее количество чисел мог выписать Олег?

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

Простые числа, меньшие $√1500-$ , назовём маленькими. Таких чисел ровно 12 : это $2,3,5,7,11,13,17,19,23,29,31,37.$

Заметим, что у каждого числа Олега есть маленький делитель (иначе оно было бы не меньше $2 43 > 1500$ ), а также у разных чисел разные маленькие делители (иначе НОД этих чисел был бы больше 1). Значит, чисел у Олега не меньше, чем всего маленьких чисел, т.е. не меньше 12.

Пример на 12 чисел строится легко: это числа $2 2 2 2 2 2 2 2 2 2 2 2 2,3 ,5 ,7,11,13 ,17 ,19 ,23 ,29 ,31,37.$

Ответ: 12

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

Задача 25#44068Максимум баллов за задание: 7

Докажите, что существует набор натуральных чисел $a ,a,...,a , 1 2 2019$ для которых $2⋅НОК (a ,a,...,a )=a + a + ...+a . 1 2 2019 1 2 2019$

Источники: Росатом - 2020, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Для каких чисел удобно находить НОК?

Подсказка 2

Для наборов, в которых много единичек!

Подсказка 3

Можно сделать все числа, кроме одного, сделать единицами. Попробуем из равенства подобрать оставшееся!

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

Возьмём

a1 = ...= a2018 = 1,a2019 =2018

Тогда

2⋅НОК(a1,a2,...,a2019)= 2⋅2018

a1+ a2+ ...+a2019 =2 ⋅2018

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

Задача 26#46228Максимум баллов за задание: 7

Пусть $a,b,c$ — натуральные числа. Могут ли наибольшие общие делители пар чисел $a$ и $b,b$ и $c,c$ и $a$ равняться $30!+ 111$ , $40!+234$ и $50!+666$ соответственно?

Источники: Всесиб-2020, 11.2 (см. sesc.nsu.ru)

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

Подсказка!

Мы знаем интересное свойство факториала - он делится на все числа до него. То есть все наши факториалы делятся на 2, 3, 4.... до 30! Попробуйте рассмотреть числа по какому-нибудь полезному модулю

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

Очевидно, что каждый факториал кратен $9.$ При этом $234$ и $666$ делятся на $9,$ откуда $a,b,c$ все кратны $9.$ Но тогда $30!+111$ должно делиться на $9,$ что неверно, поскольку $111 =3⋅37.$

Ответ:

нет

Курсы

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

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

Задача 27#72733Максимум баллов за задание: 7

Докажите, что дробь $m(n+1)+1 m(n+1)−n$ несократима для всех натуральных значений $n$ и $m.$

Источники: Муницип - 2020, 11 класс

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

Подсказка 1

Мы знаем, что дробь a/b несократима тогда и только тогда, когда НОД(a, b)=1. Пусть a=m(n+1)+1, b=m(n+1)-n. Какой алгоритм мы должны проделать, чтобы найти НОД(a, b)?

Подсказка 2

Конечно, алгоритм Евклида! Получается, что наш НОД равен НОД(n+1, m(n+1)-n). Видно, что m(n+1)-n имеет остаток 1 при делении на n+1. Подумайте, когда такое может быть, и завершите доказательство!

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

Предположим, что это не так. Тогда разность между числителем и знаменателем, равная $n+ 1,$ делится на их общий делитель $d> 1.$ Тогда $1= (m(n+ 1)+1)− m(n+ 1)$ делится на $d.$ Противоречие.

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

Задача 28#71908Максимум баллов за задание: 7

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

Источники: СпбОШ - 2019, задача 11.2(см. www.pdmi.ras.ru)

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

Подсказка 1

Предположим, что могло! Значит были изначально какие-то три числа (a < b < c), превратившиеся в одинаковые. Что можно сказать про НОД, которые к ним прибавили?

Подсказка 2

Поняли, что добавленный к a НОД — делитель c - b! Какую оценку тогда можно сделать?

Подсказка 3

Получим, что a + НОД < c!

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

Предположим, что числа $a< b<c,$ написанные изначально на доске, превратились в три одинаковых числа. Заметим, что НОД, прибавленный к числу $a$ , является делителем чисел $b$ и $c,$ а значит, и их разности $c− b.$ Следовательно, он не превосходит $c− b,$ а значит, заведомо меньше разности $c− a.$ После прибавления этого НОДа к $a$ получилось число, меньшее $c,$ и оно не могло совпасть с числом, полученным из $c.$

Ответ: нет

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

Задача 29#39358Максимум баллов за задание: 7

Найдите все такие пары натуральных чисел $a$ и $b$ , что

Н ОК(a,b)= НОД (a,b)+ 19

и докажите, что других нет.

Источники: Школьный этап - 2018, Москва, 9.5

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

Подсказка 1

Давайте сразу обратим внимание на число 19 в правой части. Нам повезло — оно простое! Тогда хорошо бы задуматься о делимости.

Подсказка 2

Ага, d — это наименьший делитель a и b, а значит, и нок на него делится. Какой тогда вывод про d отсюда можно сделать?

Подсказка 3

Верно, так как тогда и 19 должно делиться на d, а оно простое, то d равен либо 1, либо 19. Теперь осталось только аккуратно разобрать два случая. Не забудьте, что если d равен 19, то a и b минимум равны 19.

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

Обозначим за $d$ наибольший общий делитель чисел $a$ и $b$ . Очевидно, что и НОД, и НОК делятся на $d$ . Это означает, что $19= НО К(a,b)− Н ОД(a,b)$ тоже делится на $d$ . Тогда $d$ может быть равен только $1$ или $19$ .

Если $d= 1$ , то тогда $ab= НОК (a,b)=Н ОД(a,b)+ 19 =20$ . Отсюда, небольшим перебором, получаем, что $a$ и $b$ могут быть равны $(1,20)$ , $(20,1)$ , $(4,5)$ , $(5,4)$ .

Если же $d =19$ , то тогда $НОК (a,b)=Н ОД(a,b)+ 19 =38$ . С одной стороны и $a$ , и $b$ не меньше чем $d$ , поэтому они оба хотя бы $19$ . С другой стороны они оба не больше чем $Н ОК(a,b)= 38$ . Причём оба числа должны делиться на $19$ . То есть $a$ и $b$ могут быть только числами $(19,38)$ или $(38,19)$ .

Ответ:

$(1,20)$ , $(20,1)$ , $(4,5)$ , $(5,4)$ , $(19,38)$ , $(38,19)$

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

Задача 30#72736Максимум баллов за задание: 7

В таблице $4× 4$ расставлены $16$ различных натуральных чисел. Для каждой строки и каждого столбца таблицы нашли наибольший общий делитель расположенных в нем чисел. Оказалось, что все найденные восемь чисел различны. Для какого наибольшего $n$ можно утверждать, что в такой таблице найдется число не меньше $n?$

Источники: Иннополис-2018

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

Подсказка 1

Давайте для начала удобно переформулируем условие задачи. Если все НОДы различные, то какое наименьшее значение оно может принимать?

Подсказка 2

Верно, так как столбцов и строк в сумме 8, то и наименьшее значение НОДа равно 8. Давайте теперь посмотрим на одну строку или столбец, и пусть НОД чисел равен d. Тогда какое наименьшее число может быть в этой строке?

Подсказка 3

Ага, так как все числа различны, то и наименьшее число будет хотя бы 4d. Тогда совмещая эти два условия, находим, какое в принципе наименьшее число возможно на доске. Это 32. Теперь вспомним, что различные числа у нас расставляются произвольно. Поэтому осталось только придумать пример, в котором все числа будут не больше 32. То есть это будет вашим контрпримером, что больше 32 число взять нельзя. Победа!

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

Если в каком-то ряду наибольший общий делитель равен $n,$ то в нем есть четыре числа, делящихся на $n,$ a, значит, число, не меньшее, чем $4n.$ Поскольку наибольшие общие делители во всех рядах различны, один из них заведомо не меньше $8.$ Тогда в соответствующем ему ряду должно быть число, не меньшее $32.$ Приведем теперь пример таблицы, в которой все числа не больше $32.$ Наибольшие общие делители по строкам равны $5,6,7$ и $8,$ а по столбцам равны $1,2,3$ и $4.$


5	10	15	20

30	6	18	12

7	14	21	28

8	16	24	32

Замечание. Наибольшие общие делители заведомо должны быть числами от $1$ до $8,$ а ряды с НОДами $6,7$ и $8$ должны быть составлены из тех чисел, которые стоят в соответствующих рядах в таблице из примера (возможно в другом порядке).

Ответ: 32

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

Задача 31#72730Максимум баллов за задание: 7

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

НО К(a,b)= 945 НО К(b,c)=525

Чему может равняться $НОК(a,c)?$ Введите все возможные варианты в порядке возрастания через пробел.

Источники: ШВБ-2017, отборочный тур

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

Подсказка 1

Попробуйте сначала разложить на простые множители числа, которым равны НОК(a,b) и НОК(b,c). Какое разложение могли бы иметь числа a, b, c?

Подсказка 2

НОК(a,b) = 3^3 * 5 * 7, НОК(b,c) = 3 * 5^2 * 7. Тогда a делится на 3^3. А что можно сказать про c? На какие числа делится НОК(a,c)?

Подсказка 3

НОК(a,c) делится на 3^3 * 5^2. Заметим, что НОК(a,b,c) делится на все 3 числа: НОК(a,b), НОК(b,c), НОК(a,c). Тогда НОК(a,b,c) делится 3^3 * 5^2 * 7. Каким тогда может быть НОК(a,c)?

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

Разложим числа на простые множители, так как $33$ встречается только в $HOK (a,b),$ следовательно $a..33, .$ аналогично получаем, что $.. 2 c.5$

{ 3 { .. 3 .( ) HOK (a,b) =945= 3 ⋅25⋅7 ⇒ a...32 ⇒ HOK (a,c).. 33⋅52 HOK (b,c)= 525= 3⋅5 ⋅7 c.5

Заметим, что

(| HOK (a,b,c)... HOK (a,b) { HOK (a,b,c)... HOK (b,c) |( HOK (a,b,c)... HOK (a,c) . .( 3 2 ) ⇒ HOK(a,b,c).. HOK (945,525)⇒ HOK (a,b,c).. 3 ⋅5 ⋅7 .

Учитывая три факта: $(| HOK (a,b,c)... (33⋅52 ⋅7) { HOK (a,b,c)..HOK (a,c), получаем, что |( HOK (a,c)...(33⋅52) .$

$HOK (a,c) =33⋅52,$ например, при $a= 33⋅5,b= 7,c= 3⋅52$ или

$HOK (a,c) =33⋅52⋅7,$ например, при $a= 33⋅5,b= 7,c= 3⋅52⋅7$

Ответ: 675 4725

Интенсивы

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

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

Задача 32#31505Максимум баллов за задание: 7

Какое количество натуральных чисел $a$ обладает следующим свойством: “Наименьшее общее кратное чисел $16$ , $50$ и $a$ равняется $1200$ ”?

Источники: Физтех-2012, 11.8 (см. olymp.mipt.ru)

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

Подсказка 1

Разложите числа на простые множители и вспомните, как представляется НОК через эти множители.

Подсказка 2

Верно, он содержит в себе все самые большие степени вхождения простых множителей. Какие множители ОБЯЗАНО иметь число а, а какие МОЖЕТ? Когда это узнаем, то поймем, что для любого простого р1 мы можем взять все степени простого р2, правило умножения :)

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

2 4 4 2 1200= 5 ⋅2 ⋅3,16= 2,50= 2⋅5

Если $НОК (24,2⋅52,a)= 52 ⋅24⋅3$ , то в числе $a$ может быть любая степень двойки от $0$ до $4$ , любая степень пятёрки от $0$ до $2$ , обязательно первая степень тройки для того, чтобы она появилась в $НО К$ и больше никаких простых чисел, так как их нет в числе $1200.$

Всего получается $5⋅3⋅1= 15$ вариантов составления числа из множителей.

Ответ:

$15$

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

Задача 33#80194Максимум баллов за задание: 7

Какие значения может принимать наибольший общий делитель натуральных чисел $m$ и $n,$ если при увеличении числа $m$ на $6$ он увеличивается в $4$ раза?

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

Подсказка 1

Ага, нам в условии даны НОДы, значит, нужно смотреть на делители чисел, для которых мы знаем НОД. Обратите внимание, что m делится на d, а m + 6 делятся на 4d. Подумайте, как с помощью этого мы можем оценить d.

Подсказка 2

m и m + 6 делятся на d, следовательно, их разность тоже делится на d. Какие значения может принимать d?

Подсказка 3

Не забудем про то, что m + 6 и n делятся на 4, значит, m и n – четные. Что тогда можно сказать про d?

Подсказка 4

d – четное натуральное число, которое является делителем числа 6. Осталось найти пример на d = 2 и d = 6.

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

Пусть

Н ОД(m,n)= d, НОД (m + 6,n)= 4d

Значит, на число $d$ делятся числа $m + 6,m,$ а следовательно и их разность $m +6− m = 6.$ Поэтому возможны лишь следующие случаи: $d =1,d= 2,d =3,d= 6.$

Так как числа $m +6,n$ делятся на $4,$ то числа $m$ и $n$ — четные, значит, число $d$ тоже чётное. Следовательно, $d =2$ или $d= 6.$ Привидём примеры для этих двух случаев.

При $d= 2$ должно быть

НОД (m,n)= 2, Н ОД(m+ 6,n)=8

Этим условиям удовлетворяет, например, пара $n =8,m =10.$

При $d= 6$ должно быть

Н ОД(m,n)= 6, НОД (m + 6,n)= 24

Этим условиям удовлетворяет, например, пара $n =24,m =18.$

Ответ: 2 и 6

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

Задача 34#34157Максимум баллов за задание: 7

Натуральные числа $a$ , $b$ и $c$ таковы, что $НО К(a,b)= 90$ и $НОК(a,c)= 120$ . Найдите $НОК(b,c)$ .

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

Подсказка 1

Сразу же раскладываем результат НОКов на степени простых чисел, потому что именно они влияют на НОК, заметьте, что НОК от двух чисел обязательно говорит о том, что какая-то степень простого точно содержится хотя бы в одном из двух чисел, а ещё, что "a" участвует аж в двух известных нам произведениях, может стоит вести рассуждения про него?

Подсказка 2

Посмотрите, на то, что в одном НОКе есть простое число в большей степени, чем в другом, в каком тогда числе оно содержится?

Подсказка 3

Точно не в "a", потому что иначе оба НОКа содержали бы его, так мы понимаем, что именно "b" делится на 3², подумайте, а в каком числе содержится 2³?

Подсказка 4

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

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

Разложим все НОКи:

2 3 НОК(a,b)= 90= 2⋅3 ⋅5,НО К(a,c)= 120 =2 ⋅3⋅5.

Тогда из первого НОКа мы понимаем, что $a$ или $b$ содержит в своем разложении $32$ . Если $a$ кратно $32$ , то $НОК (a,c)=120$ должен быть тоже кратен $32$ , но это не так. Тогда именно $b$ содержит в своем разложении $32$ .

Аналогично поймем, что $23$ входит в разложение $c$ .

Теперь мы уже знаем, что $НО К(b,c)$ содержит $32$ и $23$ . $НО К(b,c)$ может содержать еще 5 (именно в первой степени).

Приведем примеры для $НОК (b,c) =23⋅32 = 72$ и $НОК (b,c)= 23⋅32⋅5= 360$ :

2 3 1)a= 5,b =2⋅3 ,c=2 ⋅3,

2 3 2)a= 1,b =2⋅3 ⋅5,c=2 ⋅3⋅5.

Ответ: 72 или 360

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

Задача 35#81753Максимум баллов за задание: 7

Последовательность натуральных чисел $a i$ такова, что

НОД(ai,aj)=H ОД(i,j)

для всех $i⁄= j.$ Докажите, что $a = i i$ для всех $i∈ ℕ.$

Источники: Всеросс., 1995, ЗЭ, 10.5(см. math.ru)

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

Подсказка 1:

Глобально в этой задаче нужно просто поиграться с НОДами. Попробуйте рассмотреть НОДы чисел с какими-то интересными индексами.

Подсказка 2:

Например, если рассмотреть НОД членов с индексами i, 2i, станет ясно, что aᵢ ≥ i.

Подсказка 3:

А теперь, предположив, что aᵢ > i, попробуйте рассмотреть НОД такой пары, который с одной стороны равен одному числу, а с другой стороны - другому.

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

Так как каждое $a i$ делится на НОД $(a,a )= i 2i$ НОД $(i,2i)= i$ , то $a ≥i i$ для всех $i∈ ℕ.$ Предположим, что $a >i i$ при некотором $i.$ Тогда, с одной стороны, НОД $(ai,aai) =$ НОД $(i,ai)= i$ (так как $ai$ делится на $i$ ), а с другой стороны, поскольку $aai$ делится на $ai,$ то НОД $(ai,aai)= ai > i.$ Противоречие.

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

Задача 36#136170Максимум баллов за задание: 7

Пусть $НОД(a,b)= (a,b).$ Докажите, что (a) $(a,b)= (a− b,b);$ (b) $(ac,bc)= c⋅(a,b).$

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

(a) Пусть $(a,b)= d 1$ и $(a − b,b)= d . 2$ Тогда, поскольку $a$ и $b$ делятся на $d , 1$ то и $a− b$ делится на $d, 1$ то есть $d1 ≤ d2,$ поскольку является общим делителем $a− b$ и $b.$ Аналогично $d2 ≤d1,$ то есть они равны. Что и требовалось доказать.

(b) Пусть $(ac,bc)= cd1$ и $(a,b)= d2$ (ясно, что $ac$ и $bc$ делятся на $c).$ Тогда $ac- d2c$ и $-bc- d2c$ — целые числа по определению $d2.$ Значит, $d1 ≥ d2.$ Аналогично $-ac d1c$ и $bc- d1c$ — целые, поэтому $d2 ≥ d1,$ то есть $d1 = d2,$ что и требовалось доказать.

Следующая подтема