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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#105489

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

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

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

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

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

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

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

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

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

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

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

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

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

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

Задача 2#111331

Сколькими способами можно представить число $n= 2401 ⋅3500$ в виде произведения двух натуральных чисел $x$ и $y,$ где $y$ делится на $x?$

Источники: Физтех 2025 11.2 (olymp-online.mipt.ru)

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

Подсказка 1

Заметим, что x и y имеют в разложении на простые множители только двойки и тройки. Как соотносятся их степени вхождения, если y делится на x?

Подсказка 2

Да, степень вхождения и двойки, и тройки в y больше, чем в x. Тогда можно обозначить эти степени вхождения переменными, а дальше перемножить варианты степени вхождения двойки и тройки в y.

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

Заметим, что делитель числа $n$ не может иметь простые множители кроме 2 и 3, так как само $n$ имеет только эти простые числа в своем каноническом разложении. Отсюда любой делитель $n$ имеет вид $a b 2 3,$ где $a,b∈ ℤ$ и $0≤ a≤401,0≤ b≤500.$

Тогда $y$ так же имеет вид $a b y = 23$ с аналогичными условиями на $a$ и $b.$ Отсюда

n 24013500 401−a 500−b x= y = -2a3b--=2 3

Рассмотрим отношение чисел $y$ и $x:$

a b y = -4012−a3500−b = 22a−40132b−500 x 2 3

Получившееся число является целым, так как $y$ делится на $x$ по условию. Это значит, что $2a− 401≥ 0$ и $2b− 500≥ 0,$ то есть $a ≥201$ и $b≥250.$

Таким образом, у нас есть $401 − 201+ 1= 201$ способ выбрать число $a,$ на каждый из которых есть $500− 250+1 =251$ способ выбрать число $b,$ откуда количество способов выбрать пару $a$ и $b$ равно $201⋅251= 50451.$ При этом каждая такая пара задаёт разложение числа $n$ на множители $x$ и $y,$ где $y$ делится на $x,$ поэтому $50451$ и будет ответом.

Ответ:

50451

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

Задача 3#120571

Для каждого натурального числа $n∈ ℕ$ возьмём $x = n2+ 300 n$ и $y = n$ НОД $(x,x ). n n+1$ Чему равно максимально возможное значение $yn?$

Источники: Бельчонок - 2025, Вариант 4, 11.2(см. dovuz.sfu-kras.ru)

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

Подсказка 1

Как мы умеем искать НОД у двух чисел? Каким методом можно воспользоваться?

Подсказка 2

Воспользуйтесь алгоритмом Евклида!

Подсказка 3

(n²+300, (n+1)² + 300) = (n²+300, 2n+1). Далее цепочку продолжите сами ;)

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

Будем пользоваться соотношениями:

Н ОД(u,v)= НО Д(u±v,v)

НОД (u,2v+ 1)= НО Д(2u,2v+ 1)

Запишем цепочку равенств:

Н ОД(n2+300,(n+ 1)2+300)= НОД(n2+ 300,2n+ 1)=

= НО Д(2n2 +600,2n+ 1)= НОД(600− n,2n+ 1)=Н ОД(1200− 2n,2n +1)= НОД (1201,2n+ 1)

Остаётся заметить, что последняя величина не превосходит 1201, и равенство достигается при $n= 600.$

Ответ:

$1201$

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

Задача 4#121578

Верно ли, что число

2026 2024 − 2024⋅2026+ 2025

делится на $20232?$

Источники: Надежда Энергетики - 2025, 11.5(см. www.energy-hope.ru)

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

Подсказка 1

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

Подсказка 2

Чтобы было удобнее раскладывать, можно попробовать заменить какое-то число на переменную x.

Подсказка 3

Для удобства заменим 2024, чтобы было проще работать со степенью. Осталось проверить делимость на (x - 1)².

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

Заметим, что

2026 2026 2024 − 2024⋅2026+2025= 2024 − 1− 2023⋅2026

Пусть $x= 2024.$ Тогда выражение примет вид

x2026 − 1− 2026(x− 1)=(x− 1)(x2025+ x2024+...+x +1)− 2026(x− 1)=

= (x − 1)(x2025 − 1+ x2024− 1+ ...+x − 1)

Нам необходимо проверить делимость на $20232 = (x− 1)2.$

Одна из скобок уже равна $(x − 1),$ осталось проверить делимость второй на $(x − 1).$ А это верно, так как каждая из разностей вида $(xk− 1)$ делится на $(x− 1),$ а, значит, и сумма тоже делится.

Ответ:

Верно

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

Задача 5#121760

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

Источники: Турнир городов - 2025, устный тур, 11.2(см. turgor.ru)

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

Подсказка 1:

Ясно, что m > n. Давайте для удобства обозначим m = n + k и будем считать количество таких k. Осталось записать условие на равенство сумм, пользуясь формулой суммы членов арифметической прогрессии.

