Задача
NT-B2-M10-P020 Простой тогда и только тогда
#20
★★★★☆ Уровень 4 из 5
Докажите, что \(n\ge 2\) простое тогда и только тогда, когда \(\varphi(n)=n-1\).
1001 Problems in Classical Number Theory (method inspiration) · Задача 729
Если \(n\) составное, найдите число \(1
Если \(n=p\) простое, то все числа \(1,2,\ldots,p-1\) взаимно просты с \(p\), значит \(\varphi(p)=p-1\). Обратно, если \(n\) составное, пусть \(d\) — делитель \(n\), \(1
Финальная задача проще предыдущей, но закрывает базовый признак простоты.