Northeastern WOOTers Mock AIME I Problems/Problem 15
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
.