NT-B2-M10-P010 Простая сумма делителей

Сначала покажите, что \(n\) должно быть степенью простого.

Если \(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\).

Сильная задача на разложение геометрической суммы.