Число и сумма натуральных делителей натурального числа

[Robot]

Число и сумма натуральных делителей натурального числа
Основная теорема арифметики. Всякое натуральное число п > 1 либо просто, либо может быть представлено, и притом единственным образом - с точностью до порядка следования сомножителей, в виде произведения простых чисел (можно считать, что любое натуральное число, большее 1, можно представить в виде произведения простых чисел, если считать , что это произведение может содержать всего лишь один множитель).
Среди простых сомножителей, присутствующих в разложении `n = p1*p2*...*pk`, могут быть и одинаковые. Например, `24=2*2*2*3`. Их можно объединить, воспользовавшись операцией возведения в степень. Кроме того, простые сомножители можно упорядочить по величине. В результате получается разложение
`n = p_1^(alpha_1)*p_2^(alpha_2)*.......*p_k^(alpha_k)`, где `alpha_1, alpha_2, ......, alpha_k in NN`
(1)
Такое представление числа называется каноническим разложением его на простые сомножители. Например, каноническое представление числа 2 520 имеет вид 2 520 = 2³ • З² • 5 • 7.
Из канонического разложения числа легко можно вывести следующую лемму: Если n имеет вид (1), то , то все делители этого числа имеют вид:
`d = p_1^(beta_1)*p_2^(beta_2)*......*p_k^(beta^k)`, где `0 <= beta_m <= alpha_m` ( `m = 1,2,..., k`)
(2)
В самом деле, очевидно, что всякое d вида (2) делит а. Обратно, пусть d делит а, тогда a=cd, где с — некоторое натуральное число и, следовательно, все простые делители числа d входят в каноническое разложение числа а с показателями, не превышающими соответствующих показателей числа а.
Рассмотрим две функции, заданные на множестве натуральных чисел:
а) τ(n) - число всех натуральных делителей n;
2) σ(n) сумма всех натуральных делителей числа n.
Пусть n имеет каноническое разложение (1). Выведем формулы для числа и суммы его его натуральных делителей.
Теорема 1. Число натуральных делителей числа n
`tau(n) = (alpha_1 + 1)*(alpha_2 + 1)*.....*(alpha_k + 1);`
(3)
Доказательство.
По лемме любой делитель имеет вид (2). При этом показатель β₁ может принимать значения 0,1,2,...α₁, то есть всего α₁+1 значение (это соответствует делителям вида 1, р₁, р₁²,...р₁^α₁)
Аналогично, показатель β₂ может принимать значения 0,1,2,...α₂, то есть всего α₂+1 значение (это соответствует делителям вида 1, р₂, р₂²,...р₂^α₂) и т.д. Показатель β_k может принимать значения 0,1,2,...α_k, то есть всего α_k+1 значение (это соответствует делителям вида 1, р_k, р_k²,...р_k^α_k).
Так как каждое из α₁+1 значений, которые может принимать число β₁, может сочетаться с любым из α₂+1
возможных значений числа β₂ и т. д., то мы видим, что общее число натуральных делителей числа n равно `tau(n) = (alpha_1 + 1)*(alpha_2 + 1)*.....*(alpha_k + 1);`

