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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) Существуют ли пять натуральных чисел таких, что ни одно из них не делится на другое, но квадрат любого числа делится на каждое из остальных?

б) Существуют ли пять натуральных чисел таких, что ни одно из них не делится на другое, но квадрат любого числа делится на произведение остальных?

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

Пункт а), подсказка 1

Попробуем построить пример, может быть, такое возможно. Логично рассмотреть какой-то набор простых чисел и попробовать из них поконструировать пять чисел.

Пункт а), подсказка 2

Пусть есть простые числа p₁, p₂, p₃, p₄, p₅. Пусть каждое из пяти чисел включает в своё разложение на простые произведение p₁p₂p₃p₄p₅. Можно ли подкорректировать числа, чтобы выполнялось условие?

Пункт а), подсказка 3

Оказывается, что да. Действительно, пусть первое число есть p₁²p₂p₃p₄p₅, второе — p₁p₂²p₃p₄p₅ и т.д. Тогда условие выполнено!

Пункт б), подсказка 1

Пусть есть такие числа a, b, c, d, e. Тогда запишите условие для квадрата каждого числа, что из них можно вывести?

Пункт б), подсказка 2

Из них следует, что a²b²c²d²e² ⋮ a⁴b⁴c⁴d⁴e⁴. Но тогда 1 ≥ a²b²c²d²e² ≥ 1. Какой вывод можно сделать?

Пункт б), подсказка 3

Конечно же, такое возможно только при a = b = c = d = e = 1, но такой набор не удовлетворяет условию. Отсюда следует ответ!

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

а) Да, существуют. Рассмотрим числа $p2pp p p 1 23 45$ , $p p2p p p 1 23 4 5$ , $p p p2p p 1 23 4 5$ , $p p pp2p 1 2 34 5$ , $pp pp p2 1 2 34 5$ . Для любых пяти попарно различных простых чисел $pi$ этот набор соответствует условию пункта (а).

Замечание. Другой пример: $100 100 101 99 102 98 103 97 104 96 2 ⋅3 ,2 ⋅3 ,2 ⋅3 ,2 ⋅3 ,2 ⋅3 .$

б) Предположим, что существуют такие натуральные числа $a,b,c,d,e$ . Тогда из $2.. a .bcde$ , $2.. b.acde$ , $2.. c.abde$ , $2 .. d .abce$ , $2.. e .abcd$ немедленно следует $2 22 22 ..4 44 4 4 a b cd e .ab cd e$ . Но тогда $2 22 2 2 4 44 44 ab cd e ≥a b cd e$ и $2 22 22 1 ≥a bc de ≥ 1$ , а в таком случае единственно возможная ситуация: $a= b= c= d= e=1$ . Но это противоречит предположению, что ни одно из чисел не делится на другое.

Ответ:

а) да

б) нет

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

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

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

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

Является ли число $123456789012345$ квадратом натурального числа?

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

Подсказка 1

В подобных задачах часто помогает идея разложения квадрата на простые множители. Можно ли что-нибудь сказать про степени вхождения простых в квадрат?

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

Первое решение.

С одной стороны, это число оканчивается на цифру $5$ , то есть делится на $5$ . С другой, число дает при делении на $25$ такой же остаток, что и число, образованное последними двумя цифрами. В нашем случае число, образованное последними двумя цифрами, — это $45$ . Оно не делится на $25$ , значит, и исходное число не делится на $25$ . Итак, число делится на $5$ , но не делится на $25$ .

Заметим, что если число квадрат, то простые числа входят в него в четной степени. Значит, если квадрат делится на 5, то делится и на 25. Но перед нами число, которое делится на $5$ и не делится на $25$ . Значит, оно не квадрат.

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

Это число даёт остаток $8$ при делении на $11$ , однако квадраты могут быть сравнимыми только с $0,1,3,4,5,9$ по модулю $11$ , значит, искомое число не квадрат.

Ответ:

нет

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

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

Существует ли натуральное число, которое при умножении на $2$ станет квадратом, при умножении на $3$ — кубом, а при умножении на $5$ — пятой степенью?

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

