Track / Stage 5 / 326 of 400 #926 of 1964

Problem 926

AIME late

Number theory Difficulty 5.7 Prove it

Show that a positive integer $n$ is composite if and only if $\phi(n) \leqslant n-\sqrt{n}$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

None

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.