Пример. Число 2 520 = 2³ • З² • 5 • 7. имеет (3+1)(2+1)(1+1)(1+1) = 48 делителей.
Теорема 2. Пусть n имеет каноническое разложение (1). Тогда сумма натуральных делителей числа n равна
`sigma(n) = (1 + p_1 + p_1^2 + ..... + p_1^(alpha_1))*(1 + p_2 + p_2^2 + ..... + p_2^(alpha_2))* ..............* (1 + p_k + p_k^2 + .....+ p_k^(alpha_k));`
(4)
Доказательство.
Рассмотрим произведение
`(1 + p_1 + p_1^2 + ..... + p_1^(alpha_1))*(1 + p_2 + p_2^2 + ..... + p_2^(alpha_2))* ..............* (1 + p_k + p_k^2 + .....+ p_k^(alpha_k));`
(4')
Если раскрыть скобки, то получим сумму членов вида
`p_1^(beta_1)*p_2^(beta_2)*....*p_k^(beta_k)`, где `0 <= beta_m <= alpha_m` ( `m = 1,2,...., k`)

Но такие члены являются делителями n, причем каждый делитель входит в сумму только один раз. Поэтому произведение (4') равно сумме всех делителей n, т. е. равно σ(n) . Итак, σ(n) можно вычислить по формуле (4). С другой стороны, каждая сумма 1+р_m+ р_m²+...+ р_m^α_m является суммой геометрической прогрессии с первым членом 1 и знаменателем р_m.Поэтому иначе формулу (4) можно переписать так:
(5)
Пример. Найти сумму всех делителей числа 90.
90=2 • З² • 5. Тогда σ(90)=[(2²-1)/(2-1)]• [З³-1)/(3-1)]• [(5²-1)/(5-1)]=234
Формула (4) может помочь найти все делители числа.Так, например, чтобы найти все делители числа 90, раскроем скобки в следующем произведении (не производя операцию сложения): (1+2)(1+3+З²)(1+5)=(1+1*3+1*З²+1*2+2*3+2*З²)(1+5) = 1+3+З²+2+2*3+2*З²+ 5+3*5+З²*5+2*5+2*3*5+2*З²*5 = 1+3+9+2+6+18+5+15+45+10+30+90 - слагаемыми являются делители числа 90.
Решим несколько задач на тему "Число и сумма натуральных делителей натурального числа"
Задание 1. Найдите натуральное число, зная, что оно имеет только два простых делителя, что число всех делителей равно 6, а сумма всех делителей — 28.

Решение

Решение. Так как искомое число n имеет только два простых делителя, то оно представимо в виде n= р₁^α₁•р₂^α₂ (где будем считать, что р₁ < р₂).
Так как число всех делителей этого числа равно 6, то по формуле (3) (α₁+1)•(α₂+1)=6. Учитывая, что каждый из сомножителей в левой части не меньше 2 (α₁,α₂≥1), а 6 представляется в виде произведения таких сомножителей единственным образом 6=2•3 с точностью до порядка следования множителей, то имеем два случая
1)
Так как сумма всех делителей равна 28, то (1+р₁)(1+ р₂+ р₂²)=28. 28 раскладывается в произведение двух множителей следующими способами: 28=1*28=2*14=4*7 (с точностью до порядка следования множителей)
Заметим, что 1 < р₁ < р₂, поэтому р₂ > 2, а значит, 1+р₁ >2, а 1+ р₂+ р₂² >7. Отсюда ни одно из разложений разложений числа 28 в произведение двух множителей нас не устраивает
2)
В данном случае (1+ р₁+ р₁²)(1+р₂)=28, при этом 1+ р₁+ р₁² > 3, 1+р₂ >3. Откуда 1+ р₁+ р₁²=4, 1+р₂=7 (эта система в натуральных числах решений не имеет) или 1+ р₁+ р₁²=7, 1+р₂=4, откуда р₁=2, р₂=3
Отсюда n=2² •3=12
Задания из сборника TTZ - ЕГЭ 2010. Математика. Типовые тестовые задания
Задание 2. TTZ.С6.2 Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 различных натуральных делителя (включая единицу и само число).

Решение

Решение. Так как 42=2•3•7 , а искомые числа делятся на 42, то в число их простых делителей входят числа 2, 3 и 7, а значит вид этих чисел n= 2^α₁• 3^α₂•7^α₃•Q (Q- остальная часть канонического разложения числа n). Чтобы использовать формулу числа делителей (3) число 42 надо разложить в произведение не менее 3 множителей, больших 1. Однако с точностью до порядка следования этих множителей это можно сделать единственным способом: 42=2•3•7 Это означает, что Q=1 и n= 2^α₁• 3^α₂•7^α₃, а значит, (α₁+1)•(α₂+1)(α₃+1)=2•3•7
Отсюда имеем следующие случаи:

запись можно было сделать короче, если заметить, что речь идет о перестановке в показателях трех чисел 1,2 и 6
Задание 3. TTZ.С6.9 Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных натуральных делителей(включая единицу и само число).

Решение

Решение. Так как последняя десятичная цифра числа равна 0 (то есть число делится на 10), то оно делится на 2 и на 5, то есть в число его простых делителей входит 2 и 5. А значит, n имеет вид n = 2^α₁• 5^α₂•Q (Q- остальная часть канонического разложения числа n). Чтобы использовать формулу (3) числа делителей число 15 надо разложить в произведение не менее 2 множителей, больших 1. Однако с точностью до порядка следования этих множителей это можно сделать единственным способом: 15=3•5. Поэтому Q=1 и n= 2^α₁• 5^α₂. (α₁+1)•(α₂+1)=3•5, откуда возможны всего два случая
1) α₁+1=3, α₂+1=5, откуда α₁=2, α₂=4 и n=2²• 5⁴=2500
2)α₁+1=5, α₂+1=3, откуда α₁=4, α₂=2 и n=2⁴• 5²=400
Задание 4. SPI.С6.9. У натурального числа n ровно 6 делителей. Сумма этих делителей равна 3500. Найти n.
Решение  VEk:

Решение

Задания для самостоятельной работы
SR1. Найти все числа, имеющие ровно 2 простых делителя, всего 8 делителей, сумма которых равна 60.
SR2. Найти натуральные числа, которые делятся на 3 и на 4 и имеют ровно 21 натуральный делитель.
SR3. Найти наименьшее натуральное число, имеющее ровно 18 натуральных делителей.
SR4. Найти наименьшее число, кратное 5, имеющее 18 натуральных делителей.
SR5. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 15 делителей. Сколько делителей имеет куб этого числа?
SR6. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 81 делитель. Сколько делителей имеет куб этого числа?
SR7. Найти число вида m = 2^x3^y5^z, зная, что половина его имеет на 30 делителей меньше, треть —на 35 и пятая часть — на 42 делителя меньше, чем само число.

Топик поднят, поскольку по теме топика постоянно появляются вопросы.

запись создана: 11.11.2009 в 06:50

