Problem:
For a positive integer , denote by the number of positive integers relatively prime to . How many positive integers less than or equal to are divisible by ?
Problem:
For a positive integer , denote by the number of positive integers relatively prime to . How many positive integers less than or equal to are divisible by ?
Solution:
We claim that any such integer must be either equal to or of the form , where and .
First, we note that if , it must be even. This is because if admits a prime factorization over distinct primes , then . In particular, if an odd prime divides then divides , and consequently is even.
Then, we note that at most one odd prime divides . Suppose otherwise, i.e., is a part of the prime factorization of for odd primes . Then by the multiplicativity of , we know that
must divide . Note that the largest power of dividing is , but since and are both even, divides . This is a contradiction.
Finally, we show that the said odd prime dividing must in fact be equal to . Indeed, if where and are positive integers, we have
For this to be an integer, .
Hence, we count all such integers of the form by summing over all possible values of (because there are fewer):
If , then . (This is the only case in which is allowed.)
If , then .
If , then .
If , then .
This gives us a total of values of .