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

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

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

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

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

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

Подтемы раздела делимость и делители (множители)

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

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

Задача 1#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-$

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

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

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

Задача 2#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.$

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

Задача 3#83298

Найти сумму максимальных нечетных делителей каждого из целых чисел на отрезке $[61;120]$ .

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

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

Подсказка 1

Интересно, что чисел от 61 до 120 ровно столько же, сколько нечётных от 1 до 120.

Подсказка 2

Чем нечётные отличаются от чётных? Наличием степени двойки. Тогда как удобно представить все числа?

Подсказка 3

Из первого замечания про количество нечётных хочется посмотреть, а сколько чисел вида n * 2ᴷ для каждого нечётного n (меньшего 120) лежит в промежутке от 61 до 120.

Подсказка 4

Оказывается, для каждого такого n одно своё n * 2ᴷ в промежутке от 61 до 120. Попробуйте понять, почему это так, и досчитать искомую сумму нечётных n!

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

Для каждого нечетного числа $n$ в промежутке 1 до 119 рассмотрим числа вида $n⋅2k$ , где $k∈ ℕ∪ {0}.$ Докажем, что для каждого $n$ найдётся ровно одно число вида $k n⋅2$ на промежутке от 61 до 120.

Пусть на нашем промежутке не нашлось нужного числа. Тогда должна найтись такая пара чисел $k k+1 (n⋅2 ;n ⋅2 )$ , что

k k+1 n⋅2 ≤ 60, n⋅2 ≥121,

что невозможно, поскольку из первого следует, что

k+1 n ⋅2 ≤ 120

Тогда из нашего утверждения следует, что для любого нечётного числа $n$ , меньшего 120, найдётся число от 61 до 120, что его наибольшим нечетным делителем будет $n$ . Причём для каждого $n$ такое число уникально. При этом нечётных чисел от 1 до 120 ровно 60, как и чисел от 61 до 120. Получается, что искомая сумма равна сумме всех нечётных чисел от 1 до 120.

1+-119- 1+3+ ...+ 119= 2 ⋅60= 3600

Ответ: 3600

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

Задача 4#88133

В тюрьме находятся 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 ...al$ равно $σ(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

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

Задача 5#88137

Найдите сумму максимальных нечётных делителей всех чисел от 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< 1200$ , то существует натуральное число $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

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

Задача 6#100676

Докажите, что при любом натуральном $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]

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

Курсы

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

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

Задача 7#67956

Для натурального числа $N$ выписаны все его натуральные делители $p i$ в порядке возрастания $1< p <p ...<p = N. 1 2 k$

Обозначим количество натуральных делителей числа $N$ через $σ(N ).$

Найдите все возможные значения $3 σ(N ),$ если известно, что

2 p3⋅p4⋅p1696⋅p1697 ≥N

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

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

Подсказка 1

Давайте подумаем, что можно сделать с большими по номеру делителями. Например мы знаем, что если p - наибольший делитель, а q - наименьший, то p = N/q. Как развить эту идею?

Подсказка 2

Вот пусть у N ровно n ≥ 1697 делителей. Тогда p₁₆₉₇ = N/pₙ₋₁₆₉₇₊₁, p₁₆₉₆ = N/pₙ₋₁₆₉₆₊₁. Тут уже при перемножении мы получаем N² и это хорошо. Но еще получаем в знаменателе два подряд идущих делителя. При каких n это все еще будет выполняться условие?

Подсказка 3

Если n уже ≥ 1700, то внизу будет стоять ≥ p₄⋅p₅, что больше чем p₃⋅p₄, то есть наше выражение будет уже < N². Остается n < 1700, и несложным перебором можно найти примеры на эти n и найти число делителей у N³)

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

По основной теореме арифметики $N$ представляется единственным образом в виде:

α1 α2 αn N = q1 ⋅q2 ⋅⋅⋅qn ,где qi− простое число

Тогда из правила произведения, поскольку мы каждую степень простого числа $q i$ выбираем $α +1 i$ способами, то $σ(N)= (α + 1)⋅(α + 1)⋅⋅⋅(α + 1). 1 1 n$ Из условия следует, что $σ(N)≥ 1697.$ Разберем несколько случаев:

