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 .
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 \fbox{}.