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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В тюрьме находятся 100 камер, пронумерованных числами от 1 до 100. Тюремщик Джон Фридом, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру. На третьем этапе он повернул ключ в замке каждой третьей камеры (открыл запертые и запер открытые). Продолжая действовать таким образом, на сотом этапе он повернул ключ только в замке последней сотой камеры, а затем выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели счастливчики.

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

Подсказка 1

Подумаем, что с точки зрения теории чисел значит, что в момент k-го прохода (когда тюремщик проходится по камерам k-й раз и поворачивает замок в каждой k-й) повернулся замок в камере с номером n? Например, в третий раз он меняет состояние 3, 6,… 99 двери, что нам это напоминает?

Подсказка 2

Верно, такое действие означает, что n является кратным числа k, или же k — делитель n. Если в конце дверь оказалась открыта, значит, замок поворачивали нечетное количество раз. Что мы получим, сопоставив эти две мысли?

Подсказка 3

Таким образом, отрыты в конце те двери, у номеров которых нечетное число делителей. У любого числа все (или почти все) делители можно поделить на пары. Подумаем, когда же реализуется это “почти”, которое нас и приведет к решению задачи!

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

Назовем проходом с номером $k$ изменение состояний каждой $k$ -той камеры. Рассмотрим камеру с номером $n$ . Найдем сколько раз она меняла свое состояние с открытой на закрытую или наоборот. Пусть камера поменяла свое состояние на проходе с номером $m$ , тогда номер камеры $n$ делится на $m$ . Таким образом, камера с номером $n$ меняла свое состояние столько раз, сколько различных делителей она имеет.

Заметим, что после каждой нечетной смены состояний камеры она является открытой, а после каждой четной — закрытой. Таким образом, в конце камера будет открыта тогда и только тогда, когда количество смен ее состояний, то есть количество делителей ее номера является нечетным числом. Докажем, что число имеет нечетное количество делитей тогда и только тогда, когда является полным квадратом. Как известно, число делителей числа $a1 a2 al n = p1 p2 ...pl$ равно $σ(n)= (1 +a1)(1+ a2)...(1+ al)$ — нечетное число, но тогда число $1+ ai$ нечетно при всех $i= 1,...,l$ , следовательно, каждое из чисел $ai$ при всех $i=1,...,l$ делится на 2, то есть степень вхождения любого простого числа в $n$ четна, а значит $n$ является квадратом. Аналогично, если $n$ суть полный квадрат, то числа $ai$ при всех $i= 1,...,l$ делятся на 2, следовательно, $σ(n)= (1+ a1)(1+a2)...(1+al)$ — нечетно.

Наконец, открытыми будут те и только те камеры, номера которых есть полный квадрат, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Ответ: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

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

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

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

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

Найдите сумму максимальных нечётных делителей всех чисел от 601 до 1200 включительно.

Источники: по мотивам Росатома - 2024, 11.3

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

Подсказка 1

Зададимся вопросом, что означает тот факт, что у двух чисел из отрезка [601; 1200] одинаковый наибольший нечётный делитель. Если это так, как могут отличаться эти два числа?

Подсказка 2

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

Подсказка 3

Такая ситуация невозможна, ведь на отрезке нет чисел, которые отличаются друг от друга хотя бы в два раза. Какой вывод можно сделать из этого рассуждения?

Подсказка 4

Тогда мы получили, что искомые делители у всех наших чисел различны. Делитель не может быть больше самого числа, поэтому мы не получим делители, превосходящие 1200. Тогда не остаётся выбора, какие нечётные числа брать :)

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

Пусть $S =a +a + ...+a 601 602 1200$ — сумма максимальных нечётных делителей чисел на отрезке $[601,1200]$ , причём $a i$ является максимальным нечётным делителем числа $i$ для всех $i∈{601,602,...,1200}.$

Пусть $n$ — натуральное нечётное число на отрезке $[1;1200].$ Докажем, что $n$ совпадает с $aj$ для некоторого $j ∈ {601,602,...,1200}.$ Предположим противное. Рассмотрим ряд

2 n,2n,2 n,...

Поскольку $n< 601,$ то существует неотрицательное число $i$ такое, что $2in <601,$ а $2i+1n >1200,$ что невозможно.

Таким образом, каждое нечётное число на отрезке $[1;1200]$ совпадает с $a j$ для некоторого $j ∈ {601,602,...,1200}$ . Осталось заметить, что на отрезке $[1,1200]$ каждое второе число является нечётным, следовательно, количество нечётных чисел равно 600, ровно из стольких слагаемых состоит $S$ , то есть никаких других чисел там нет. Наконец, по формуле суммы членов арифметической прогрессии

1200 1+ 3+...+1199= 1200⋅-4--= 1200⋅300= 360000.

Ответ: 360000

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

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

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

0 2 4 2[n2] n−1 C n+ Cn+ Cn+ ...+ Cn = 2

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

Подсказка 1

Хотим построить комбинаторное решение. Надо определиться, из скольких элементов множество мы будем рассматривать и какие объекты считать.

Подсказка 2

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

Подсказка 3

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

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

Пусть имеется множество $N$ из $n$ элементов.

Поймём что слева слагаемое $2k Cn$ это количество подмножеств $N$ мощности $2k,$ а вся сумма тогда равна количеству подмножеств $N,$ содержащих чётное число элементов.

Теперь посчитаем число этих же объектов так: выделим в $N$ элемент $A,$ тогда для каждого подмножества $M$ из оставшегося числа элементов, либо $M$ содержит чётное число элементов, либо $M$ в объединении с $A$ содержит чётное число элементов. Причём таким образом рассмотрены всевозможные чётные подмножества, а значит их $n−1 2 .$

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

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

Докажите тождество

1 2 3 n n− 1 Cn+ 2Cn+ 3C n+ ...+nC n = n2

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

Подсказка 1

Нетрудно понять, какое множество хотим рассматривать (из скольки элементов). Вопрос в том, что за объекты будем считать.

Подсказка 2

Справа непонятно совсем, поэтому давайте думать что за цешка из n по k, умноженная на k.

Подсказка 3

Отлично, цешка из n по k, умноженная на k - это количество подмножеств из k элементов с выделенным главным элементиком. Теперь не составляет труда понять, почему справа считается то же самое.

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

Пусть имеется $n$ школьников, из которых требуется выбрать дежурного и группу помощников для уборки (в группе помимо дежурного как ни странно может никого не быть).

Слагаемое слева $k kCn$ означает число способов выбрать группу из $k$ школьников, а затем дежурного в ней. Сложив по всем $k$ получаем число всевозможных групп с дежурным.

Можно же сначала $n$ способами выбрать дежурного, затем оставшихся распределить в группу или нет. Получаем справа также посчитано число искомых объектов.

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

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

Для $n> 2$ докажите тождество

1 2 2 2 32 n−12 2 n− 2 1⋅(n− 1)⋅(Cn) +2 ⋅(n− 2)⋅(Cn) + 3⋅(n − 3)⋅(Cn)+ ...+ (n− 1)⋅1⋅(Cn ) =n ⋅C2n−2

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

Подсказка 1

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

Подсказка 2

Действительно, квадраты намекают на деление на две группы по n, коэффициенты перед цешками на выбор одного из них. Давайте совмещать идеи.

Подсказка 3

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

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

Пусть имеются два класса $A$ и $B$ по $n$ школьников, из которых требуется выбрать по дежурному, а также включающую их группу из $n$ активистов.

В силу $k n−k Cn =C n$ верно $k 2 k n−k k⋅(n− k)⋅(Cn) = k⋅Cn⋅(n− k)⋅Cn .$

Слагаемое слева $k 2 k⋅(n− k)⋅(Cn)$ количество способов выбрать $n$ активистов из которых в $A$ классе $k$ школьников, один из которых дежурный, остальные в $B$ классе с одним дежурным в нём. Сложив по всем $k$ получаем число всевозможных групп из $n$ активистов, в которых по одному дежурному в каждом из классов.

Можно же сначала $2 n$ способами выбрать в группу активистов по дежурному с классов, а затем из остальных школьников добрать группу. Получаем справа также посчитано число искомых объектов.

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

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

Даны натуральные $n,m$ такие, что $m < n.$ Докажите, что

0 m 0 1 m 1 n m n (− 1) ⋅0 ⋅C n+(−1) ⋅1 ⋅Cn +...+ (−1) ⋅n ⋅Cn =0

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

