Use a standard induction argument. Show that it is true for . Assume it is true for all values up to . Prove it is true for .

So, , so it is obviously true for . Next, assume it is true up to . How would you show it is true for ? There are two cases. Either is prime or there exists some prime number . If it is the latter case, then you are done. So, suppose is prime. Let's consider the factors of . Since is prime, it is not a factor of , so any factor of that is greater than is also greater than . There are at most factors that are greater than and at most factors that are greater than 1 and less than or equal to . So, for , its factors that are greater than are the factors of that are greater than , those same factors times , and also the factors of that are no greater than multiplied by . So, there are at most factors of that are greater than . All that remains is to show that .

This was only a very rough outline of what you need to prove. You would need to flesh it out.

Edit: Reading through this, this is not a terribly good method. Instead, you should probably use Euler's totient.

If is prime, . If and then has a prime factor greater than or equal to . So, you just need to show that for all . By assumption, is prime, so it is relatively prime to . Hence 1 and are both relatively prime to making . This means there are at least relatively prime numbers to . For every , implying that at least one of the numbers relatively prime to is greater than .