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

Делимость и делители (множители) → .03 Количество, сумма, произведение делителей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определите количество кратных трём натуральных делителей числа $11!=1 ⋅2 ⋅...⋅11$ .

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

Для начала разберемся, какие простые множители входят в число $11!$ и в каких степенях.

8 4 2 1 1 11!=1 ⋅2 ⋅3 ⋅4 ⋅...⋅11 =2 ⋅3 ⋅5 ⋅7⋅11

Теперь рассмотрим вид числа, которое является делителем $11!$ и которое само делится на $3.$ Пусть $11!$ делится на $d,$ тогда

d= 2α1 ⋅3α2 ⋅5α3 ⋅7α4 ⋅11α5,

где все $αi$ принимают значения от $0$ до соответствующей степени в числе $11!,$ кроме $α2,$ которое принимает значения от $1$ до $4$ .

Следовательно, исходная задача свелась к подсчету различных чисел $d,$ определенного вида. Посчитаем количество таких различных $d :$

9⋅4⋅3⋅2⋅2= 432

Ответ: 432

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

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

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

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

Найдите все натуральные числа $n$ от 400 до 600 такие, что если перемножить все делители числа $n$ (включая 1 и $n$ ), получим число $5 n$ .

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

Утверждается, что $n$ удовлетворяет условию задачи, если и только если его разложение $n= pk1...pks 1 s$ на простые множители имеет вид либо $9 n =p$ , либо $4 n= p1p2$ .

Действительно, для каждого $j =1,...,k1$ имеется $(k2+ 1)...(ks+ 1)$ делителей числа $n$ , содержащих $p1$ в степени $j$ в разложении на простые множители: все эти делители имеют вид $j m1 ms p1p2 ...ps , mi ∈ {0,...,ki}$ . Следовательно, произведение всех делителей числа $n$ содержит $p1$ в степени $1 (k2+ 1)...(ks +1)(1+...+k1)= 2(k1+1)...(ks+1)k1$ . Условие, что произведение всех делителей равно $5 n$ , эквивалентно утверждению, что каждое $pj$ входит в их произведение в степени $5kj$ , и, тем самым, предыдущее выражение равно $5k1$ . Другими словами,

1 2 (k1+ 1)...(ks+ 1)= 5.

С другой стороны, $kj ≥ 1$ . Отсюда следует, что $s≤ 2$ . Пусть $s= 2$ . Тогда одно из $kj$ , скажем, $k1$ равно 1 , а тогда $k2 = 4$ (простота числа 5). В случае, когда $s= 1,k1 = k$ , получаем уравнение $12(k+ 1)= 5$ , то есть $k =9$ . Итак, все числа $n ⁄= 1$ , удовлетворяющие условию задачи, имеют разложение на простые множители вида либо $n= p1p42,p1 ⁄= p2$ , либо $n = p9;p1,p2,p>1$ . Перечислим те из них, которые лежат между 400 и 600.

Числа $n= p1p42$ . Имеем $p42 ≤600∕2= 300$ , тем самым, $p2 ≤ 4,p2 ∈ {2,3}$ . Итак, $16 ≤p42 ≤ 81$ . Следовательно, $4 =[400∕81]< p1 ≤ [600∕16]= 37$ , а, значит,

p1 ∈ {5,7,11,13,17,19,23,29,31,37},p2 ∈{2,3}.

Выписывая всевозможные произведения $n =p1p42$ , лежащие в промежутке от 400 до 600 , с вышеуказанными $p1$ и $p2$ , получаем $5⋅34 = 405,7⋅34 = 567,29⋅24 = 464,31⋅24 =496,37⋅24 = 592$ .

Единственное $n =p9$ , лежащее между 400 и 600 , есть $512=29$ . Итого получаем список всех возможных чисел $n$ :

n =405,464,496,512,567,592.

Ответ: 405,464,496,512,567,592

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

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

Для каких натуральных $n$ все делители числа $n$ могут быть написаны в клетки некоторой прямоугольной таблицы так, что каждый делитель написан ровно в одной клетке, в каждой клетке написан какой-то делитель, сумма чисел в каждой строке одинаковая, а также сумма чисел в каждом столбце одинаковая?

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

Предположим, что делители $n$ можно расположить в прямоугольную таблицу $k× l,k ≤l.$ Пусть сумма чисел в каждом столбце равна $s.$ Поскольку $n$ находится в одном из столбцов, $s≥n,$ равенство достигается при $n= 1.$