1.

Пусть $σ(N)= 1697.$ Тогда:

N 1 =p1 < p2 < ⋅⋅⋅< p1696 = p2 < p1697 = N.

Значит, $p3⋅p4⋅p1696⋅p1697 = p3⋅p4N2 ≥ N2. p2$ То есть условие выполняется.
Так как $1697−$ простое число, то из формулы для $σ(N )$ следует, что $N = q1696$ (в противном случае 1697 было бы составным).Таким образом,

σ(N3) =(3⋅1696+ 1)= 5089.

2.

Пусть $σ(N)= 1698.$ Тогда:

N- N- 1 =p1 < p2 < ⋅⋅⋅< p1696 = p3 < p1697 = p2 < p1698 = N.

Значит, $p3⋅p4⋅p1696⋅p1697 = pp42N2 ≥ N2.$ То есть условие выполняется.
Так как $1698 =(1697+ 1)= (1 +1)(848+ 1)= (2+ 1)(565+ 1)$ и
$1698= (5+ 1)(282+ 1)= (1+ 1)(2+1)(282+ 1),$ то:

3 σ(N ) =(3⋅1697+ 1)= 5092;

σ(N3)= (3 ⋅1 +1)(3⋅848+ 1) =10180;

3 σ(N )= (3 ⋅2 +1)(3⋅565+ 1) =11872;

3 σ(N )= (3 ⋅5 +1)(3⋅282+ 1) =13552;

σ(N3 )=(3⋅1+ 1)(3⋅2+ 1)(3⋅282+ 1)= 23716.

3.

Пусть $σ(N)= 1699.$ Тогда:

1 =p1 < p2 < ⋅⋅⋅< p1696 = N-< p1697 = N-< p1698 < p1699 = N. p4 p3

Значит, $p3⋅p4⋅p1696⋅p1697 = N2 ≥ N2.$ То есть условие выполняется.
Так как $1699−$ простое число, то из формулы для $σ(N )$ следует, что $N = q1698$ (в противном случае 1699 было бы составным).Таким образом,

σ(N3) =(3⋅1698+ 1)= 5095.

4.

Пусть $σ(N)≥ 1700.$ Тогда $p1696 < Np,p1697 < Np-. 3 2$ Следовательно, $p3⋅p4⋅p1696 ⋅p1697 <N2.$ Таким образом, этот случай невозможен.

Ответ:

$5089,5092,5095,10180,11872,13552,23716$

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

Задача 8#73176

Существует ли такое натуральное число $n$ , что $6n− 1$ имеет ровно $n$ натуральных делителей?

Источники: 24 Кубок Колмогорова

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

Пусть $n =2kt$ , где $t$ нечетно. Тогда

2kt ( 2k−1t )( 2k−2t ) ( t )(t ) 6 − 1= 6 + 1 6 + 1 ... 6 +1 6− 1 .

Заметим, что все множители в этом разложении взаимно просты, так они нечетны и каждый из них, уменьшенный на 2, равен произведению всех следующих. Следовательно, количество делителей числа $n 6 − 1$ равно произведению количеств делителей у множителей. Всего множителей $k+1$ и все они больше единицы, поэтому если ни один из множителей не является точным квадратом, то количество делителей у каждого множителя четно. Тогда количество делителей числа $n 6 − 1$ делится на $k+1 2$ , а $n$ не делится на $k+1 2$ . Таким образом, один из множителей должен являться точным квадратом. Так как среди натуральных чисел не может быть двух последовательных квадратов, то квадратом является или $6t+1$ , или $6t− 1$ . При этом $6t− 1≡ 2 (mod 3)$ и тоже не является квадратом. Значит, $6t+ 1= m2$ , $6t = (m + 1)(m − 1)$ . Обе скобки не могут одновременно делиться на 3, поэтому одна из них делится на $3t$ , откуда разность между скобками хотя бы $3t− 2t > 2$ при $t> 1$ . Очевидно, $t=1$ тоже не подходит.

Ответ: не существует

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

Задача 9#73691

Обозначим за $σ(n)$ сумму всех делителей числа $n$ (включая само число). Для каких $n$ выполняется неравенство $σ(8n)> σ(9n)?$

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

Запишем $n$ в каноническом виде: $n= ∏m pki. i=1 i$ Тогда $σ(n)= ∏m (1+ p +...+pki). i=1 i i$

Отсюда видно, что при домножении или делении числа $n$ на какой-то множитель, взаимно простой с числами $8$ или $9$ (то есть, не кратный $2$ и $3$ ), правая и левая части неравенства $σ(8n)>σ(9n)$ изменяются в одинаковое количество раз. Значит, нам достаточно найти все решения вида $kl n= 2 3$ — всё остальное можно получить из них домножением на какое-то число $x,$ не делящееся ни на $2,$ ни на $3.$

Тогда

σ(8m )= (1+ 2+ ...+ 2k+3)(1 +3+ ...+ 3l)

k l+2 σ(9n)=(1+ 2+ ...+ 2)(1 +3+ ...+ 3 )

Их частное должно быть больше $1:$

1+2+...+2k+3- ----7---+ 8 σ(8n)= 11++32++......++32l+k2-= 1+2+..4.+2k---> 1 σ(9n) -1+3+...+3l 1+3+...+3l + 9

Знаменатель этой дроби всегда больше $9.$ Числитель же равен $9$ при $k =2$ и и меньше $9$ при больших $k.$ Осталось разобрать два случая: $k =1$ и $k =0.$ При $k= 1$ имеем:

7 -----4----- 3 + 8> 1+ 3+...+3l + 9

31 4 3-> 9+ 1+3-+...+-3l

Правая часть равна $13$ при $l= 0.$ При $l≥ 1$ правая часть не больше $10.$ Значит, $σ(8n)> σ(9n)$ при $k =1$ и $l≥ 1.$ При $k =0$ имеем:

15 >9 +-----4-----l 1 +3+ ...+ 3

Это равенство всегда верно. Таким образом, у нас есть две серии ответов.

Ответ:

$n =3lx$ или $n= 6⋅3lx,$ где $l$ — целое неотрицательное число, а $x$ — натуральное число, не делящееся ни на $2,$ ни на $3$

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

Задача 10#74874

Обозначим через $d(n)$ количество натуральных делителей числа $n.$ Последовательность натуральных чисел $a ,a,...,a 1 2 400$ удовлетворяет условию

an+1 = d(an)+ d(n)

Докажите, что в этой последовательности не более $210$ простых чисел.

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

Отметим, что если $n$ не является квадратом натурального числа, то хотя бы одно из чисел $a ,a n n+1$ не является простым. Докажем это утверждение от противного – тогда $an$ простое. Число $. d(n).. 2,$ так как $n$ не квадрат, а $d(an)=2.$ Следовательно, $a = d(a )+d(n) ... 2 n+1 n$ , при этом $a > 2, n+1$ поэтому $a n+1$ не является простым – противоречие.

Вычеркнем из последовательности $an$ все элементы, индексы которых являются квадратами, а все остальные элементы разобьем на пары. Между любыми двумя квадратами находится четное количество чисел ( $. (a+ 1)2− a2− 1= 2a .. 2$ ), поэтому такой способ ставит в пару подряд идущие числа. По доказанному, в каждой паре находится не более одного простого элемента, значит среди $400− 20 =380$ невычеркнутых элементов есть не более, чем $190$ простых. Вычеркнутые элементы могут быть простыми. Их количество равно $20,$ поэтому общее число простых элементов можно оценить как $190+20= 210,$ что и требовалось доказать.

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

Задача 11#88135

Сумма двух различных натуральных делителей натурального числа $n$ равна 100. Какое наименьшее значение может принимать число $n?$ (Среди указанных делителей могут быть единица и само число.)

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

Подсказка 1

Предположим, что мы взяли какие-то два делителя числа n числа и сложили их. Если каждый из этих двух делителей меньше n, то он меньше n “в сколько-то раз”. Какой вывод мы тогда сможем сделать для их суммы?

Подсказка 2

