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

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

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

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

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

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

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

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

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

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

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

Так как $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)

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

Для каждого нечетного числа $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. Тюремщик Джон Фридом, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру. На третьем этапе он повернул ключ в замке каждой третьей камеры (открыл запертые и запер открытые). Продолжая действовать таким образом, на сотом этапе он повернул ключ только в замке последней сотой камеры, а затем выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели счастливчики.

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

Назовем проходом с номером $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

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

Пусть $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)

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

По основной теореме арифметики $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.$

Тогда

σ(8n)=(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?$ (Среди указанных делителей могут быть единица и само число.)

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

Если один из наших делителей — само число $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#104821

Вася написал трёхзначное число $M$ и сообщил Вам, что среди чисел от $1$ до $M$ ровно пять процентов являются делителями $M$ . Чему может быть равно $M$ ? Найдите все варианты, и покажите, что других нет.

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

Напомним, что количество делителей числа $n= pα1pα2...pαk 1 2 k$ (здесь написано каноническое разложение $n$ на простые сомножители) равно $(α1+ 1)(α2+ 1)...(αk +1)$ .

Заметим, что $M$ кратно 20. Если в разложении числа $M$ есть простой множитель $p$ , не меньший 11, то число делителей $M$ делится на $p$ , а значит, $M$ содержит в разложении хотя бы десятую степень простого числа — т.е. $M$ уже хотя бы четырёхзначное. Аналогично, если $M$ делится на 7, то $M$ содержит в разложении хотя бы шестую степень простого числа $q$ . Если $q ≥3$ , то $M$ не является трёхзначным, если же $q =2$ , то $M$ должно делиться на $6 2 ⋅5 ⋅7$ , т.е. тоже больше 1000.

Итак, искомое число равно $a bc 2 3 5$ , причём

2a−23b5c− 1 = (a+ 1)(b+ 1)(c+1)

Если $c≥2$ , то одно из чисел $a +1,b+1,c+ 1$ делится на 5. Из ранее озвученных соображений $a= 4$ (остальные варианты приводят к не менее чем четырёхзначному числу). Итак, $M$ делится на $4 2 25 = 400$ . Легко видеть, что числа 400 и 800 не подходят.

Тогда $c =1$ , и $a−2 b 2 3 = 2(a+ 1)(b+ 1)$ , или $a−3 b 2 3 = (a +1)(b+ 1)$ . Число $a−3 b 2 3$ в 40 раз меньше $M$ , т.е. оно не меньше 3 и не больше 25. Таких чисел не очень много: $3,4,6,8,9,12,16,24$ . Перебрав эти варианты, получим, что подходит только 12 , т.е. $M = 480$ .

Ответ: 480

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

Задача 13#34016

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

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

Представим число $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$

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

Задача 14#76579

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

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

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

Заметим, что $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

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

Задача 15#80969

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

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

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

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

Задача 16#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$ — противоречие.

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

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

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

Задача 17#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,$ то есть требуемое также очевидно.

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

Задача 18#88338

Существуют ли такие натуральные числа $a,b,c,$ что $a$ и $b$ имеют ровно 1000 общих делителей, $a$ и $c$ имеют ровно $720$ общих делителей, а $a,b,c$ имеют ровно $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$ ведёт к противоречию.

Ответ:

нет

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

Задача 19#88339

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

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

Если в разложение $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,$ значит в этом случае переход также доказан.

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

Задача 20#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$ на самом деле удовлетворяет условию, пришли к противоречию, а значит получили требуемое.

Ответ: