MathDB

\phi (n) >= \pi (n) / 2

Source: 2006 VMEO III Shortlist SL N10 Vietnamese Mathematics e - Olympiad https://artofproblemsolving.com/community/c2461015_vmeo__vie

October 28, 2021

number theoryphi functioninequalities

Problem Statement

The notation

\phi (n)

is the number of positive integers smaller than

n

and coprime with

n

\pi (n)

is the number of primes that do not exceed

n

. Prove that for any natural number

n > 1

, we have

\phi (n) \ge \frac{\pi (n)}{2}