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 or | + | We claim that <math>\phi(n)>n-\sqrt{n}</math> if and only if <math>n</math> is prime or 1. |
'''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. | '''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. |
Revision as of 21: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 1.
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
.