Для всех $j = 1,2,...,l$ определим $dj$ как максимальное число в $j$ -м столбце. Не умаляя общности, положим $d1 >d2 > ...> dl.$ Эти числа — делители $n,$ значит $n dl ≤ l.$ Поскольку $dl$ — максимальное число в $l$ -м столбце, имеем $s n dl ≥ k ≥ k.$

Таким образом, $n n l ≥ k,$ откуда $k ≥l.$ Учитывая, что $k ≤l,$ получаем $k =l.$ Значит, все ранее полученные неравенства становятся равенствами. В частности, $s=n$ и $n = 1,$ в этом случае все условия соблюдены.

Ответ:

$n =1$

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

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

Митя сложил все нечётные натуральные делители некоторого чётного числа $N$ (включая единицу), а Ваня сложил все чётные натуральные делители числа $N$ (включая само число). Затем Ванину сумму умножили на Митину. Может ли произведение быть квадратом натурального числа?

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

Первое решение.

По условию число имеет вид $k 2 ⋅m,$ где $m$ — нечётное. Заметим, что любому нечётному делителю $d$ числа $N$ взаимнооднозначно соответствует группа чётных делителей

2 k 2d,2 d,...,2 d

Тогда если обозначить Митину сумму через $S,$ то Ванина сумма примет вид

2 k k (2+ 2 +...+2 )S = 2(2 − 1)S

Если перемножить суммы, то мы получим

2(2k− 1)S2

Теперь видно, что вопрос задачи сводится к тому, может ли быть квадратом число вида $2(2k − 1).$ Очевидно, что нет, потому что оно делится на $2,$ но не делится на $4.$

Второе решение.

Разложим число из условия по основной теореме арифметике

N = 2k⋅pk1⋅...pkr 1 r

Из такого представления известно, что сумма всех делителей числа $K =pk11⋅...pkrr$ равна

(1 +p1+ ...+ pk11)...(1+pr+ ...+ pkrr )= S

При этом это является суммой всех нечётных делителей $N.$ Для получения суммы только чётных делителей формула принимает вид

S⋅(2+22+ ...+ 2k)

В итоге произведение сумм равно $S2⋅(2+ 22 +...+ 2k)= 2S2 ⋅(2k− 1),$ однако легко видеть, что в левую часть двойка входит в нечётной степени, потому сумма не может быть точным квадратом.

Ответ: нет

Критерии оценки

За выражение произведения в виде S² * (2 + 2² + … + 2^k) – не менее 2 баллов.

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

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

Назовём натуральное число почтенным, если сумма всех его делителей, включая $1,$ но не включая само число, на $1$ меньше этого числа. Найдите все почтенные числа, некоторая точная степень которых тоже почтенно.

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

Подсказка 1

Чтобы что-то понять про точную степень почтенного числа, важно понять что-нибудь про его делители.

Подсказка 2

Ага, сумма делителей степени почтенного числа равна n^k-1, как ещё это можно представить?

Подсказка 3

n^k-1 = (d₁+d₂+...+d_m)(n^(k-1)+...+1). Разбейте данное произведение на сумму делителей и поймите что-нибудь про n.

Подсказка 4

n — степень простого числа, докажите это.

Подсказка 5

Так как все делители почтенного числа известны — логично проверить его на почтенность.

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

Пусть $n$ — почтенное число. Тогда сумма $d +d + ...+ d 1 2 k$ его делителей, отличных от $n,$ равна $n− 1.$ У числа $nk$ заведомо есть делители

k−1 k−1 d1, d1n,..., d1n , d2, d2n,..., dk, dkn,..., dkn .

Все они различны и отличны от $nk,$ а их сумма равна

2 k−1 (1+ n+ n + ...+n )(d1+ d2+ ...+dk)=

= (1+n +n2 +...+ nk−1)(n− 1)= nk− 1.

Следовательно, у числа $nk$ нет делителей(так как оно тоже должно быть почтенным), отличных от вышеперечисленных. Это означает, что $n$ является степенью простого числа. В противном случае, если $n$ делится на $pt$ (и не делится на $pt+1$ ), то в приведённом выше списке делителей числа $nk$ отсутствует делитель $pt+1.$
Итак, пусть $n= pm.$ Тогда сумма отличных от $n$ делителей числа $n$ равна $1+p +p2+ ...+ pm −1,$ что по условию равно $pm − 1.$ Но

1+ p+ p2 +...+ pm−1 = pm-−1− 1, p− 1

что меньше $pm −1− 1$ при $p⁄= 2$ и равно $pm−1− 1$ при $p =2.$ Таким образом, числа $n =2m$ удовлетворяют условию задачи, а остальные числа не удовлетворяют условию.

Ответ:

все степени двойки, включая нулевую

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

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

Найдите все натуральные $n,$ у которых ровно $16$ делителей

1 =d1 < d2 < ...< d16 = n

причем $d6 =18,$ а $d9− d8 = 17.$

Источники: Irish-1998, Andreescu p.127

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

Посмотрим внимательно на $d = 18. 6$ Если $n$ делится на $d , 6$ то у $n$ есть те же делители, что и у $18,$ то есть у $n$ есть делители $2,3,6,9.$ По условию $d1 = 1,d6 = 18,$ следовательно, делители $d2,d3,...,d5$ это в точности делители $18.$

Тогда число $n$ может быть представимо в следующих видах: (a) $1+α 2+β n= 2 ⋅3 .$ В этом cлучае общее количество делителей это

(1+ 1+α)(3+β)= 16

То есть или $α= 2,β = 1$ или $α = 0,β =5.$ Но первый случай невозможен, так как появился бы делитель $4.$ Рассмотрим второй случай. Если $n = 2⋅37,$ то $d =52,d =81, 8 9$ что противоречит условию $d − d = 19. 9 8$

(b) $1+α 2+β k n= 2 ⋅3 ⋅p ,$ где $p$ — какой-то простой делитель, больше $18.$ В этом cлучае общее количество делителей это

(1+ 1+ α)(3+ β)(1+ k)= 16

То есть $α= 0,β = 1,k= 1$ и только такой случай, так как $3+β ≥3.$ Переберем случаи, где может быть $p.$

Если $p$ больше $d = 18, 6$ но меньше $d = 27, 8$ то $d =p 7$ и $d = 2p, 9$ откуда $d − d = 2p− 27= 17, 9 8$ откуда $p=22,$ что невозможно.

Если $p$ больше $d7 = 27,$ но меньше $d9 = 54,$ то $d9− d8 = 54− p =17,$ откуда $p= 37.$

Если $p$ больше $d8 = 54,$ то $d9 =p.$ Тогда $d9− d8 = p− 54 =17,$ откуда $p= 71.$

Получаем $2$ ответа: $3 n= 2⋅3 ⋅37$ или $3 n= 2⋅3 ⋅71.$

Ответ:

$2⋅33⋅37,2 ⋅33⋅71$

Курсы

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

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

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

Найдите все натуральные числа, имеющие ровно шесть делителей, сумма которых равна $3500.$

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

Запишем каноническое разложение натурального числа $n = pα1 ⋅pα2⋅...⋅pαk. 1 2 k$ Его количество делителей равно $(α + 1)(α + 1)...(α +1). 1 2 k$ Если это число равно $6,$ то либо $k= 1$ и $α1 = 5,$ либо $k= 2,α1 = 2,α2 = 1.$ То есть либо $5 n= p,$ либо $2 n = pq$ ( $p$ и $q$ — простые).

В первом случае $2 3 4 5 1 +p+ p + p +p + p = 3500,$ откуда $2 3 4 p(p+ p +p + p )=3499.$ Число $3499$ не делится на $2,3,5$ и $7,$ поэтому $p> 10,$ но в этом случае $2 3 4 p(p+ p +p + p )>3499.$ Поэтому это уравнение решений в простых числах не имеет.

Во втором случае $2 2 1+ p+ p +q +pq+ pq =3500,$ то есть $2 3 (1+ p+ p)(1+q)= 5 ⋅7⋅4.$ Первый множитель нечётен и не кратен $5$ (чтобы убедиться в этом, достаточно это утверждение проверить для соответствующих остатков). Отсюда, учитывая, что $2 1 +p+ p > 1,$ имеем $2 1+ p+p = 7.$ Значит, $p= 2,$ $q = 499.$ Числа $2$ и $499$ — простые. Искомое число $n =22⋅499= 1996.$

Ответ:

$1996$

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

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

Докажите, что количество делителей натурального числа $n$ не превосходит $2√n.$

Источники: ММО - 1960, задача 7.5

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

Если $d$ — делитель числа $n,$ то $n d$ — тоже делитель числа $n.$ Хотя бы одно из этих двух чисел не превосходит $√n.$ Поэтому число делителей не превосходит $√- 2 n.$

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

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

Докажите, что количество натуральных делителей числа

α1 α2 αk n =p1 ⋅p2 ⋅...⋅pk

(где $p i$ — различные простые числа) равно

(α1+ 1)(α2+1)...(αk+ 1).

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

Это так, ведь для делителя мы каждую степень простого числа $p i$ выбираем $α + 1 i$ способами. По правилу произведения получается приведённая в условии формула.

Предыдущая подтема

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