Подсказка 1

Ищем комбинаторный смысл. Что первое приходит в голову? А вот над объектом, который будем подсчитывать стоит подумать, всё-таки плюсы/минусы весьма непонятно.

Подсказка 2

Ага, вполне логично рассмотреть множество из n элементов (пусть уж они будут детьми), и будем в слагаемых слева выбирать группу и раздавать её участникам m различных шариков. Может есть идеи для объекта?

Подсказка 3

Подсчитать можно следующий объект: распределение шариков детям. Ясно, что любое распределение слева посчитано в нескольких слагаемых. Давайте посчитаем вклад данного распределения шариков в ответ.

Подсказка 4

Для этого можно зафиксировать детей, у которых окажутся шарики при данном распределении (это не все дети, поскольку m<n), и посмотреть на группы добираемые к ним.

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

Предположим, что у нас есть $n$ детей и $m$ разных шариков. И мы хотим эти шарики раздать детям (некоторые дети могут получить больше одного шарика). В левой части в слагаемом $m k k C n$ мы сначала выбираем $k$ детей, которым будем давать шарики, а затем считаем количество способов раздать выбранным $k$ детям эти шарики. То есть один способ раздачи шариков посчитан в нескольких слагаемых. Зафиксируем произвольный способ раздачи шариков. Пусть в нем ровно у $x$ детей есть хотя бы один шарик. Тогда в слагаемом $m k k Cn$ этот способ посчитан 0 раз, если $k <x$ и $k−x Cn−x$ раз, если $k ≥x$ (то есть мы к зафиксированным $x$ детям добавляем еще $k− x$ ). Таким образом, суммарно в левой части наш зафиксированный способ посчитан следующее число раз.

(− 1)xCxn−−xx+ (−1)x+1Cxn+−1x−x+ ...+ (− 1)nCnn−−xx =0

Так как сумма $ℓ Cn−x$ по всем $ℓ$ равна $n− x 2 ,$ а сумма по всем четным $ℓ$ числа $ℓ Cn−x$ равна $n−x−1 2 .$ То есть сумма по всем нечетным $ℓ$ чисел $ℓ Cn−x$ также равна $n−x−1 2 .$ Тогда знакопеременная сумма $ℓ Cn−x$ по всем $ℓ$ равна $0.$ То есть любой зафиксированный способ посчитан в левой части $0$ раз. Значит, и все выражение в левой части равно $0.$

Курсы

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

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

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

Для каждого натурального $n$ докажите, что

n 1 n 1- n 1- n n C n + 2Cn+1+ ...+ 2kCn+k+ ...+ 2nC2n = 2

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

Подсказка 1

Ищем комбинаторный смысл, у деления на степень двойки он не сильно ясен, так что избавляемся от знаменателей.

Подсказка 2

Вот после домножения выглядит уже приличнее. Первым делом, конечно, хочется построить соответствие с всевозможными подмножествами 2n-элементного множества, но тут закопаться можно, что с левой частью совсем непонятно. Давайте добавим ещё элементик и попробуем считать какие-то более необычные объекты.

Подсказка 3

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

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

Сразу домножим наше тождество на $2n.$ То есть будем доказывать, что

n n n−1 n n−k n 0 n 2n 2Cn + 2 Cn+1+ ...+ 2 Cn+k+...+2 C2n = 2

Предположим, что у нас в ряд стоят $2n +1$ человек. И мы хотим выбрать из них хотя бы $n +1$ человека. Понятно, что каждому такому выбору соответствует выбор, в котором меньше $n+ 1$ человека (просто выбрать тех, кого не выбрали в первом способе). Тогда всего таких вариантов ровно $2n+1 2n 2 ∕2= 2 .$ Посчитаем требуемое количество способов по-другому. Посмотрим, где может находиться $(n+ 1)$ -ый человек (считая слева направо). Пусть он находится на $n+ k+1$ месте, где $k≥ 0.$ Тогда среди первых $n +k$ человек у нас есть ровно $n Cn+k$ способов выбрать $n$ человек. А среди оставшихся $2n +1− n− k− 1= n− k$ человек мы можем выбирать любых людей, то есть $n−k 2$ способов. Итого, если $(n +1)$ -ый по счету человек стоит на $(n+ k+ 1)$ -ом месте, то всего вариантов $n−k n 2 Cn+k.$ Сложив способы по всем $k= 0,1,2,...,n,$ получаем требуемое равенство.

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

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