Подсказка 2:

Пусть первой наименьшее число среди n чисел равно x. Тогда у вас должно получиться равенство, в котором участвуют x, k и n. Обратите внимание на чётность множителей.

Подсказка 3:

У вас должно было получиться равенство (2x + k - 1)k = 2n². Давайте заметим, что у 2n² нечётное количество нечётных делителей. А сколько значений х соответствует распределению делителей по скобочкам?

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

Решение 1. Ясно, что $m > n,$ положим $m =n +k,$ где $k$ — натуральное, и будем искать количество подходящих $k,$ то есть таких $k,$ для которых уравнение

x +(x+ 1)+...+(x+ k− 1)+ ((x+ k)+ ...+(x+ k+ n− 1))= (x+ k+n)+ ...+ (x+k +2n− 1)

имеет решение в натуральных $x.$ Преобразуем, пользуясь формулой суммы арифметической прогрессии. Получим:

(2x+-k−-1)⋅k- (2x+-2k+-n−-1)⋅n- (2x-+2k+-3n−-1)⋅n- 2 + 2 = 2

Умножив на $2$ и приведя подобные слагаемые получаем:

(2x+ k− 1)k= 2n2 (∗)

Слева в уравнении (*) два сомножителя разной чётности, дающие в произведении $2 2n ,$ при этом левый сомножитель больше правого. Наоборот, если зафиксировать нечётный делитель $d$ числа $2 2n ,$ то, зная $d,$ найдём дополнительный делитель $′ 2n2 d = d ,$ и далее из системы $′ ′ k= min{d,d} ,2x+ k− 1= max{d,d }$ однозначно находим натуральное $x$ (равное $(d−d′+1) |-2|-- ).$

Итак, количество подходящих $k$ равно количеству нечётных делителей числа $2n2,$ которое, в свою очередь, равно количеству всех делителей числа $s2,$ где (нечётное) $s$ получается из $n$ делением на наибольшую степень двойки, входящую в разложение $n.$ Но количество делителей точного квадрата нечётно (так как все делители числа $s2,$ кроме $s,$ можно разбить на пары: $t↔ st2 ,$ и только делитель $s$ остаётся без пары).

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2.

Очевидно, $m =n +k,$ где $k$ натуральное. Запишем равенство из условия в виде

(a+1)+ ...+ (a +m )=(a+ m +1)+ ...+ (a+ m +n)

Отсюда:

2 a = n-− k+-1 (∗∗) k 2

Чтобы условие задачи выполнялось с данным $k,$ необходимо и достаточно, чтобы $a$ было целым неотрицательным.

Положим $n =s⋅2r,$ где $s$ нечётное, $r$ целое неотрицательное. Тогда $a$ будет целым в двух случаях: (а) если оба члена равенства (**) целые $;$ (б) если оба они полуцелые $.$ Первый случай имеет место, когда $k$ — нечётный делитель числа $n2,$ то есть делитель числа $s2.$ Количество $c$ таких значений $k$ нечётно, поскольку это всевозможные делители полного квадрата. Второй случай означает, что

k= d⋅22r+1,

где $d$ — делитель числа $s2.$ Между первым и вторым множеством значений $k$ есть биекция: каждому $k$ из первого множества соответствует число $2nk2$ из второго множества, и обратно.

Пусть $(f,g)$ — пара из указанной биекции, причём $f <g.$ Тогда при $k =f$ получится неотрицательное $a,$ а при $k =g$ отрицательное. Действительно, в силу $(∗∗)$ требуется проверить неравенство

k(k+1)≤ 2n2.

Но $f(f + 1) ≤fg = 2n2, g(g+ 1)> gf =2n2,$ что и требовалось. Поэтому подходящих значений $k$ будет ровно $c,$ то есть нечётное количество.

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

Задача 6#123926

Степень вхождения простого числа $p$ в натуральное $a$ равна $α,$ а степень вхождения $p$ в натуральное $b$ равна $β.$ Докажите, что степень вхождения $p$ в $НО Д(a,b)$ равна $min(α,β),$ а степень вхождения $p$ в $НОК(a,b)$ равна $max(α,β).$

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

Вспомним, что одно натуральное число делится на другое тогда и только тогда, когда для каждого простого множителя, входящего в разложение первого и второго чисел, степень вхождения в первое число не меньше степени вхождения во второе число.

Не умаляя общности, пусть $α≤ β,$ тогда $min(α,β)= α,max (α,β)= β.$

1) Пусть НОД $(a,b)= d.$ По определею НОД $(a,b)$ — это наибольший общий делитель $a$ и $b,$ то есть и $a,$ и $b$ делятся на $d,$ и нет числа, большего, чем $d,$ на которое так же делятся и $a,$ и $b.$

Если степень вхождения $p$ в $d$ больше $α,$ то $a$ не будет делиться на $d$ — противоречие.

