Задача
NT-B2-M10-P004 Чётность функции Эйлера
#4
★★☆☆☆ Уровень 2 из 5
Докажите, что при \(n>2\) число \(\varphi(n)\) чётно.
1001 Problems in Classical Number Theory (method inspiration) · Задача 523
Сопряжите каждый взаимно простой остаток \(a\) с \(n-a\).
Если \(\gcd(a,n)=1\), то \(\gcd(n-a,n)=1\). Эти два остатка различны: равенство \(a=n-a\) дало бы \(2a=n\), откуда \(a\) не взаимно просто с \(n\) при \(n>2\). Значит все взаимно простые остатки разбиваются на пары, и их количество \(\varphi(n)\) чётно.
Источник-идея стандартная; полезно перед задачами на \(\varphi(n)\).