Докажите, что среди чисел Фибоначчи $(f = f +f ,a =1,a = 1) n+1 n n−1 1 2$ бесконечно много

(a) кратных 5;

(b) кратных 2024.

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

(a) Запишем последовательность чисел Фибоначчи в системе остатков по модулю 5:

1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2,...

В последовательности Фибоначчи каждое число определяется двумя предыдущими, поэтому, если пара последовательных чисел повторится, последовательность станет циклической. Тогда длина предпериода или периода не может превышать $5⋅5= 25.$ Остаётся проверить, появится ли в периоде остаток 0 по модулю 5. Выше уже выписана последовательность; можно заметить, что период равен 20 и в нём содержится остаток 0. Следовательно, в последовательности Фибоначчи существует бесконечно много чисел, кратных 5.

(b) Будем рассматривать числа последовательности Фибоначчи по модулю 2024. Из пункта (a) понятно, что здесь также будет период, и его длина не более $2 2024 .$ Назовём состоянием пару последовательных чисел. Состояние $(x,y)$ однозначно определяет следующее число — $(x+ y)$ и предыдущее — $(y− x).$ Это означает, что предпериода нет, так как в каждое состояние $(x,y)$ мы однозначно попадаем из состояния $((y− x),x).$ Значит, период начинается с $(1,1,2,...).$ Пусть последний остаток в периоде равен $A,$ тогда:

(1,1,2,3,5,...,A,)(1,1,2,3,5,...,A,)...

Но так как $A + 1≡1 (mod 2024),$ то $A$ и есть искомое число, кратное 2024. Следовательно, в последовательности Фибоначчи существует бесконечно много чисел, кратных 2024.

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

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

На какие натуральные числа может быть сократима дробь $13n+-8? 8n +5$

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

Подсказка

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

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

Дробь можно сократить на НОД числителя и знаменателя, если он больше $1.$ Попробуем найти НОД числителя и знаменателя. Для этого применим алгоритм Евклида

(13n+ 8,8n+ 5)=(5n+ 3,8n +5)= (5n +3,3n +2)=

= (2n+ 1,3n +2)= (2n +1,n+ 1)=(n,n+ 1) =1

Таким образом, наибольший общий делитель числителя и знаменателя равен $1,$ поэтому дробь несократима.

Ответ:

Дробь несократима

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

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

Колесо длины $19,$ в обод которого вбит гвоздь, достаточно долго едет по колесу длины $102.$ На сколько частей поделят большее колесо отметины от гвоздя?

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

Подсказка 1

Разделим колесо длиной 102 на 102 равных части (длиной 1 по окружности) и каждой точке деления поставим в соответствие число от 0 до 101. Можно полагать, что первая отметина гвоздя находится в точке 0. Также сразу ясно, что все отметины гвоздя могут попасть только в отмеченные точки. А как узнать, в какой точке появится отметина после x полных оборотов колеса длиной 19?

Подсказка 2

Верно! Можно заметить, что отметина появятся в точке, равной остатку от деления числа 19x на 102. Перепишем это утверждение по определению остатку 19x = 102y + r. Осталось узнать, какие r могут получиться! Как это сделать?

Подсказка 3

Точно! Давайте представим уравнение в виде 19x + 102y = r (переобозначим и вместо -y напишем y). Можно заметить, что 19 и 102 взаимно просты. Что можно сказать о решениях этого диофантового уравнения?

Подсказка 4

Конечно! По теореме о линейном представлении НОД найдутся такие числа a и b, что 19a + 102b = 1. А можно ли теперь узнать, какие r можно представить в виде 19x + 102y = 1?

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

Количество частей равно количеству отметин. Вычислим число отметин. Выберем первую точку на колесе длины $102,$ на которой появилась отметина, и обозначим ее $0.$ От этой точки против часовой стрелки отметим последовательно точки $1,2,...,101$ так, чтобы расстояние по окружности между соседними точками было равно $1.$ Таким образом, мы разбили колесо длины $102$ на $102$ равные части. Заметим, что отметины гвоздя могут появляться только в отмеченных точках, так как первая отметина появилась в точке $0$ и длина у меньшего колеса целая. Каждая точка, в которой появится отметина гвоздя, может быть вычислена, как остаток от деления $19x$ на $102,$ где $x$ — количество полных оборотов, совершенных от первого попадания в точку $0$ колесом длины $19$ к данному моменту. Таким образом, из деления с остатком получаем $19x =102y+ r,$ где $r$ — остаток.