Если степень вхождения $p$ в $d$ меньше $α$ и равна $γ,$ то $′ γ d =d ⋅p ,$ где $′ d$ и $p$ взаимнопросты. Тогда и $a,$ и $b$ делятся на $′ d ,$ а так же и $a,$ и $b$ делятся на $α p.$ Из взаимнопростости $′ d$ и $p$ следует, что и $a,$ и $b$ делятся на $′ α d ⋅p ,$ при этом $′ α d ⋅p > d$ — противоречие.

Получается, степень вхождения $p$ в $d$ равна $α.$

2) Пусть НОК $(a,b)= k.$ По определею НОК $(a,b)$ — это наименьшее общее кратное $a$ и $b,$ то есть $d$ делится и на $a,$ и на $b,$ и нет числа, меньшего, чем $k,$ которое так же делится и на $a,$ и на $b.$

Если степень вхождения $p$ в $k$ меньше $β,$ то $k$ не будет делиться на $b$ — противоречие.

Если степень вхождения $p$ в $k$ больше $β$ и равна $ω,$ то $k =k′⋅pω,$ где $k′$ и $p$ взаимнопросты. Рассмотрим число $k′⋅pβ.$ Так как $k$ делится на $a$ и $b,$ то в $k′$ входят все простые числа, входящие в $a$ и $b,$ кроме $p,$ при этом их степень не меньше, чем в $a$ и $b.$ Получатся, $k′⋅pβ$ делится и на $a,$ и на $b,$ при этом $k′⋅pβ <k$ — противоречие.

Получается, степень вхождения $p$ в $k$ равна $β.$

Курсы

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

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

Задача 7#126725

Найдите все натуральные $n,$ для которых существует такое чётное натуральное $a,$ что число

2 n (a− 1)(a − 1)...(a − 1)

является точным квадратом.