Да, в таком случае сумма этих двух делителей, равная ста, будет меньше, чем n, следовательно, n больше ста. Это не очень удовлетворительный результат, потому что первый пример, приходящий в голову — 99+1 — это пример меньше, чем на 100. Какой вывод можно отсюда сделать?

Подсказка 3

Тогда получается, что один из делителей заведомо равен самому числу. В таком случае, введя d как меньший делитель, можно записать условие в виде достаточно простого выражения!

Подсказка 4

Из нашей записи получится, что n/d+1 должно быть делителем числа 100. При этом для каждого фиксированного d чем больше n/d, тем больше n. Отсюда и получим искомый ответ!

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

Если один из наших делителей — само число $n$ , а второй — некоторое число $d$ и $n= dk$ , то мы получаем

100= d+ dk =d(k+ 1)

n ( 1) 100= n+ k = n⋅ 1+ k

Чем $k$ больше, тем и само $n$ больше.

Наименьшее $k >1$ такое, что $k+ 1$ является делителем 100, это 3. При таком $k$ получаем $n =75$ .

Если же $n$ нет среди двух наших делителей, то $n n 2 + 3 ≥100$ , откуда $n ≥120$ .

Ответ: 75

Интенсивы

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

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

Задача 12#34016

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

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

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

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

Ответ:

$144$

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

Задача 13#76579

При каком наименьшем $n$ все натуральные делители числа $n$ можно поделить на три группы, суммы в которых равны? Если группа состоит из одного числа, то сумма чисел в этой группе равна этому одному числу.

Источники: Турнир Ломоносова-2022, 11.4

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

Подсказка 1

Вспомните для начала, как считать сумму делителей числа, или выведите. Это несложно. Давайте подумаем в общем о природе групп. Какая может быть минимальная сумма делителей у одной группы?

Подсказка 2

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

Подсказка 3

Да, это число 120, сумма его делителей 360. Поэтому у нас получатся группы (120), (40, 20, 60) и в последней группе остальные числа. Отсюда получается и идея для доказательства оценки. Если число будет меньше 120, то сумма его делителей будет меньше 3n. Как тогда можно оценить самым грубым образом сумму делителей в общем виде?

Подсказка 4

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

Подсказка 5

Да, давайте просто переберём все наши возможности. Это когда n просто степень простого числа, когда n произведение двух степеней простых. Рассмотрев ещё, что будет происходить с 3 делителями или больше, получим, что n содержит ровно 3 простых делителя. А можем ли мы сказать, из каких точно делителей должно состоять n?

Подсказка 6

Верно, маленьким перебором получится, что n представляется в одном из трёх видов 2*3²*p, 2²*3*p, 2*3*p, где p простое число. Теперь только осталось разобрать их, и мы получим оценку на число 120. Победа!

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

Заметим, что $120 =23⋅3⋅5,$ поэтому сумма всех делителей числа $120$ равна $(1+2 +4+ 8)(1+ 3)(1+ 5) =15⋅4⋅6= 360.$ Поэтому нам надо поделить делители в группы с суммой $120.$ Подойдут группы ${120}$ , ${20,40,60}$ и все оставшиеся числа.

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

Вспомним, что сумма делителей числа $α1α2 αs n= p1 p2 ...ps$ равняется

( )( ) ( ) σ(n)= 1+ p1 +p21+ ...+ pα11 1+ p2+p22+ ...+ pα22 ...1+ ps+ p2s +...+ pαss

Следовательно

( 1 1 ) ( 1 1 ) ( 1 ) σ(n)= n 1 +p1 +...+ pα11 ... 1+ ps + ...+ pαss < n 1 +p1 +... ...

( ) ... 1+ 1-+ ... = n⋅--p1-...-ps-- ps p1− 1 ps− 1

В неравенстве мы заменили конечную сумму геометрической прогрессии на бесконечную.

Пусть теперь $n$ — некоторое число. Если у $n= pa,$ то

--p- σ(n)< n⋅p− 1 ≤2n< 3n,

поскольку число $p 1 p−-1 = 1+ p−1$ тем больше, чем меньше $p.$

