Задача
NT-B2-M10-P012 Делимость сумм простых степеней
#12
★★★★☆ Уровень 4 из 5
Пусть \(p\) — простое, \(a,b\ge 0\). Докажите, что \(\sigma(p^a)\mid \sigma(p^b)\) тогда и только тогда, когда \(a+1\mid b+1\).
1001 Problems in Classical Number Theory (method inspiration) · Задача 498
Используйте \(\sigma(p^a)=\frac{p^{a+1}-1}{p-1}\).
Имеем \(\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\) корректно, потому что обе суммы являются соответствующими геометрическими частными.
Можно предварительно напомнить НОД степеней \(p^u-1\).