Подсказка 1

По сути, в рамках этой задачи вас ничего не должно волновать, кроме степеней вхождения 2,3 и 5, так как все остальное здесь никак не используется. Попробуйте подумать какие должны быть степени вхождения 2,3 и 5.

Подсказка 2

Когда мы умножаем число на 2, то изменяется только степень вхождения 2, а все остальное-остается таким же как было. Значит какими должны быть степени вхождения 3 и 5? Попробуйте применить похожие рассуждения к каждому из чисел 2,3,5.

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

Рассмотрим число $215⋅320 ⋅524.$ Легко видеть, что оно нам подходит. Придумать пример можно примерно так. Рассмотрим степень вхождения $2$ в наше число. Она должна быть нечетным числом (после прибавления единицы станет чётным), делящемся на $3$ и на $5$ (умножение на $3$ и $5$ степень двойки не меняют). Например, нам подходит $15.$ Проделав аналогичные действия для $3$ и $5,$ получим пример.

Ответ:

да

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

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

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

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

Подсказка 1

Пусть у вас есть некий набор из этих чисел, который подходит под условие. Попробуйте преобразовать каждое из чисел по общему правилу так, чтобы набор, который получился после преобразования, также удовлетворял условию про «произведение любых двух-квадрат».

Подсказка 2

Да, нужно поделить каждое из чисел на максимальный квадрат, который делит данное число. Что тогда можно сказать про получившееся число? Какие степени вхождения простых?

Подсказка 3

Да, степени вхождения простых равны 1. Теперь возьмем два любых числа из получившегося набора. Их произведение также будет квадратом(ровно так мы и получили эти числа). Какой вывод можно сделать про эти два числа на основе первого и третьего предложения? А какой тогда вывод можно сделать про все числа?

Подсказка 4

Да, выходит, что эти два числа равны(поскольку если у одного из них есть какое-то простое, которого нет у другого, то степень этого простого будет равна 1 и число точно не будет квадратом). Но мы же взяли два любых числа и сделали такой вывод. Что это значит в рамках всего набора?

Подсказка 5

Это значит, что все числа из получившегося набора равны. Попробуйте вернуть то, на что поделили каждое число из изначального набора и понять, сколько максимум можно взять чисел вида n*x^2(n-их общая часть, х^2-то на что делили) из набора от 1 до 2021. Каким нужно взять n для максимизации кол-ва?

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

Рассмотрим выбранные числа и поделим каждое на наибольший точный квадрат, на который оно делится. Поскольку мы делим на квадрат, то любое произведение останется квадратом. Однако простые множители входят в каждое число не больше, чем в первой степени. Если для каких-то двух чисел этот набор простых оказался разным, то хотя бы одно в произведении будет в нечётной степени и произведение не будет квадратом. Потому все полученные числа совпадают и равны некоторому $m$ . Каждое число из первоначального набора получается умножением $m$ на какой-то квадрат. Если $m = 1$ , то чисел не более $44$ (они будут равны $2 2 2 1 ,2,...44$ ), поскольку $2 45 > 2021$ . Если же $m > 1$ , то $2 2 44 ⋅m ≥ 2⋅44 >2021$ , то есть чисел меньше $44$ .

Ответ:

$44$

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

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

Разложите число $1001$ на два натуральных множителя всеми возможными способами.

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

Сначала разложим число $1001$ на простые множители: $1001= 7⋅11 ⋅13$ . Итак, у этого числа $3$ различных простых множителя. Значит, когда мы раскладываем число на два натуральных множителя, возможны два варианта: либо в одном числе оказываются $3$ простым сомножителя, в другом $0$ , либо в одном числе оказываются $2$ простых сомножителя, в другом $1$ .

В первом случае мы получаем только разложение $1 ⋅1001$ . Во втором случае одно из чисел простое, и у нас есть $3$ разложения: $7⋅143$ , $11⋅91$ , $13⋅77$ .

Ответ: 1 ⋅1001, 7⋅143 , 11⋅91 , 13⋅77

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

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