@темы: ЕГЭ, Теория чисел

Comments

[VEk]

Robot Спасибо! Замечательный материал!

[zholga]

Robot, молодец! Спасибо большое!

[Гость]

Поправьте (5)

[La Balance]

Спасибо, особенно за дополнительные задачи =)

[Robot]

Гость Поправила
Спасибо за внимательность

[noil]

Спасибо и отдельное спасибо за задачи!

[Гость]

Огромное спасибо! Очень нужная информация!

[Гость]

Спасибо! Очень нужная инфа и всё понятно! Молодец!

[Гость]

спасибо большое!

[lisa55]

Спасибо большое, замечательный материал!
Вы не могли бы дать ответы на задания для самостоятельной работы?..Свериться хотелось бы)

[Robot]

Вот эти задачи из Кудреватова (он у нас в Литература по теории чисел)
SR5. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 15 делителей. Сколько делителей имеет куб этого числа? (ответ: 28)
SR6. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 81 делитель. Сколько делителей имеет куб этого числа? (ответ: 160 или 169)
SR7. Найти число вида m = 2^x*3^y*5^z, зная, что половина его имеет на 30 делителей меньше, треть —на 35 и пятая часть — на 42 делителя меньше, чем само число.(ответ: х=6,у=5, z=4)
==
А первые я решала в момент опубликования поста. Сейчас уже ответы потеряны, как будут свободные полчаса, я решу снова и выложу.

[VEk]

Не гарантирую, но получилось так:
sr1 - 24
sr2 - 576, 2916
sr3 - 180
sr4 - 180

[radiys]

благодарю)отличный материаЛ)

[Lavrusha]

Спасибо)))

[Гость]

а в задании4 :почему К принадлежит к множеству чисел 1,7,10,25...?
сорри туплю

[VEk]

Просто в задании 4 за k обозначено `(S(n))/(p_1+1)`. Так как множество возможных значений `p_1` определено, то и множество значений k также определяется.

[Гость]

Помогите разобраться с 3

[Robot]

Что именно непонятно?

[Гость]

само условие,непонятно по какой формуле рассчитывать

[Robot]

Там написано - формула три.
Вы об этой задаче (?)
Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных натуральных делителей(включая единицу и само число).

[Гость]

Здравствуйте я про задачи для самостоятельного решения sr 3 и sr4
Только они не получились

[VEk]

Гость При решении этих задач используется теорема 1. Выложите свои попытки решения. Подправим.

[Robot]

VEk
Ну, я уж е набрала, так что отправлю идеи
==
SR3. Найти наименьшее натуральное число, имеющее ровно 18 натуральных делителей.
Пусть n, число, имеющее 18 натуральных делителей
Действительно, используется т. 1, формула(3). Так как там множители больше 1, то представим 18 в виде произведения чисел, больших 1.
Это можно сделать 4 способами ( с точностью до порядка следования множителей): 1)18=9*2, 2)18=6*3 и 3)18=3*3*2, 4) 18=18
В первых двух случаях каноническое разложение числа n включает два простых делителя n= p^α₁• q^α₂, в третьем случае - три простых делителя n=p^α₁• q^α₂•t^α₃, в последнем - один простой делитель n=p^α₁
Так как нас интересует наименьшее натуральное число, то простые p, q,t нужно брать наименьшими и при этом меньший из простых делителей должен возводиться в бОльшую степень
Поэтому возможны следующие случаи
1) n= 2^α₁• 3^α₂
при этом α₁+1=9, α₂+1=2
2)n= 2^α₁• 3^α₂
при этом α₁+1=6, α₂+1=3
3) n=2^α₁• 3^α₂•5^α₃
при этом α₁+1=3, α₂+1=3, α₃+1=2
4) n=2^α₁
при этом α₁+1=18
Потом из получившихся чисел выбираем наименьшее
==
Четвертая задача отличается от данной тем, что там число делится на 5 и в его разложение ОБЯЗАНО входить 5
UPD
Спасибо  VEk на указание пропущенного случая.

[VEk]

Robot Может быть в sr4, как раз число 5 не должно входить в разложение. Тогда ответ 288. А так в обеих задачах получается одинаковый ответ

[Robot]

Может быть, я не помню, откуда задачи брала.
Можно, конечно, решить и в формулировке SR4. Найти наименьшее число, не кратное 5, имеющее 18 натуральных делителей.

[Гость]

Спасибо)

[Essen]

спасибо огромное!!!
разобралась с формулами и примерами.. только в последней не могу понять откуда взялся второй вариант, как определили, что число раскладывается в пятую степень?

[VEk]

Essen У числа 6 делителей, 6 = 1*6=2*3. Поэтому либо число имеет 2 простых делителя - один в 1-й, второй - во 2-й степени, либо один простой делитель, но в пятой степени ( см. формулу (3).

[Essen]

VEk
спасибо) вечер был.. я немного тормозила) теперь всё понятно!

[Гость]

А мне очень стыдно, но формулы вроде поняла, а ни одной задачи решить не могу((( Я тупая(((