Аналогично, если $n =pa⋅qb,$ то

p q 2 3 σ(n)< n⋅p−-1q−-1 ≤n2-− 1 ⋅3− 1-= 3n

Итак, если $σ(n)≥3n,$ то в разложение $n$ входит хотя бы 3 простых числа. Поскольку уже $2 ⋅3 ⋅5 ⋅7 =$ $210> 120,$ то нас интересуют лишь $n,$ в разложении которых ровно три простых числа.

Если среди этих простых чисел нет $2:$ если среди них нет и $3,$ то $n ≥$ $5 ⋅7 ⋅11 >120,$ значит $3$ есть; если нет $5,$ то $n ≥3⋅7⋅11> 120,$ значит и $5$ есть; если нет $7,$ то $n≥ 3⋅5⋅11 >120,$ значит и $7$ есть. Тогда $n =3⋅5⋅7= 105$ (добавление ещё одного простого сделает $n$ больше $120$ ), сумма делителей которого равна $(1 +3)(1+ 5)(1+ 7)=192< 315.$ Значит, $n$ обязательно делится на $2.$

Пусть третий простой делитель $p.$ Заметим, что $2⋅3⋅p≥ 30;$ поскольку мы ищем $n< 120,$ то домножить $2⋅3⋅p$ мы можем максимум на $3.$ Итак, получили всего немного вариантов: или $n =2 ⋅32⋅p$ , или $n =22⋅3⋅p$ , или $n =2 ⋅3 ⋅p.$

В первом случае при $p≥ 7$ получаем $n ≥ 126,$ при $p =5$ получаем $n =90,$ а

σ(90) =(1+ 2)(1+3 +9)(1 +5)= 234 <270

Во втором случае,

σ(n)= (1 +2+ 4)(1+ 3)(1+ p)=n ⋅ 7⋅ 4 ⋅ p+1 4 3 p

Если $σ(n)≥ 3n,$ то

p+-1≥ 9 p 7

Отсюда $p< 5,$ что неверно.

Аналогично, в третьем случае

σ(n) =(1+ 2)(1+ 3)(1+p)= n⋅ 3 ⋅ 4⋅ p+-1 2 3 p

Отсюда $p+1 p$ должно быть хотя бы $3 2,$ что неверно при $p≥ 5.$

Ответ: 120

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

Задача 14#80969

Докажите, что $τ(n)≤ 2√n,$ где $τ(n)$ — количество делителей $n.$

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

Заметим, что все делители числа $n$ разбиваются на пары $(d,n). d$ Нетрудно понять, что в каждой паре один из делителей не превосходит $√ - n,$ а второй не меньше $√- n.$ Но тогда пар не больше $√- n,$ а значит количество делителей не превосходит $√- 2 n,$ что и требовалось.

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

Задача 15#80972

Докажите, что ни с какого момента последовательность $τ(n2+ 1)$ не становится строго возрастающей.

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

Предположим, что с некоторого момента последовательность $τ(n2+ 1)$ стала строго возрастающей. Заметим, что у числа $n2+ 1$ чётное число делителей, т.к. они разбиваются на пары вида $n2+1 (d, d ),$ причём нет пары, в которой числа были бы равны, иначе это означало бы, что $n2+1- d = d ,$ то есть $2 2 n + 1= d,$ что очевидно не так. Это означает, что $2 2 τ((n +1) +1)≥ τ(n +1)+ 2.$ Также заметим, что наименьший делитель в паре не превосходит $√-2--- [ n + 1]= n,$ а значит всего их не более чем $2n.$ При чётном $n$ число $2 n + 1$ — нечётно, а значит и его делители также нечетны. То есть наша оценка на количество делителей может быть улучшена до $n$ поскольку среди чисел от $1$ до $n$ половина чётна и они точно не подойдут, а значит всего делителей не больше чем $n 22 =n.$ Тогда если мы возьмем число $N > n$ такое, что $N + n$ чётно, то мы получим, что $2 2 n +N ≥ τ((n+ N) + 1) ≥τ(n +1)+ 2N >2N,$ то есть $n +N ≥ 2N$ — противоречие.

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

