Northeastern WOOTers Mock AIME I Problems/Problem 15

Problem 15

Find the sum of all integers $n\le96$ such that $\phi(n)>n-\sqrt{n},$ where $\phi(n)$ denotes the number of integers less than or equal to $n$ that are relatively prime to $n$ .

Solution

We claim that $\phi(n)>n-\sqrt{n}$ if and only if $n$ is prime. \\

IF: If $n$ is prime, then $\phi(n) = n - 1 > n - \sqrt{n}$ , which is true for all $n \geq 2$ . \\

ONLY IF: If $n$ is not prime, then $n$ must have a prime divisor $p$ such that $p \leq \sqrt{n}$ ; if this was not the case, then the number of not necessarily distinct prime factors $n$ could have would be $1$ , contradiction. It follows that $\phi(n) \leq \left( 1 - \frac{1}{p} \right) \cdot n \leq \left( 1 - \frac{1}{\sqrt{n}} \right) \cdot n = n - \sqrt{n}$ .

Page

Toolbox

Search

Northeastern WOOTers Mock AIME I Problems/Problem 15

Problem 15

Solution