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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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Максимум баллов за задание: 7

Сколькими способами можно представить число $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Максимум баллов за задание: 7

Для каждого натурального числа $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Максимум баллов за задание: 7

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

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Максимум баллов за задание: 7

Дано натуральное число $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Максимум баллов за задание: 7

Степень вхождения простого числа $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Максимум баллов за задание: 7

Найдите все натуральные $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Максимум баллов за задание: 7

Обозначим за $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Максимум баллов за задание: 7

Пусть $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Максимум баллов за задание: 7

Докажите, что $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Максимум баллов за задание: 7

Натуральные числа $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#128859Максимум баллов за задание: 7

Формула Лежандра. Пусть $p$ — простое число, $n$ — произвольное натуральное число. Тогда

∑ [ n-] vp(n!)= α≥1 pα .

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

Покажем, что это выражение равно сумме степеней вхождения $p$ в каждое из чисел от $1$ до $n.$ Заметим, что слагаемое $[ n-] pα$ равно количеству чисел, кратных $α p$ и не превосходящих $n.$ Отсюда следует, что число со степенью вхождения $p,$ равной $m,$ было посчитано по $1$ разу в каждом из слагаемых

[n] [ n] [ n] p , p2 ,..., pm-.

То есть оно было посчитано ровно $m$ раз. Получили требуемое.

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

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

Найдите все натуральные числа $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)$

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

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

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

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

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

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

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

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

Подсказка 1

Замечательный год должен быть составлен из двух двузначных чисел! Какие можно сразу отбросить?

Подсказка 2

Обозначим год 20ab, где a принимает значения от 1 до 9. Рассмотрим 20ab - (20 + ab). Что можно сказать про его делимость?

Подсказка 3

Получили 1980=2² * 3² * 5 * 11. Осталось только подсчитать подходящие делители!

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

Заметим, что года, у которых третья цифра 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$

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

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

Является ли простым число $2...27999...9$ ? (сначала $2$ написано $2024$ раза, затем $9$ написано $2024$ раза).

Источники: Миссия выполнима - 2025, 10.4 (см. www.fa.ru)

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

Подсказка 1

Что легче доказать: простоту числа или обратное утверждение?

Подсказка 2

Конечно же, второе! Попробуем явно найти делитель.

Подсказка 3

Банальные признаки делимости не подходят, но может, есть что-то другое? На что всегда делится число, записанное одинаковыми цифрами?

Подсказка 4

Казалось бы, задача почти решена, но мешает 7. Вот если бы на 7 делились числа из двоек и девяток...

Подсказка 5

Осталось только всё строго записать! Представьте исследуемое число в виде суммы, в которой каждое из слагаемых кратно 7.

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

Заметим, что число $111111 =7 ⋅15873$ делится на $7.$ Тогда числа $222222= 2⋅111111$ и $999999= 9⋅111111$ тоже делятся на $7.$ Также на $7$ делится и число $22799 =7 ⋅3257.$ Откуда следует, что число

4043 2027 2022 2016 2...279...9= 222222⋅10 + ...+222222⋅10 + 22799⋅10 + 999999⋅10 +...+ 999999

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

Ответ: Нет

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

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

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

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

При каких натуральных $n$ число $20n+ 16n− 3n − 1$ делится на 323?

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

__________________________________________________________________________________________________

Лемма. Число $n n a − b$ кратно числу $a− b,$ где $a,b$ — натуральные, $n$ — неотрицательное целое.

Доказательство. По формуле сокращенного умножения

n n n−1 n−2 n−2 n−1 a − b =(a− b)(a + a b+ ...+ ab + b )

Значит, $an− bn$ кратно $a − b.$

______________________________________________________________________________________________________________________________________________________

Заметим, что $323= 17⋅19,$ при этом 17 и 19 взаимнопростые, откуда число делится на 323 тогда и тогда тогда, когда оно делится на 17 и на 19.

Для начала рассмотрим делимость на 17. По лемме $n n 20 − 3$ кратно $20− 3= 17,$ то есть наше число делится на 17 тогда, когда $n 16 − 1$ кратно 17. При этом $n n 16 ≡ (− 1) (mod 17),$ то есть $n 16 − 1$ кратно 17 только при чётном $n.$

Теперь рассмотрим делимость на 19. По лемме $n n 20 − 1$ делится на $20− 1= 19,$ а при $n =2k$ число $n n 2k 2k 16 − 3 = 16 − 3$ делится на $2 2 16 − 3 =13⋅19.$

Итак, исходное число делится на 323 при чётных $n.$

Ответ:

При четных $n$

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

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

Пусть $n >1,$ а

1= d1 < d2 <...<dk =n