Задача 16#80973

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

σ(n)- √ - τ(n) ≥ n

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

Пусть $n$ — не квадрат, тогда все его делители разбиваются на пары $(d;n). d$ Пусть всего таких пар $x,$ тогда $σ(n)≥2x√n,$ поскольку $n √ - d+ d ≥2 n.$ Также $τ(n)=2x,$ но тогда $σ(n) √ - τ(n) ≥ n,$ что и требовалось.

Если же $n$ — квадрат, то пусть все делители $n,$ не считая $√- n,$ образуют $x$ пар, тогда $√- σ(n)≥(2x+ 1) n$ и $τ(n)= 2x+1,$ то есть требуемое также очевидно.

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

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

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

Задача 17#88338

Существуют ли такие натуральные числа $a,b,c,$ что $a$ и $b$ имеют ровно 1000 общих делителей, $a$ и $c$ имеют ровно $720$ общих делителей, а $a,b,c$ имеют ровно $350$ общих делителей?

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

Подсказка 1

Вспомните формулу количества делителей у числа через его разложение на простые множители. Напишите их для a, b и c. Возможно там что-то не так?

Подсказка 2

Вы записали формулы для общих делителей через степени, приравняли их к 1000, 720 и 350. Посмотрите на делители этих чисел. Не возникает ли там противоречие?

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

Запишем разложение чисел $a,b$ и $c$ на простые множители: $a= pα1⋅...⋅pαk,b =pβ1⋅...⋅pβk,c= pγ1⋅...⋅pγk, 1 k 1 k 1 k$ показатели целые неотрицательные.

Количество общих делителей двух чисел равно количеству делителей их наименьшего общего делителя, тогда количество общих делителей $a$ и $b$ равно:

(min{α1;β1} +1)⋅...⋅(min{αk;βk}+1)= 1000

Аналогично выражается количество общих делителей чисел $a$ и $c,$ чисел $a,b$ и $c:$

(min{α1;γ1}+ 1)⋅...⋅(min{αk;γk}+ 1)=720

(min{α1;β1;γ1}+ 1)⋅...⋅(min{αk;βk;γ1} +1)= 350

Заметим, что $350$ кратно $7,$ значит некоторая скобка $(min{αi;βi;γi}+ 1)$ кратна $7.$ Если $min{αi;βi;γi}=αi,$ то скобки $(min{αi;βi}+1)$ и $(min{αi;γi}+ 1)$ также делятся на $7,$ однако $720$ и $1000$ на $7$ не делятся, противоречие. Если $min{αi;βi;γi}= βi,$ то скобка $(min{αi;βi} +1)$ делится на $7,$ что противоречит условию. Аналогично случай $min{αi;βi;γi} =γi$ ведёт к противоречию.

Ответ:

нет

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

Задача 18#88339

Докажите, что количество натуральных делителей числа $n,$ представимых в виде $4k+ 3,$ не превосходит количества делителей, представимых в виде $4k +1.$

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

Подсказка 1

Давайте поймëм, что чётные делители n нас не интересуют, то есть можно считать, что n нечëтное число.

Подсказка 2

Поскольку речь в задаче идёт о числах 4k + 1 и 4k + 3, то стоит рассмотреть отдельно n первого и второго видов. С каким-то из них задача решается довольно просто.

Подсказка 3

Вероятно, вы уже решили задачу для n вида 4k + 3. Для n вида 4k + 1 на самом деле ничего трудного нет. Попробуйте доказать по индукции. Сначала рассмотрите тривиальный случай, когда n - степень числа, и потом аккуратно докажите переход.

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

Если в разложение $n$ входит двойка в некоторой степени, отбросим её, так как мы работаем только с нечётными делителями. Если $n ≡3 (mod 4),$ то каждому делителю $d$ вида $4k+ 3$ поставим в соответствие число $n d,$ нетрудно понять, что оно имеет вид $4k+ 1.$ Тогда в этом случае чисел вида $4k +1$ действительно не меньше, чем чисел $4k +3.$

Теперь пусть $n≡ 1 (mod 4).$ Докажем задачу индукцией по количеству простых чисел, входящих в $n.$

