Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution)
m (→‎Solution)
Line 10: Line 10:
 
We claim that <math>\phi(n)>n-\sqrt{n}</math> if and only if <math>n</math> is prime.  
 
We claim that <math>\phi(n)>n-\sqrt{n}</math> if and only if <math>n</math> is prime.  
  
−
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>.  
+
'''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>.  
  
−
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
+
'''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>
 
<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>
 
Note that the edge case of <math>n = 1</math> does not conflict with this.
 
Note that the edge case of <math>n = 1</math> does not conflict with this.
  
−
This proves both directions of the claim. All that remains is to sum the first <math>24</math> prime numbers, starting with <math>2</math> and ending with <math>89</math>, to obtain an answer of \boxed{963}.
+
This proves both directions of the claim. All that remains is to sum the first <math>24</math> prime numbers, starting with <math>2</math> and ending with <math>89</math>, to obtain an answer of \box{963}.

Revision as of 21:26, 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}.\] Note that the edge case of $n = 1$ does not conflict with this.

This proves both directions of the claim. All that remains is to sum the first $24$ prime numbers, starting with $2$ and ending with $89$, to obtain an answer of \box{963}.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Northeastern_WOOTers_Mock_AIME_I_Problems/Problem_15&oldid=159732"