Let be the product of the first 10 primes, and let where denotes the number of positive integers less than or equal to that are relatively prime to , and the sum is taken over ordered pairs of positive integers for which divides . Compute .
Solution
Solution 1: We see that, for any positive integer , Since and are both weakly multiplicative (if and are relatively prime, then and , we may break this up as where the product is over all primes that divide . This is simply , giving an answer of . Solution 2: We recall that So, we may break up the sum as so is simply times the number of divisors of . This number is . Solution 3: When constructing a term in the sum, for each prime dividing , we can choose to include in , or in , or in neither. This gives a factor of , or 1, respectively. Thus we can factor the sum as So the answer is 1024.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.