Источники: ВСОШ, ЗЭ, 2025, 9.3 (см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте сначала вручную разобраться с n = 1, 2, 3. Для этих случаев достаточно вспомнить утверждение о том, что если произведение двух взаимно простых чисел — квадрат, то каждое из них также является квадратом. В частности, при n = 3 надо поработать с нодами скобок a - 1, a + 1, a² + a + 1. Быть может, этот ход мыслей можно развить и для больших n?

Подсказка 2:

Итак, скорее всего вы поняли, что n = 1, 2 подойдёт, а n = 3 — нет. Чем остальные случаи отличаются. Например, если n > 3, то оно находится между двумя натуральными степенями двойки. То есть существует такое натуральное k, что 2^k ≤ n < 2^{k + 1}. Подумайте, как это можно использовать.

Подсказка 3:

Если записать скобку a^{2^k} – 1 как (a^{2^{k – 1}} – 1)(a^{2^{k – 1}} + 1), то становится ясно, что все произведение состоит из скобки a^{2^{k – 1}} + 1 и скобок вида a^m – 1. А как насчёт того, чтобы посмотреть на нод выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с произвольной скобкой a^m – 1?

Подсказка 4:

Нод второго выражения и a^m – 1 кратен ноду первого выражения и a^m - 1. Чтобы было проще работать, вот вам интересный факт: нод второй скобки и a^m – 1 равен a^нод(2^k, m) – 1. Осталось поработать с нодом 2^k и m.

Подсказка 5:

Исходя из выбора k, ясно, что нод 2^k и m не превышает 2^{k – 1}. Попробуйте теперь показать, что ноды выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с a^m – 1 совпадают. Кажется, это раскроет идею подсказки 3.

Подсказка 6:

Стало быть, a^{2^{k – 1}} + 1 — точный квадрат. А вас это не смущает?

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

Заметим, что для $n= 1$ подойдёт $a =10.$ Для $n =2$ подойдёт $a= 8.$

Предположим, что для $n =3$ нашлось требуемое число $a.$ Тогда число

2 3 3 2 (a − 1)(a − 1)(a − 1)= (a− 1) (a +1)(a + a+ 1)

является точным квадратом. Поскольку

2 a + a+ 1= a(a+ 1)+1,

числа $a+ 1$ и $a2+ a+ 1$ взаимно просты. Раз число $a+1$ нечётно, числа $a+ 1$ и $a− 1$ также взаимно просты. Следовательно, числа $a+ 1$ и $(a− 1)(a2+a +1)$ — точные квадраты. В частности, число $a+ 1$ при делении на 3 может давать лишь остаток 0 или 1, а тогда число $a− 1$ не делится на 3. Отсюда

2 НО Д(a− 1,a + a+1)= НОД (a − 1,(a +2)(a − 1)+ 3)= НО Д(a − 1,3)=1,

значит, числа $a− 1$ и $a2 +a+ 1$ также являются точными квадратами. Но второе являться квадратом не может, поскольку

a2 < a2 +a+ 1< (a+1)2.

Противоречие.

Осталось доказать, что требуемого $a$ не существует при $n ≥4.$ Предположим, что такое $a$ нашлось. Возьмём такое натуральное $k ≥2,$ что $2k ≤n < 2k+1.$ Поскольку

a2k − 1= (a2k−1 − 1)(a2k−1 + 1),

число

(a− 1)(a2 − 1)...(an− 1)

представляется в виде произведения $2k−1 a +1$ и нескольких множителей вида $m a − 1,$ где $1≤ m ≤n$ и $k m ⁄=2 .$

Докажем, что множитель $2k−1 a +1$ взаимно прост со всеми остальными множителями в этом разложении. Пусть $2k−1 a + 1$ и $am − 1$ имеют некоторый общий делитель $d.$ Тогда и НОД $k a2 − 1$ и $am − 1$ кратен $d.$ Но

k k НОД(a2 − 1,am− 1)= aНОД(2 ,m)− 1.

Поскольку $k m ⁄= 2$ и $k+1 m ≤n < 2 ,$ число $m$ не может делиться на $k 2 .$ Таким образом, $k Н ОД(2,m )$ — степень двойки, не превосходящая $k−1 2 .$ Следовательно, $2k−1 a − 1$ делится на НОД $2k a − 1$ и $m a − 1,$ а, значит, делится и на $d.$ Поскольку $a$ чётно, числа $2k−1 a − 1$ и $2k−1 a + 1$ не имеют общих делителей, отличных от 1, значит, $d= 1,$ что и требовалось.

Множитель $2k−1 a + 1$ взаимно прост со всеми остальными множителями в произведении, являющемся точным квадратом, поэтому он сам является точным квадратом. Тогда $k−1 a2 +1$ и $k−1 a2$ — отличающиеся на 1 квадраты натуральных чисел, что невозможно. Значит, наше предположение неверно, и для $n≥ 4$ требуемых чисел $a$ не найдётся.

Ответ:

$n =1$ и $n =2$

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

Задача 8#126992

Обозначим за $d(n)$ число натуральных делителей числа $n$ (включая единицу и само число). Найдите все такие $n,$ что $n =33⋅d(n)$

Источники: ИТМО - 2025, 10.8 ( см. olymp.itmo.ru)

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

Подсказка 1

Так как n представимо как 33 * d(n), то, не мудрствуя лукаво, легко понять, что n делится на 3 и на 11. Зная эти факты, можем записать, как будет выглядеть число n в разложении на простые множители.

Подсказка 2

Зная информацию из подсказки 1 и равенство из условия можно записать несколько уравнений. Подставив одно в другое, можно понять, что 3 и 11 могут входить в состав числа n только в очень маленьких степенях.

Подсказка 3

Да! Действительно. Пусть в состав числа n 3 входит в степени l, а 11 в степени k. Тогда надо разобрать всего 2 случая: k = l = 1; k = 1, l = 2. Осталось только аккуратно рассмотреть, что получается в этих случаях и какие из них реализуются.

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

Очевидно, $n$ делится на $3$ и на $11.$ Разложим $n$ в произведение степеней простых чисел:

l k k1 km n= 3 ⋅11 ⋅p1 ⋅...⋅pm

Тогда

d(n)= (l+1)(k+ 1)(k1+ 1)...(km + 1)

Разделив $n$ на $33⋅d(n)$ получим

3l−1 11k−1 pk11 pkmm l+1-⋅k+-1-⋅k1+1-...⋅km-+1 =1

Заметим, что все дроби в этом произведении, кроме первых двух, гарантированно не меньше $1$ (равенство достигается только в случае $1 12+1 =1$ ). Тогда как минимум одна из первых двух дробей не превосходит единицы, как и их произведение.

Вторая дробь не превосходит единицы только при $k= 1.$ В этом случае она равна $12.$ Первая же дробь может быть равна как $12$ при $l= 1,$ так и $2−1 32+1-=1$ при $l= 2.$ При этом при $k> 1$ вторая дробь составляет как минимум $131,$ а при $l> 2$ первая дробь составляет как миниумм $332+1 = 94.$ И то и другое больше двух, что делает произведение дробей больше единицы.

Осталось разобрать два случая: $k= l= 1$ и $k= 1,l= 2.$ В первом случае и первая, и вторая дробь равны $12,$ а их произведение составляет $14.$ Значит, произведение остальных должно быть равно $4.$ Множитель $2$ в числителе может получиться только одно из оставшихся простых чисел равно $2.$ Рассмотрим дроби вида $2k1, k1+1$ которые не превосходят $4,$ это :

-21- 1+ 1 = 1

22 4 2+-1 = 3

3 -2--= 2 3+ 1

-24- = 16-= 31 4 +1 5 5

Нас устраивают только дроби, у которых после сокращения в числителе остаётся хотя бы $4.$ Если мы используем дробь $4, 3$ нам понадобиться ещё один множитель $3$ в числителе, которого у нас нет, если же возьмём $16- 5 ,$ нам понадобится ещё дробь с $5$ в числителе, то есть минимум $5 2,$ что уже даёт слишком большое произведение.

Во втором случае первая дробь равна $1 2,$ а вторая равна $1.$ Значит, произведение остальных должно быть равно $2.$ Мы можем добавить к ним только $-23- 3+1 = 2$ и получить единицу в качестве произведения.

Значит,

l k 3 2 3 n= 3 ⋅11 ⋅2 = 3 ⋅2 ⋅11= 72⋅11= 792

Ответ:

$792$

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

Задача 9#127178

Пусть $a$ и $b$ — целые числа. Докажите, что если $a2+ 9ab+b2$ делится на $11,$ то и $a2− b2$ делится на $11.$

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

Выделим полный квадрат:

2 2 2 2 2 a + 9ab+ b = a − 2ab+ b+ 11ab =(a− b) + 11ab

По условию

2 (a− b) + 11ab

кратно 11, кроме того и $11ab$ тоже кратно 11. Значит, $(a− b)2$ тоже обязано быть кратно 11. Так как 11 — это простое число, то это означает, что $a− b$ кратно 11.

Теперь распишем $a2− b2$ как разность квадратов и получим $(a− b)(a+ b)$ , а, так как ранее определили, что множитель $a− b$ кратен 11, то и все произведение тоже будет делиться на 11.

Ответ:

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

Задача 10#128119

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

Источники: БИБН - 2025, 10.5 (см. www.unn.ru)

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

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

Раз просят наименьшее, то давайте будем пробовать добавлять по одному числу, начиная с 0. Что будет, если у нас всего одно число во второй группе?

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

Сумма оставшихся чисел не меньше 190 — сильно много. Теперь для двух чисел во второй группе.

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

211 = (a+1)(b+1), бывает ли так?

Пункт а, Подсказка 4

211 — простое. Приведите пример для трёх чисел.

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

Как можно снизу оценить произведение через количество выбранных чисел?

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

Если чисел хотя бы 6, то произведение хотябы 6! = 720 > 210. Значит, чисел не больше 5.

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

Предположим, подойдёт пятёрка (1,2,3,4,x). Найдите x.

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

a) Сумма всех чисел от 1 до 20 равна 210. Очевидно, что во второй группе больше одного числа, так как в противном случае оно было бы равно сумме оставшихся 19 чисел, тоесть не меньше, чем $1+2 +...+ 19= 190.$ Покажем, что на самом деле во второй группе больше двух чисел. Действительно, в противном случае для чисел $a$ и $b$ из второй группы выполнялось бы равенство