— все натуральные делители числа $n.$ Оказалось, что ровно для одного индекса $2≤ i≤k − 1$ число $di−1di+1$ не делится на $di.$ Может ли число $n$ быть квадратом натурального числа?

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

Подсказка 1:

Обратите внимание на то, что если dᵢ₊₁ является простым числом, то dᵢ₋₁ должно делиться на dᵢ, чего не может быть. Подумайте над этим.

Подсказка 2:

Рассуждения из предыдущей подсказки должны вызывать резонный вопрос: сколько может быть простых делителей в разложении n?

Подсказка 3:

Их ровно 2. То есть n = p₁ˣp₂ʸ, p₂ > p₁. Попробуйте рассмотреть какую-нибудь удобную тройку делителей dᵢ₋₁, dᵢ, dᵢ₊₁ и применить к ней условие.

Подсказка 4:

Давайте возьмём такое i, что dᵢ = p₂, тогда d = p₁ᵏ, где k — некоторое натуральное число. Чему может быть равно dᵢ₊₁?

Подсказка 5:

dᵢ₊₁ = p₁p₂ и x = k. Если вы к этому ещё не пришли, обязательно обоснуйте эти равенства на основании предыдущих подсказок. Попробуйте теперь подобрать ещё какую-нибудь тройку делителей, для которых не выполняется делимость из условия.

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

Предположим, что $n$ является квадратом натурального числа. Пусть $n= p2α1...p2αs. 1 s$ Рассмотрим произвольное $2≤ i≤s.$ Пусть $pi = dj,$ понятно, что $j ≥3.$ Тогда, если $dj−1$ делит $dj−2dj,$ то $dj−1$ делит и $dj−2,$ так как $(dj−1,dj)= 1.$ Но $dj−2 < dj−1$ — противоречие. Значит, если у $n$ есть хотя бы три разных простых делителя, то есть хотя бы два индекса $1≤ i≤ k,$ для которых число $di−1di+1$ не делится на $di$ — противоречие. Также понятно, что у $n$ должно быть хотя бы два простых делителя, иначе таких индексов $i$ бы не было, поскольку $n$ было бы степенью простого числа.

Осталось разобрать случай, когда у $n$ ровно два различных простых делителя $p1 <p2.$ Если $p2 = dj,$ то $k dj−1 =p1,$ $k−1 dj−2 = p1 .$ Как мы знаем, для $i= j− 1$ число $di−1di+1$ не делится на $di.$ Поэтому для всех остальных индексов должна быть выполнена делимость. Это в частности означает, что она выполнена для $i=j,$ то есть $dj+1$ делится на $p2.$ Тогда он равен $p2p1,$ и это больше $k+1 p1 .$ А значит, у $n$ нет делителя $k+1 p1 ,$ то есть $2α1 =k.$ Теперь пусть $2 p2 = dl,$ $l> j+1.$ Тогда $k dl− 1 =p2⋅p1,$ $k−1 dl−2 =p2⋅p1 .$ То есть $dl−1$ не делит $dl−2dl$ — противоречие!

Ответ:

нет

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

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

Серёжа выписал в ряд все натуральные делители некоторого натурального числа $N$ в порядке возрастания. Оказалось, что для любых двух соседних чисел в этом ряду $N$ делится и на разность этих чисел. Докажите, что для любых соседних чисел $a> b$ в этом ряду $ab$ делится на $a− b.$

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

Подсказка 1.

По условию мы можем работать с выражениями вида N/(a−b). С другой стороны, нужно получить, что ab/(a−b) является целым числом. Значит, нужно как-то попытаться сократить на N.

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

Заметим, что если $a$ и $b$ — два соседних делителя числа $N,$ то $N- a$ и $N- b$ — тоже два соседних делителя числа $N.$ Применяя для этих двух делителей условие задачи, получаем, что $N$ делится на $N- N- b − a ,$ то есть

N ab N-−-N-= a−-b ∈ ℤ b a

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

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

Пусть $1= d < d < ...< d = n 1 2 k$ — все натуральные делители натурального числа $n,$ являющегося точным квадратом. Может ли среди $di$ оказаться поровну чисел вида $3k+ 1$ и $3k+2?$

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

Подсказка 1.

Для начала рассмотрим случай, в котором n не делится на 3. Тогда делителей вида 3k не будет. Может ли выполняться условие задачи в этом случае?

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

Предположим, что такое возможно. Пусть $n= 32am,$ где $m$ не делится на 3. Тогда $m$ тоже является точным квадратом, причём делители $n,$ не кратные 3, совпадают с делителями $m.$ У $m,$ как у точного квадрата, нечётное число делителей, все они не делятся на 3, так что разбить на две равные группы их точно не получится.

Ответ:

нет

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