Можно ли числа от $1$ до $10$ разбить на две группы так, чтобы произведение чисел в одной группе равнялось произведению чисел в другой группе?

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

Рассмотрим простое число $7$ . Никакое другое число от $1$ до $10$ на него не делится, и более того, так как $7$ простое, то никакое произведение остальных чисел от $1$ до $10$ не будет делиться на $7$ . При любом разбиении чисел от $1$ до $10$ на две группы число $7$ попадет только в одну группу. Тогда произведение чисел в этой группе будет делиться на $7$ , а в другой — не будет. Таким образом, произведения чисел в двух группах не могут быть равны.

Ответ: Нет, нельзя

Курсы

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

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

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

Найдите наименьшее число, произведение цифр которого равно $200$ .

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

Разложим число $200$ на множители: $200 =2 ⋅2 ⋅2 ⋅5 ⋅5$ . Число тем меньше, чем меньше в нем знаков. При этом произведение цифр делится на $25$ , значит, в нем обязательно есть цифры, которые делятся на $5$ . Это либо $0$ , либо $5$ . В числе не может быть нулей, так как тогда произведение цифр будет равно $0$ . Значит, в числе обязательно есть две пятерки. Произведение оставшихся цифр равно $8$ . Чтобы получить такое произведение, нужна либо одна восьмерка, либо хотя бы две цифры. Так как цифр должно быть как можно меньше, мы используем одну восьмерку. Итак, число состоит из цифр $5$ , $5$ и $8$ . Нам нужно найти наименьшее число, значит, в начало нужно поставить меньшие цифры, а в конец большие. Получается число $558$ , это и является ответом.

Ответ: 558

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

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

Прямоугольник с целыми длинами сторон разбит на двенадцать квадратов со следующими длинами сторон: $2$ , $2$ , $3$ , $3$ , $5$ , $5$ , $7$ , $7$ , $8$ , $8$ , $9$ , $9$ . Каков периметр прямоугольника?

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

Подсказка 1

Нам известно, что прямоугольник разбит на 12 квадратов с заданными длинами сторон. Что мы можем найти в этой фигуре, зная размеры внутренних квадратов?

Подсказка 2

Верно, мы можем рассчитать её площадь. Также эта площадь равна произведению сторон прямоугольника. Из условия нам известно, что они целые. Разложим значение площади на множители и посмотрим, какие значения могут принимать стороны прямоугольника. Не забывайте, что прямоугольник должен иметь разбиение на квадраты.

Подсказка 3

Так как у нас есть квадрат стороной 9, то обе стороны не меньше 9, и единственное возможное разбиение: 16 и 29. Остаётся только найти периметр такого прямоугольника

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

Найдем площадь прямоугольника

S = 2⋅2+2 ⋅2 +3⋅3+ 3⋅3+ 5⋅5+5 ⋅5 +7⋅7+ 7⋅7+ 8⋅8+ 8⋅8+9⋅9+ 9⋅9=

=464= 2⋅2⋅2⋅2⋅29

Обе стороны прямоугольника должны быть не меньше $9$ , так как присутствует квадрат со стороной $9$ . Тогда единственный вариант разложения числа $464$ на $2$ множителя:

464= 16 ⋅29

Периметр прямоугольника в это случае будет равен $90.$

Замечание. По условию сказано, что прямоугольник разбит. Это значит, что какое-то разбиение существует. Мы сейчас на самом деле доказали, что если разбиение и существует, то только когда этот прямоугольник со сторонами $16$ и $29$ . Так как из условия следует, что разбиение существует, то нам приводить пример этого разбиения не обязательно. Вот если бы мы нашли два возможных варианта ответа, нам бы пришлось дополнительно приводить к каждому из них пример. Тем не менее, пример действительно есть, и дотошный читатель может его без проблем нарисовать.

Ответ: 90

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

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

Сколько различных делителей у числа $201600$ ?

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

Подсказка 1

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

Подсказка 2