210− a− b= ab

211= (a+1)(b +1)

Раз 211 — простое число, следовательно, данное уравнение не имеет решений на промежутке от 1 до 20. Приведем пример второй группы из 3 чисел. Сначала возьмем единицу, будет верно, что

209− a− b= ab

210= (a+1)(b +1)

Нам подойдут тройки ${1;9;20}$ и ${1;13;14}.$

б) Докажем, что чисел во второй группе меньше 6. В противном случае, наименьшее произведение чисел второй группы равнялось бы

1⋅2⋅3 ⋅4 ⋅5 ⋅6 =720> 210

Получили противоречие с равенством произведения чисел второй группы и суммы чисел первой группы. Подберем пример для случая, когда во второй группе 5 чисел. Предположим, что подойдет пятерка вида $(1;2;3;4;x),$ где $x ∈[5;20].$ Должно выполниться условие

210− 10− x= 24x

x= 8

Подойдет набор $(1;2;3;4;8).$

Ответ:

а) 3; б) 5

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

Задача 11#128852

Натуральные числа $a$ и $b$ таковы, что сумма $a2+ b2 b a$ целая. Докажите, что оба слагаемых целые.

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

Возьмём произвольное простое число $p.$ Пусть $v(a)=α, p$ $v(b) =β. p$ По условию число

a2 b2 a3+-b3- b + a = ab

является целым. Значит,

vp(a3+ b3)≥ vp(ab)= α+ β.

Возникает два случая, которые нужно рассмотреть: если $α= β$ и если $α⁄= β.$ В случае равенства мы не сможем вычислить $3 3 vp(a +b ),$ зато можно сразу сказать, что тогда $2α≥ β$ и $2β ≥ α,$ что в силу произвольности выбора $p$ даёт требуемое. Пусть теперь $α ⁄=β.$ Условие инвариантно относительно перестановки $a$ и $b.$ Значит, можно, не умаляя общности предположить, что $α <β.$ Тогда

vp(a3+ b3)= min(3α,3β)= 3α.

Следовательно, $3α ≥ α+ β,$ или же $2α ≥β.$ Это даёт делимость $2 a$ на $b,$ а делимость $2 b$ на $a$ вытекает из $β > α.$

