Problem
NT-B2-M10-P020 Prime If and Only If
#20
★★★★☆ Level 4 of 5
Prove that \(n\ge 2\) is prime if and only if \(\varphi(n)=n-1\).
1001 Problems in Classical Number Theory (method inspiration) · Problem 729
If \(n\) is composite, find a number \(1
If \(n=p\) is prime, then all numbers \(1,2,\ldots,p-1\) are coprime to \(p\), so \(\varphi(p)=p-1\). Conversely, if \(n\) is composite, let \(d\) be a divisor of \(n\) with \(1
The final problem is simpler than the previous one, but closes the basic primality criterion.