Задача 60545

Тема:    [ Количество и сумма делителей числа ]

Сложность: 3+ Классы: 9,10

Условие

Пусть  (m, n) > 1.  Что больше  τ(mn)  или  τ(m)τ(n)?  Исследуйте тот же вопрос для функции σ(n).

Решение

Из мультипликативности функций τ(n) и σ(n) следует, что для обснования ответа достаточно проверить неравенства для случая, когда числа m и n – степени одного и того же простого числа. Пусть  m = p^α,  n = p^β.  Тогда (см. задачу 60537)  τ(m)τ(n) = (α + 1)(β + 1) > α + β + 1 = τ(mn);
σ(m)σ(n) > σ(mn)  ⇔  (p^α+1 – 1)(p^β+1 – 1) > (p^α+β+1 – 1)(p – 1)  ⇔  p^α+β+1 + p > p^α+1 + p^β+1  ⇔  p(p^α – 1)(p^β – 1) > 0,  а последнее неравенство очевидно.

Ответ

τ(mn) < τ(m)τ(n);  σ(mn) < σ(m)σ(n).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	3
Название	Мультипликативные функции
Тема	Неопределено
задача
Номер	03.093