Интенсивы

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

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

Задача 12#128898

Найдите все натуральные числа $m,n$ и простые числа $p,$ удовлетворяющие уравнению $mnnp = pm.$

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

В правой части стоит степень простого числа, поэтому в левой части единственным простым делителем является $p,$ то есть $m = pa,$ $b n =p .$ Подставим эти выражения в исходное равенство:

apb bp pa (p ) ⋅(p) = p

Степень вхождения $p$ с обеих сторон должна быть одинаковой:

b a ap + bp= p

Рассмотрим случай $b=0.$ Тогда $a =pa,$ но $a< 2a ≤ pa,$ так что это невозможно. Теперь вернёмся к равенству степеней вхождения $p.$ Поскольку в правой части стоит степень $p,$ степени вхождения $p$ в $apb$ и $pb$ должны быть равны. Значит, $pb−1|b$ и

b≥pb−1 ≥ 2b−1

Пусть $b≥3.$ Тогда $2b−1 > b,$ так что решений нет. При $b= 2$ получаем $p= 2$ и

4(a+ 1)= 2a

Это уравнение не имеет решений в целых числах. Теперь остался случай $b= 1.$ Равенство на степени вхождения превращается в

ap+ p= pa

Снова сделаем оценку $pa−1 ≥2a−1,$ то есть $a +1 ≥2a−1.$ Такое неравенство выполняется при $a ≤3.$ При $a= 0$ решений нет, при $a= 1$ решений тоже нет. При $a = 2$ получаем $p= 3, m = 9, n= 3.$ При $a= 3$ получаем $p= 2,$ $m =8,$ $n =2.$

Ответ:

$(m,n,p)=(8,2,2)$ или $(9,3,3)$

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

Задача 13#128900

Даны натуральные числа $m,n,k.$ Оказалось, что $mk + nk+m$ делится на $mn.$ Докажите, что $m$ — точная $k$ -я степень натурального числа.

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

Будем считать $k≥ 2,$ иначе утверждение очевидно. Пусть $p$ — простой делитель $m$ и $a$ — его степень вхождения. Пусть $b$ — степень вхождения $p$ в $n.$ Предположим, что $b= 0.$ Тогда выражение из условия не делится на $p,$ то есть не делится и на $mn.$ Итак, $b≥1.$ Посчитаем степень вхождения $p$ в $k k m + n +m.$ В $mn$ это $a+b >a.$ Значит, в $k k m + n + m$ степень вхождения $p$ строго больше, чем $a.$ Рассмотрим это выражение по модулю $a+1 p ,$ оно даёт остаток 0. Так как $ak ≥2a ≥a+ 1,$ то $k m$ делится на $a+1 p ,$ следовательно, $k n + m$ тоже. Но $m$ имеет степень вхождения $p$ в точности $a,$ поэтому такую же степень вхождения должно иметь и $k n.$ Значит, $a= kb,$ то есть степень вхождения $p$ в $m$ делится на $k,$ что и требовалось доказать.

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

Задача 14#128975

Назовем год замечательным, если номер года делится на сумму двузначных чисел, из которых этот номер составлен. Например, $2025$ год — замечательный, поскольку $2025$ делится на $20+ 25=45.$ Сколько ещё замечательных годов в XXI веке (с $2001$ по $2100$ год включительно)?

Источники: ПВГ - 2025, 10.2 (см. pvg.mk.ru)

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

Заметим, что года, у которых третья цифра 0, не могут быть замечательными, так как эти годы не составлены из двух двузначных чисел. Так что можем обозначить год как $---- 20ab,$ при этом $a∈ [1;9],$ $b∈[0;9].$

Рассмотрим разность

---- -- -- -- 2 2 20ab− (20+ ab)= 2000 +ab− 20−ab= 1980=2 ⋅3 ⋅5⋅11

Так как замечательное число $20ab$ делится на $20+ ab,$ рассмотренная разность также должна делиться на $20+ab.$ Перечислим делители числа $1980,$ лежащие на отрезке $[20 +10;20 +99]=[30;119]:$

2 2 2⋅11= 44, 3⋅11= 33, 3 ⋅11= 99, 5⋅11= 55, 2⋅3⋅11 =66,

2⋅5⋅11= 110, 32⋅5= 45, 2⋅32⋅5= 90, 22⋅3⋅5 =60, 2⋅3⋅5= 30, 22⋅32 =36

Так как подходящих делителей 11, в XXI веке 11 замечательных годов, то есть кроме 2025 есть ещё 10 замечательных годов.

Ответ:

$10$

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

Задача 15#34950

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

02 12 n2 n (C n)+ (Cn)+ ...+ (Cn) =C 2n

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

Подсказка 1

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

Подсказка 2

Правая часть чётко говорит брать 2n элементов и считать число подмножеств из n элементов. Слева же в каждом слагаемом перемножают цешки из n. Что бы это могло значить?