База, когда в $n$ не входят простые числа, т.е. $n= 1,$ очевидна. Пусть теперь $n$ — степень простого числа. Если это простое вида $4k+ 1,$ то всё тривиально. Если же оно вида $4k+ 3,$ то $n$ является квадратом, в противном случае $n$ будет иметь вид $4k+ 3.$ Тогда делители $n$ можно разбить на пары $2 3 (1,p),(p ,p),....$

Переход: если $n$ включает в себя простое число вида $4k+ 1$ в некоторой степени, выкинем его. В оставшемся числе делителей вида $4k+ 3$ не меньше делителей $4k +1.$ Возврат простого числа увеличивает количество и тех, и тех делителей в одинаковое количеств раз, а значит утверждение по-прежнему верно.

Пусть теперь в $n$ входят только простые числа вида $4k+ 3.$ Если хотя бы одно простое число $p$ входит в чётной степени $2t,$ выкинем его и для каждого оставшегося делителя $d$ рассмотрим делители $pd,p2d,...,p2td.$ Среди них равное количество делителей вида $4k+ 1$ и $4k+ 3,$ поэтому условие верно.

Если же все простые входят в нечётной степени, то выкинем из $n$ два простых числа $p2a+1$ и $q2b+1.$ Для оставшегося числа и числа $p2a+1q2b+1$ работает предположение. Пусть у оставшегося числа $x$ делителей вида $4k+ 1$ и $y$ делителей вида $4k+ 3$ ( $x ≥y$ ). У числа $p2a+1q2b+1$ — $x1$ и $y1.$ Тогда при перемножении появилось $xx1+ yy1$ делителей вида $4k+ 1$ и $xy1+ x1y$ делителей $4k+ 3.$ По транснеравенству очевидно, что $xx1 +yy1 ≥ xy1 +x1y,$ значит в этом случае переход также доказан.

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

Задача 19#88340

(a) Докажите, что у чисел вида $4 n + 1$ бесконечно много простых делителей.

(b) Докажите, что найдется бесконечно много натуральных $n,$ для которых наибольший простой делитель числа $n4+1$ больше $2n.$

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

(a) Предположим противное, пусть $4 n +1$ делится на конечное число простых чисел $p1,p2,...,pk.$ Заметим, что при $n= p1p2...pk$ число $4 n + 1$ не делится ни на одно из этих простых чисел и оно явно больше $1,$ значит оно либо делится на простое число, которого нет в наборе, либо является им, пришли к противоречию.

(b) Пусть у числа $n40 +1$ наибольший простой делитель равен $p.$ Можно считать, что $n0$ меньше $p.$ Если оказалось, что $p2 < n0,$ то вместо $n$ подставим $p− n0.$ Причём $(p− n0)4 +1$ по-прежнему делится на $p$ и при этом $p >2(p− n0).$ Тогда наибольший простой делитель числа $(p− n0)4+ 1$ точно подходит к условию. Таким образом для каждого $n,$ при котором условие не выполняется, можно подобрать $n,$ для которого оно справедливо.

Теперь предположим, что существует лишь конечное количество значений $n,$ для которых условие верно: $n1 <n2 <...<nk.$ Продолжим подставлять $n =nk +1,nk+ 2,...$ до тех пор, пока не получим выражение $n4+ 1$ с наибольшим простым делителем $q,$ на который не делится ни одно выражение $n4i + 1.$ Рано или поздно мы его получим, это следует из предыдущего пункта. Тогда либо полученное $n,$ либо $q− n$ на самом деле удовлетворяет условию, пришли к противоречию, а значит получили требуемое.

Ответ:

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

Задача 20#97948

Сумма трёх различных натуральных делителей нечётного натурального числа $n$ равна $10327.$ Какое наименьшее значение может принимать $n?$

Источники: ВСОШ - 2022, школьный этап, 10 класс

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

Наибольший делитель $n$ равен $n.$ Так как $n$ нечетно, то средний по величине не превосходит $n, 3$ а, поскольку делители различны, третий по величине не превосходит $n 5.$ Тогда имеем