Вопрос задачи сведен к вопросу о том, какие числа $0 ≤r≤ 101$ могут быть представлены в виде $19x− 102y.$ Очевидно, что $19$ и $102$ взаимно просты, поэтому имеется пара $(x0,y0)$ такая, что $19x0− 102y0 = 1.$ Умножим это равенство на $0 ≤r≤ 101$ и получим $19(rx0)− 102(ry0)= r.$ Следовательно, все числа от $0$ до $101$ рано или поздно получатся, значит, отметины будут во всех отмеченных точках, и количество частей, на которые разделится колесо, равно $102.$

Ответ:

$102$

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

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

Найдите с помощью алгоритма Евклида линейное представление НОД чисел $37$ и $11.$

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

Подсказка

Можно обозначить a = 37 и b = 11, а затем, выполняя действия алгоритма Евклида, параллельно выполнять аналогичные действия с числами a и b. Например, 37 - 11 = a - b. Что получится в конце?

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

Обозначим для удобства $a =37,b=11.$ Проделаем алгоритм Евклида, дополнительно указывая представления чисел в виде линейных комбинаций чисел $a,b$

(a,b)=(37,11)= (37− 3⋅11,11)= (4,11) =(a− 3b,b)

(a − 3b,b)= (4,11)= (4,3)=(a− 3b,b− 2a+6b)= (a− 3b,7b− 2a)

(a− 3b,7b − 2a)= (4,3)=(1,3)= (a− 3b− 7b+ 2a,7b− 2a)= (3a − 10b,7b− 2a)

Очевидно, что $37$ и $11$ взаимно просты, поэтому мы уже нашли линейное представление НОД — это $3a− 10b =3⋅37− 10⋅11.$

Ответ:

$3⋅37− 10⋅11$

Интенсивы

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

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

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

Докажите, что если для некоторых натуральных $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.$

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

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

Существуют ли натуральные $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$ — противоречие.

Ответ:

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

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

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

Какое наибольшее значение может иметь наибольший общий делитель чисел $n2+ 20$ и $(n+ 1)2+ 20$ для натуральных $n?$

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

Подсказка 1

Для удобства в этой задаче можно полагать, что в НОДе числа могут быть отрицательными, а сам он всегда положителен. Первый шаг алгоритма Евклида дает ((n+1)²+20,n²+20) = (2n+1, n²+20). Можно ли теперь по алгоритму Евклида сделать так, чтобы получившееся выражение превратилось в выражение вида (a+b,ab)?

Подсказка 2

Конечно! Вычтем n(2n+1) из второго аргумента. Тогда получится (2n+1,-n²-n+20). Это равно (2n+1, (n+5)(n-4)). Тогда (n+5) + (n-4) = 2n+1. Предположим, что наш НОД больше 1. Что можно сказать о простых числах, которые его делят?

Подсказка 3

Верно! Можно утверждать, что простые числа, делящие выражение вида (ab, a+b) делят оба числа a и b. Тогда, поскольку (n+5,n-4)=(9,n-4), то все простые делители такого НОДа равны 3. Что можно сказать об n?

Подсказка 4

Верно! Тогда n = 3s + 1. Подставляем и получаем, что наш НОД равен 3(3(s+2)(s-1), 2s+1). Поскольку 2s + 1 = (s+2) + (s-1), то можно снова применить утверждение о простых делителях выражений (ab,a+b) и получить, что наш новый простой делитель либо равен 3, либо делит оба числа s+2 и s-1. Чему тогда равен этот простой делитель?

Подсказка 5

Верно! Тогда этот простой делитель равен 3. Получаем, что s = 3k + 1. После подстановки получается 9(9k(k+1),2k+1). Числа k и k+1 взаимно просты, тогда из утверждения о выражениях (a+b,ab) получается, что k(k+1) и 2k+1 взаимно просты. Какое наибольшее значение может принимать наш НОД?

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

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