Подсказка 3

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

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

Пусть имеется множество $N$ из $n$ элементов. Тогда справа $Cn 2n$ количество его подмножеств мощности $n.$

Посмотрим теперь, что будет слева. Разделим $N$ на два непересекающихся подмножества $A$ и $B$ по $n$ элементов в каждом. В силу $k n−k Cn = Cn$ верно $k2 k n−k (Cn) =(Cn)⋅(C n ).$ Тогда $k 2 (Cn)$ количество способов выбрать в $N$ подмножество мощности $n,$ что $k$ элементов лежат в $A,$ остальные $n − k$ в $B.$ Проходясь по всем $k$ получаем всевозможные подмножества $N$ мощности $n.$

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

Задача 16#76655

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

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть $φ (n)$ - функция Эйлера числа $n.$ (Количество чисел от $1$ до $n$ взаимно простых с $n.$ ) Тогда для любого натурального числа $n >1$ справедливо неравенство

∑ n2 d < φ(n)- d|n

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если $n =pα1pα2...pαk, 1 2 k$ то

∑ 2 α1 2 α2 2 αk d =(1+ p1+p1+ ...+ p1 )(1+ p2+ p2+ ...+ p2 )...(1+ pk +pk+ ...+ pk ) d|n

Используя формулу суммы геометрической прогрессии, получаем:

∑ d= (1+ p + p2 +...+ pα1)(1+ p +p2+ ...+ pα2)...(1+ p +p2+ ...+ pαk)= d|n 1 1 1 2 2 2 k k k

(pα11+1 − 1)(pα22+1− 1)...(pαk+1− 1) = ----(p1−-1)(p2-− 1)...(pkk− 1)--.

Функция Эйлера вычисляется по формуле $φ(n)=pα11−1(p1− 1)pα22−1(p2− 1)...pαkk− 1(pk− 1).$ Тогда чтобы получить $φ(n)$ в знаменателе, домножим числитель и знаменатель на $pα11−1pα22−1...pαkk−1$

(pα11+1−-1)(pα22+1−-1)...(pαkk+1−-1)= (p1− 1)(p2− 1)...(pk− 1)

α1−1 α2−1 αk−1 α1−1 α2−1 αk−1 = p1--p2α1−.1..pk--(pα12−1-− 1)(p2-α−k−11)...(pk---−-1)= p1 (p1− 1)p2 (p2− 1)...pk (pk− 1)

(p2α1 − pα1−1)(p2α2− pα2−1)...(p2αk− pαk−1) p2α1p2α2...p2αk n2 = --1----1-----2--φ(2n)------k----k----< -1--2φ(n)--k--= φ(n)

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

∑ -n2- 100n < d|nd< φ(n).

Тогда

100n< -n2-⇒ φ(n)< n-. φ(n) 100

То есть количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $-n- 100.$

Рассмотрим два случая: $n$ делится на $100$ и $n$ не делится на $100.$

1. Число $n$ делится на $100.$ Тогда можно разбить числа от $1$ до $n$ на $n-- 100$ групп по $100$ идущих подряд чисел. Если количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n-- 100$ , то хотя бы в одной группе не будет числа взаимно простого с $n$

2. Число $n$ не делится на $100.$ Тогда среди чисел $2$ до $n$ можно выделить $-n- [100]$ групп по $100$ идущих подряд чисел. Если в каждой группе будет число взаимно простое с $n$ , то чисел взаимно простых с $n$ хотя бы $n [100]+ 1$ ( $1$ тоже взаимно проста с $n$ ). Это противоречит тому, что количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n 100-$

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

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

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

Задача 17#78889

Можно ли вычеркнуть из произведения $1!⋅2!⋅3!⋅...⋅56!$ один из факториалов так, чтобы произведение оставшихся было квадратом целого числа?

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

2 2 2 28 2 1!⋅...⋅56!=(1!) ⋅2⋅(3!) ⋅4 ⋅...⋅(55!) ⋅56=2 ⋅(1!⋅3!⋅...⋅55!)⋅28!

Отсюда видно, что, вычеркнув $28!,$ мы получим квадрат числа $214⋅1!⋅3!⋅...⋅55!.$

Ответ:

Да, можно

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

Задача 18#78899

Дано $41$ различное натуральное число, меньшее $1000.$ Известно, что среди любых трех из них есть два, дающих в произведении точный квадрат. Докажите, что среди этих чисел есть точный квадрат.

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

