Difference between revisions of "Northeastern WOOTers Mock AIME I Problems/Problem 15"

(Created page with "== Problem 15 == Find the sum of all integers <math>n\le96</math> such that <cmath>\phi(n)>n-\sqrt{n},</cmath> where <math>\phi(n)</math> denotes the number of integers less...")
 
m (Solution)
Line 8: Line 8:
 
== Solution ==
 
== Solution ==
  
\begin{claim}
+
We claim that <math>\phi(n)>n-\sqrt{n}</math> if and only if <math>n</math> is prime. \\
<math>\phi(n)>n-\sqrt{n}</math> if and only if <math>n</math> is prime.
 
\end{claim}
 
  
\begin{proof}
+
IF: If <math>n</math> is prime, then <math>\phi(n) = n - 1 > n - \sqrt{n}</math>, which is true for all <math>n \geq 2</math>. \
F
+
 
\end{proof}
+
ONLY IF: If <math>n</math> is not prime, then <math>n</math> must have a prime divisor <math>p</math> such that <math>p \leq \sqrt{n}</math>; if this was not the case, then the number of not necessarily distinct prime factors <math>n</math> could have would be <math>1</math>, contradiction. It follows that
 +
<cmath> \phi(n) \leq \left( 1 - \frac{1}{p} \right) \cdot n \leq \left( 1 - \frac{1}{\sqrt{n}} \right) \cdot n = n - \sqrt{n} </cmath>.

Revision as of 20:18, 7 August 2021

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}\].