Difference between revisions of "Northeastern WOOTers Mock AIME I Problems/Problem 15"
m (→Solution) |
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. | + | We claim that <math>\phi(n)>n-\sqrt{n}</math> if and only if <math>n</math> is prime or <math>1</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>. | + | '''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>. For <math>n = 1</math> the statement is true as well. |
− | '''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 and not <math>1</math>, 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> | ||
− | |||
− | 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 <math>\boxed{ | + | 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>, and add <math>1</math> to obtain an answer of <math>\boxed{964}</math>. |
Revision as of 20:33, 7 August 2021
Problem 15
Find the sum of all integers such that 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 or .
IF: If is prime, then , which is true for all . For the statement is true as well.
ONLY IF: If is not prime and not , 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
This proves both directions of the claim. All that remains is to sum the first prime numbers, starting with and ending with , and add to obtain an answer of .