Верно, это какое-то число, в разложении которого на простые множители содержатся 2, 3, 5 и 7(в каких-то степенях). Вот, например, некоторые делители этого числа: 10, 15, 70, 420. А давайте думать, как будто мы не считаем их количество, а "собираем" сами(как конструктор), только тогда нам нужно ни одно не пропустить. У нас есть определённые "детали" – это степени чисел, потому что если степень простого другая, то и делитель уже другой. Подумайте из какого множества мы выбираем наши степени? Как можно их интерпретировать?

Подсказка 3

Ага, степени простых в наших делителях просто не может превышать те, которые у нашего исходного числа, иначе это не делитель. Но тогда у нас есть 4 "прозрачных мешочка" с возможными степенями чисел 2, 3, 5 и 7, откуда мы выбираем по одному и комбинируем между собой. Осталось тогда только посчитать с точки зрения комбинаторики, сколькими способами мы можем выбрать степень из каждого "мешочка" и перемножить между собой, так как выбор у нас независимый.

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

Представим число $201600$ в каноническом виде (разложение на простые множители):

7 2 2 201600 =2 ⋅3 ⋅5 ⋅7

Что такое делитель числа? Это какое-то число, каноническое разложение которого имеет вид: $2a ⋅3b⋅5c⋅7d$ , так как если в разложении делителя не могут появиться простые числа, не входящие в число $201600.$

Также на числа $a,b,c,d$ есть ограничения: $0≤ a≤ 7,0≤ b≤ 2,0≤ c≤ 2,0 ≤d ≤1$ , так как в делителе числа степень каждого простого множителя не может превышать степень этого простого в исходном числа (иначе на делитель не поделилось бы, что невозможно по определению). Заметим, что именно такой вид имеют все делители нашего числа, значит, нам всего лишь остается посчитать количество способов выбрать такие 4 числа $a,b,c,d$ (как мы уже увидели: каждая четверка задает какой-то делитель нашего числа, и наоборот, каждый делитель описывается такой четверкой чисел).

Вариантов выбрать четверку таких чисел ровно $8⋅3⋅3⋅2= 144$ , так как способов выбрать число $a$ из чисел от 0 до 7 — 8, аналогично остальные степени. Осталось заметить, что если два делителя совпадали бы, то совпадали и их степени простых в каноническом разложении (то есть наши четверки чисел), однако у нас все четверки различны, значит, и все делители различны.

Ответ:

$144$

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

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

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

Ответ:

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

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

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

Ответ:

Интенсивы

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

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

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

Коля, Серёжа и Ваня регулярно ходят в кинотеатр: Коля бывал в нём каждый 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-й день (считая, что сегодня - нулевой).

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

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

Про два натуральных числа $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.$

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

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

Сколько существует пар натуральных чисел, у которых наименьшее общее кратное равно $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 упорядоченные пары

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

Ответ:

Нет, нельзя

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

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

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

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

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

Ответ:

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

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

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

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

Два натуральных числа $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

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

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

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

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$ в левую часть.

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

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

Докажите, что любые два соседних числа Фибоначчи взаимно просты.

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

Предположим, что найдутся два не взаимно простых соседних числа Фибоначчи $f n$ и $f n+1$ . Обозначим их НОД через $d$ . Тогда предыдущее число Фибоначчи $fn−1 =fn+1− fn$ также делится на $d$ . Рассуждая аналогично, дойдём до начала последовательности Фибоначчи и получим, что все числа делятся на $d$ . Но тогда и $f1 = 1$ делится на $d$ , откуда $d= 1$ , противоречие.

Ответ:

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

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

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

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

Будем решать задачу от противного. Рассмотрим разложение чисел на простые множители, представив каждое число в виде $pα1pα2...pαk 1 2 k$ . Посмотрим, что происходит при переходе от одного числа к другому. У нас либо добавляется, либо пропадает один простой множитель, либо одна из $α$ изменяется на 1. В любом случае сумма $α1+ α2+ ...+ αk$ изменяется на 1, то есть меняет чётность. Значит, чётность этой суммы должна чередоваться — но это невозможно, если чисел всего 2021, то есть нечётное количество.

Ответ: Нет, нельзя

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