#10 Арифметические функции

\(540=2^2\cdot 3^3\cdot 5\). Поэтому \(\tau(540)=3\cdot 4\cdot 2=24\). Далее \(\sigma(540)=(1+2+4)(1+3+9+27)(1+5)=7\cdot 40\cdot 6=1680\). И \(\varphi(540)=540\cdot\frac12\cdot\frac23\cdot\frac45=144\).

Так как \(\tau(n)=(a+1)(b+1)\), получаем пары \((a+1,b+1)=(1,18),(2,9),(3,6),(6,3),(9,2),(18,1)\). Так как в записи \(2^a3^b\) допускаются \(a,b\ge 0\), все пары дают решения: \(3^{17}\), \(2\cdot 3^8\), \(2^2\cdot 3^5\), \(2^5\cdot 3^2\), \(2^8\cdot 3\), \(2^{17}\).

При взаимной простоте \(a\) и \(b\) каждый делитель \(d\mid ab\) единственно представляется как \(d=d_1d_2\), где \(d_1\mid a\), \(d_2\mid b\). Поэтому \(\sigma(ab)=\sum_{d_1\mid a}\sum_{d_2\mid b}d_1d_2=\left(\sum_{d_1\mid a}d_1\right)\left(\sum_{d_2\mid b}d_2\right)=\sigma(a)\sigma(b)\).

Если \(\gcd(a,n)=1\), то \(\gcd(n-a,n)=1\). Эти два остатка различны: равенство \(a=n-a\) дало бы \(2a=n\), откуда \(a\) не взаимно просто с \(n\) при \(n>2\). Значит все взаимно простые остатки разбиваются на пары, и их количество \(\varphi(n)\) чётно.

Рассмотрим числа \(1,2,\ldots,n\). После сокращения дроби \(\frac{k}{n}\) её знаменатель становится некоторым делителем \(d\) числа \(n\). Для фиксированного знаменателя \(d\) числитель может быть любым числом от \(1\) до \(d\), взаимно простым с \(d\), то есть таких дробей \(\varphi(d)\). Все \(n\) значений \(k\) посчитаны ровно один раз, поэтому \(\sum_{d\mid n}\varphi(d)=n\).

Условие даёт \(\frac{n}{\varphi(n)}=2\). Если \(n\) имеет нечётный простой делитель \(p\), то в произведении есть множитель \(\frac{p}{p-1}\), и вместе с возможным множителем \(2\) от простого \(2\) получить ровно \(2\) нельзя. Значит единственный простой делитель \(n\) — \(2\). Поэтому \(n=2^a\), \(a\ge 1\). Все такие числа подходят, так как \(\varphi(2^a)=2^{a-1}\).

Имеем \(\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}=3\). Чтобы произведение было целым и равно \(3\), должны входить простые \(2\) и \(3\): \(\frac{2}{1}\cdot\frac{3}{2}=3\). Любой другой простой \(p\ge 5\) добавит множитель \(\frac{p}{p-1}>1\) и изменит значение. Значит \(n=2^a3^b\), где \(a,b\ge 1\). Все такие \(n\) подходят.

Нужно \(\prod_{p\mid n}\frac{p}{p-1}=\frac52\). Множители от \(2\) и \(5\) дают \(2\cdot\frac54=\frac52\). Если добавить другой простой, произведение изменится. Без \(2\) или без \(5\) значение тоже не получится. Следовательно \(n=2^a5^b\), где \(a,b\ge 1\). Проверка: \(\varphi(2^a5^b)=2^{a-1}\cdot 4\cdot 5^{b-1}=\frac{2}{5}2^a5^b\).

Пусть \(n=2^a\prod p_i^{\alpha_i}\), где \(p_i\) нечётные. Для нечётного \(p\) сумма \(1+p+\cdots+p^\alpha\) имеет \(\alpha+1\) нечётных слагаемых, значит нечётна тогда и только тогда, когда \(\alpha\) чётно. Для \(2^a\) сумма \(1+2+\cdots+2^a\) всегда нечётна. Поэтому \(\sigma(n)\) нечётна ровно тогда, когда все показатели при нечётных простых чётны. Это значит, что нечётная часть \(n\) — квадрат; показатель при \(2\) может быть любым. Если \(a\) чётен, \(n\) квадрат; если \(a\) нечётен, \(n=2\cdot\) квадрат.

Если \(n\) имеет хотя бы два взаимно простых множителя \(p^a\) и \(q^b\), то \(\sigma(n)\) раскладывается в произведение двух чисел больше \(1\), значит не простое. Поэтому \(n=p^a\). Тогда \(\sigma(n)=1+p+\cdots+p^a\). Если \(a+1\) составно, пусть \(a+1=uv\), \(u,v>1\). Тогда \(1+p+\cdots+p^a=\frac{p^{uv}-1}{p-1}\) раскладывается как \(\frac{p^u-1}{p-1}(1+p^u+\cdots+p^{u(v-1)})\), что составно. Значит \(a+1\) простое, а \(\tau(n)=a+1\).