Предположим, что среди этих чисел нет точного квадрата. Обозначим через $p ,...,p 1 n$ все простые числа, меньшие $1000.$ Заметим, что по условию каждое выписанных чисел раскладывается в произведение $p1,...,pn$ в некоторых степенях. Каждое из наших простых чисел входит в одно выписанное число в четной или нечетной степени. Сопоставим каждому выписанному числу последовательность из $0$ и $1$ длины $n.$ Число на $i$ - ой позиции будет равно $1,$ если $pi$ в ходит в выписанное число в нечетной степени и $0$ в противном случае (на самом деле это и есть бесквадратная часть, про которую мы говорили в теории). Предположим, что среди последовательностей выписанных чисел есть три различные. Тогда для трех соответствующих этим последовательностям чисел не выполнено условие (два числа в произведении могут давать точный квадрат, только если четности вхождения каждого $pi$ - ого одинаковые).

То есть мы показали, что различных последовательностей может быть не больше $2.$ Обозначим эти последовательности через $a1,...,an$ и $b1,...,bn.$ Обозначим через $a a b b a =p11⋅⋅⋅pnn,b= p11 ⋅⋅⋅pnn .$ Очевидно что $a⁄= b.$ Считаем. что $a< b,$ тогда $a ≥2,b≥ 3,$ так как при $a= 1$ мы получим, что числа являются квадратами, а мы предположили, что их нет. Каждое из выписанных чисел дает точный квадрат либо при делении на $a,$ либо при делении на $b.$ Причем для чисел, которым соответствуют одинаковые последовательности, эти квадраты должны быть различными. Рассмотрим наибольшее выписанное число, которому соответствует последовательность $a$ -шек. Оно равно $a⋅s2$ для некоторого натурального $s,$ откуда $s2 ≤ 500,$ то есть $s≤ 22.$ Но тогда количество выписанных чисел, которым соответствует первая последовательность, не превосходит $22.$ Аналогично поступаем со второй последовательностью. Опять рассматривает наибольшее число $bh2 ≤1000,$ откуда $h2 ≤ 1000∕3,$ то есть $h≤ 18,$ откуда таких чисел не больше $18.$ То есть всего чисел не больше, чем $22+ 18 =40.$ Получили противоречие с количеством данных чисел.

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

Задача 19#78906

Найдите все такие составные числа $n,$ что для любого разложения на два натуральных сомножителя $n= xy$ сумма $x +y$ является степенью двойки.

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

Подставив $x= 1,y = n,$ получим, что $n= 2k− 1$ для некоторого натурального $k.$ Пусть $n =ab,$ где $a≥ b>2,$ и пусть $a +b= 2t$ для некоторого натурального числа $t.$ Очевидно, что $k >t.$ Тогда

k t 2 +2 = ab+ a+b+ 1= (a+ 1)(b+1), 2k− 2t = ab− a− b+ 1= (a− 1)(b− 1)

Перемножив эти равенства, получим, что число $(a − 1)(a +1)× (b− 1)(b+ 1)$ делится на $2t 2 .$ Но двойка входит в одно из чисел $b− 1$ или $b+1$ в первой степени, а во второе — в степени, не большей $t− 1.$ Аналогично для чисел $a − 1$ и $a+ 1.$ Следовательно, делимость на $2t 2$ возможна, только если в обеих упомянутых оценках двойки входит в степени ровно $t− 1.$ Это возможно, лишь если $t−1 t−1 b= 2 − 1,a =2 + 1$ (поскольку $a≥ b$ и $t a+b =2$ ). Тогда $k= 2t− 2$ и $k 2 − 1$ делится на $3.$ Значит, можно считать, что в наших рассуждениях выбрано $b =3.$ Тогда $a= 5,$ и $n= 15$ — единственное подходящее число.

Ответ:

$n =15$

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

Задача 20#79329

Докажите, что если $n+ 1$ делится на $24,$ то сумма всех делителей натурального числа $n$ тоже делится на $24.$

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

Подсказка 1

Видим, что задача на остатки! Тогда сразу же нужно разложить число 24 на степени простых и понять, какие остатки имеет n при делении на эти числа.

Подсказка 2

Число n имеет остаток 2 при делении на 3 и остаток 7 при делении 8. Теперь наша задача — понять что-то про сумму всех делителей числа n. Поскольку мы ничего не знаем про эти делители в совокупности, можно попробовать разбить их на пары определённым образом. (Почему делителей у n чётное число?)

Подсказка 3

Наши пары делителей — d и n/d. Произведение каждой пары равно n и имеет соответствующие остатки при делении на 3 и 8. Осталось осуществить небольшой перебор и понять, какие пары остатков могут давать d и n/d при делении на 3 и 8!

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

Так как $n+ 1$ делится на $3$ и $8,$ то $n$ при делении на $3$ даёт остаток $2,$ а при делении на $8$ — остаток $7.$

Разобьём делители на пары вида $(d,n∕d),$ так как число $n$ не может быть полным квадратом ввиду противоречия с делимостью на $3.$ Заметим, что если $d$ даёт остаток $1$ при делении на $3,$ то $n∕d$ даёт остаток $2$ и наоборот. Поэтому сумма делителей в каждой такой паре кратна $3.$

Аналогично, сумма делителей в каждой такой паре кратна $8.$

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