Задача
NT-B2-M10-P015 Сумма взаимно простых чисел
#15
★★★★☆ Уровень 4 из 5
Докажите, что при \(n>1\) сумма всех положительных \(a\le n\), взаимно простых с \(n\), равна \(\frac{n\varphi(n)}{2}\).
1001 Problems in Classical Number Theory (method inspiration) · Задача 531
Сопрягите \(a\) с \(n-a\).
Если \(\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}\).
Очень полезная пара-идея.