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 == | ||
| − | + | 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. | ||
| − | \ | ||
| − | \ | + | 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 |
| + | <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 
such that ![\[\phi(n)>n-\sqrt{n},\]](http://latex.artofproblemsolving.com/2/2/7/2278d67dcf2c3f9a73967961071ed4672ca776ae.png)
where 
denotes the number of integers less than or equal to 
that are relatively prime to .
Solution
We claim that 
if and only if is prime. \\
IF: If is prime, then 
, which is true for all 
. \\
ONLY IF: If is not prime, then must have a prime divisor 
such that 
; if this was not the case, then the number of not necessarily distinct prime factors could have would be 
, 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}\]](http://latex.artofproblemsolving.com/b/0/4/b04a56580674ee898087c1e87f6c518bab1916c5.png)
.