2 2 2 2 ((n+ 1)+ 20,n + 20)=(2n+ 1,n + 20)= (2n+ 1,− n − n +20)= (2n +1,(n +5)(n − 4))

Заметим, что $2n+ 1= (n +5)+ (n − 4).$ Докажем небольшую лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $p$ — простое число. Тогда $p|ab$ и $p|(a+ b)$ $⇔$ $p|a$ и $p|b.$

_________________________________________________________________________________________________________________________________________________________________________________

Таким образом, если числа $2n+ 1$ и $(n+ 5)(n− 4)$ имеют общий делитель $d >1$ то все простые числа $p|d$ являются делителями чисел $n+ 5$ и $n− 4.$ Поскольку $(n+ 5,n− 4)= (9,n− 4),$ то все такие простые числа являются делителями $9.$ Тогда, если простое число делит и $2n +1,$ и $(n+ 5)(n− 4),$ то оно равно $3.$ Таким образом, $n= 3s+1,s∈ ℕ.$ Получаем после подстановки в выражение для НОД

((3s+ 6)(3s− 3),6s+ 3)= 3(3(s +2)(s− 1),2s+ 1)

Заметим, что $(s+2)+ (s− 1)= 2s +1.$ Тогда по лемме простое число, делящее $(3(s+ 2)(s− 1),2s+ 1)$ либо равно $3,$ либо делит оба числа $s+ 2$ и $s− 1.$ По алгоритму Евклида $(s+ 2,s− 1)= (3,s− 1).$ Таким образом, любое простое число, делящее $(3(s+ 2)(s− 1),2s+ 1),$ равно $3.$ Следовательно, $s= 3k +1.$ Снова подставляем!

3(27k(k+1),3(2k+ 1))= 9(9k(k+ 1),2k+1)

Снова заметим, что $2k +1 =k +(k+ 1),$ однако числа $k$ и $k +1$ взаимно просты, поэтому общих делителей у $k(k+ 1)$ и $2k+ 1$ нет. Это значит, что $(9k(k +1),2k+ 1)≤ 9,$ тогда $2 2 ((n +1) +20,n + 20)≤ 81.$ Положим $k =4,$ тогда $2k +1 =9,$ и $(9k(k+1),2k +1)= 9.$ Так как $k= 4,$ получаем $s= 13$ и $n= 40.$ Таким образом, мы получили и пример, и оценку.

Ответ:

$81$

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

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

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

Предположим, что такой набор существует, $λ$ — наибольший общий делитель чисел этого набора. Тогда для любой четверки чисел $4 {λai}i=1$

4∏ ∑4 4∏ ∑4 λai | (λai)4, а значит, ai | a4i, i=1 i=1 i=1 i=1

то есть условие делимости выполнено и для набора, полученного из исходного делением каждого из чисел на $λ.$ Таким образом, можно считать, что числа набора взаимнопросты в совокупности.

Предположим, что в наборе существует число $d,$ кратное простому числу $p,$ большему $3.$ Тогда для любых трех чисел $a,b,c$ набора, отличных от $d$ верно, что

4 4 4 4 4 4 4 a + b +c ≡ a + b +c + d ≡abcd≡ 0 (mod p) (∗)

В частности, для произвольного числа $e$ набора, отличного от чисел $a,b,c,d$

4 4 4 4 4 4 a +b + c ≡0 ≡b + c +e (mod p)

Таким образом,

a4 ≡ e4 (mod p)

для любых двух различных чисел набора, отличных от $d.$ Пусть $q$ — остаток при делении числа $a4$ на $p,$ тогда в силу $(∗)$

0≡ a4+b4+ c4 ≡3q4 (mod p)

следовательно, $q$ кратно $p,$ то есть все числа набора кратны $p,$ что невозможно, следовательно, среди чисел набора не существует числа, которое имело бы простой делитель, больший $3.$

Таким образом, все числа набора суть степени тройки. Поскольку все числа набора взаимно просты в совокупности, в наборе участвует единица. Тогда для произвольных чисел $3x,3y,3z > 1$ набора

1+ 34x+ 34y +34z кратно 3x+y+z

что неверно, поскольку

1 +34x+ 34y+ 34z ≡1 (mod 3)

следовательно, такого набора не существует.

Ответ:

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

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

