Difference between revisions of "Northeastern WOOTers Mock AIME I Problems/Problem 15"
m (→Solution) |
m (→Solution) |
||
Line 13: | Line 13: | ||
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. | ||
− | 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 \ | + | 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}. |
Revision as of 20:24, 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.
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 Note that the edge case of does not conflict with this.
This proves both directions of the claim. All that remains is to sum the first prime numbers, starting with and ending with , to obtain an answer of \boxed{963}.