Если \(n=\prod p_i^{a_i}\), то \(\tau(n)=\prod(a_i+1)=14\). Так как \(14=14\) или \(14=7\cdot 2\), получаем два типа. Первый: \(n=p^{13}\). Второй: \(n=p^6q\), где \(p\ne q\) — простые. Других типов нет.

Имеем \(\sigma(p^a)=1+p+\cdots+p^a=\frac{p^{a+1}-1}{p-1}\). Из известного факта \(p^u-1\mid p^v-1\) тогда и только тогда, когда \(u\mid v\), получаем: \(\sigma(p^a)\mid\sigma(p^b)\) тогда и только тогда, когда \(p^{a+1}-1\mid p^{b+1}-1\), то есть \(a+1\mid b+1\). Деление на общий множитель \(p-1\) корректно, потому что обе суммы являются соответствующими геометрическими частными.

Пусть \(m=\prod p^{a_p}\), \(n=\prod p^{b_p}\), где \(0\le a_p\le b_p\). Для простого \(p\) вклад в \(\varphi(p^a)\) равен \(p^{a-1}(p-1)\) при \(a\ge 1\). Если \(a_p=0\), вклада нет. Если \(a_p\ge 1\), то соответствующий вклад в \(\varphi(n)\) содержит \(p^{b_p-1}(p-1)\), который делится на \(p^{a_p-1}(p-1)\). Перемножая по простым, получаем \(\varphi(m)\mid\varphi(n)\).

Для целости \(\frac{n}{\varphi(n)}\) произведение \(\prod_{p\mid n}\frac{p}{p-1}\) должно быть целым. Каждый нечётный простой \(p\) даёт в знаменателе чётный множитель \(p-1\). В числителе произведения простых может быть только один множитель \(2\), если \(2\mid n\). Поэтому нечётных простых делителей не больше одного. Если нечётный простой \(p\) есть, то нужно, чтобы \(p-1\mid 2\), значит \(p=3\), и обязательно \(2\mid n\). Следовательно решения: \(n=1\), \(n=2^a\) при \(a\ge 1\), и \(n=2^a3^b\) при \(a,b\ge 1\). Все они легко проверяются.

Если \(\gcd(a,n)=1\), то \(\gcd(n-a,n)=1\). Пара \(a,n-a\) имеет сумму \(n\). Самопары нет: \(a=n-a\) даёт \(2a=n\), и тогда \(a\) не взаимно просто с \(n\) при \(n>2\); случай \(n=2\) даёт сумму \(1=\frac{2\cdot 1}{2}\). Значит \(\varphi(n)\) чисел разбиваются на \(\frac{\varphi(n)}{2}\) пар, сумма каждой пары \(n\). Итоговая сумма равна \(\frac{n\varphi(n)}{2}\).

Каждому делителю \(d\) соответствует делитель \(\frac{n}{d}\), и произведение пары равно \(n\). Если \(n\) не квадрат, все делители разбиваются на \(\frac{\tau(n)}{2}\) пар, и произведение равно \(n^{\tau(n)/2}\). Если \(n\) квадрат, один делитель \(\sqrt{n}\) спаривается сам с собой; формула всё равно верна, потому что произведение остальных пар даёт \(n^{(\tau(n)-1)/2}\), а оставшийся множитель \(\sqrt{n}\) даёт \(n^{1/2}\). Итого \(n^{\tau(n)/2}\).

Для каждой пары разных делителей \(d\) и \(\frac{n}{d}\) имеем \(d^2+\left(\frac{n}{d}\right)^2\ge 2n\). Такая пара содержит два делителя, значит её вклад не меньше \(n\) на делитель. Если \(n\) квадрат, центральный делитель \(\sqrt{n}\) даёт вклад \(n\), тоже ровно \(n\) на один делитель. Складывая по всем делителям, получаем \(\sigma_2(n)\ge n\tau(n)\).

Пусть \(d\) — наименьший делитель \(n\), больший \(1\). Тогда \(d\le \sqrt{n}\), иначе у \(n\) не было бы делителя между \(1\) и \(\sqrt{n}\). Число \(\frac{n}{d}\) тоже делитель и \(\frac{n}{d}\ge \sqrt{n}\). Делители \(1,d,\frac{n}{d},n\) дают вклад не меньше \(1+d+\frac{n}{d}+n>n+\sqrt{n}\). Значит \(\sigma(n)>n+\sqrt{n}\).

Пусть \(n=\prod_{i=1}^{r}p_i^{a_i}\), где \(r=\omega(n)\). Тогда \(\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1)\). Если среди \(p_i\) нет числа \(2\), то все \(p_i\) нечётны, и каждый множитель \(p_i-1\) чётен; значит \(2^r\mid\varphi(n)\), тем более \(2^{r-1}\mid\varphi(n)\). Если \(2\mid n\), то среди остальных \(r-1\) простых все нечётны, и их множители \(p_i-1\) дают делимость на \(2^{r-1}\). Утверждение доказано.

Если \(n=p\) простое, то все числа \(1,2,\ldots,p-1\) взаимно просты с \(p\), значит \(\varphi(p)=p-1\). Обратно, если \(n\) составное, пусть \(d\) — делитель \(n\), \(1