Количество различных чисел в нашей последовательности ограничено, значит, все числа имеют понятный вид! Осталось разделить отношение первых k на отношение первых m и понять, при каком условии получается точный квадрат!

Подсказка 3

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

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

Рассмотрим произведения первых $k$ чисел в ряду. Всего таких произведений $2n+ 1$ (также учитваем произведение, в котором $0$ простых чисел, будем считать, что оно равно $1$ ).

Ясно, что произведение чисел любой подпоследовательности этого ряда — частное каких-то двух произведений первых чисел.

Пусть ряд состоит из чисел $p1,p2,...,pk(k ≤n).$ Тогда любое произведение первых чисел имеет вид $α1 α2 αk p1 p2 ...pk .$ Если мы найдём два произведения первых чисел, у которых чётности соответствующих $αi$ совпадают, то мы найдём подпоследовательность ряда, произведение чисел которой равно квадрату.

Всего существует $k 2$ наборов чётностей $αi$ (каждое $αi$ либо чётное, либо нет). Осталось заметить, что $k n n 2 ≤2 < 2 + 1.$ Значит, найдутся два произведения с одинаковым набором чётностей у $αi,$ получили требуемое.

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

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

Докажите, что при любом натуральном $n$ значение выражения

[n ] [n ] [n] √- 1 + 2 +...+ n +[ n]

является чётным.

Источники: Индийская национальная олимпиада

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

Заметим, что выражение $[n] k$ равняется количеству чисел, которые не превосходят $n$ и делятся на $k.$ Воспользуемся фактом, что если число не является точным квадратом, то оно имеет чётное количество делителей, а если число является точным квадратом, то оно имеет нечётное число делителей. Тогда рассмотрим выражение

[n] [n] [n] 1 + 2 + ...+ n

Из утверждений выше получаем, что каждое число, не превосходящее $n,$ будет учтено в нём столько раз сколько у него делителей. Значит, каждый не точный квадрат будет учтён чётное число раз, а каждый точный квадрат — нечётное число. Но заметим, что число точных квадратов, не превосходящих $n,$ равно $√- [n].$ Тогда в выражении

[ ] [ ] [ ] √- n1 + n2 +...+ nn +[ n]

каждое число учтено чётное число раз, т.е. выражении число равно сумме чётных чисел, а, следовательно, и само является чётным.

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

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

Докажите тождества

k k k− 1 m k k m −k (a) Cn = Cn−1+C n− 1; (b) Cn Cm = CnCn−k

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

(a) Левая часть — количество способов выбрать из $n$ человек ровно $k.$ Посчитаем это по-другому. Зафиксируем одного человека. Если он в нашей группе, то остается выбрать еще $k− 1$ человека из $n− 1.$ Если он не в нашей группе, то из оставшихся $n − 1$ людей надо выбрать $k.$ Поскольку рассмотренные случаи не пересекаются, а ответы для каждого из них соответственно равны $k−1 Cn−1$ и $k Cn−1,$ то общий ответ $k k−1 Cn−1+ Cn−1.$

(b) Рассмотрим задачу: найти количество способов выбрать $m$ человек из $n$ и составить из этих $m$ человек команду из $k$ человек. Можно сначала зафиксировать $k$ человек, после чего добавить к ним еще $m − k$ из оставшихся $n− k.$ Это соответствует правой части уравнения: $k m −k Cn⋅Cn−k .$ С другой стороны, можно делать ровно то, что написано в условии: сначала выбрать $m$ человек, а затем среди них выбрать $k$ человек. Это соответствует левой части уравнения: $m k Cn ⋅Cn.$

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

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

Тождество Вандермонда. Докажите, что

k 0 k 1 k−1 k 0 Cn+m = CnCm + CnCm + ...+ CnCm

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

Рассмотрим следующую задачу. Пусть у нас есть группа из $m$ девочек и $n$ мальчиков. Нужно найти количество способов выбрать среди них $k$ человек. С одной стороны, это количество равно $k Cm+n.$ С другой стороны, можно воспринимать ее так: сумма количеств способов выбрать $i$ мальчиков и $k− i$ девочек. Для данного $i$ это количество равно $i k−i CnCm ,$ где $0≤ i≤k.$ Суммируем эти выражения по всем $i$ и получаем выражение в правой части.

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