Find the number of positive integers satisfying such that
What is the largest number among them? As usual, is the number of positive integers less than or equal to and relatively prime to
Solution
Let us analyze the problem and find the positive integers such that and:
### Step 1: Simplify the Sum
The expression inside the sum, , evaluates to 1 if divides , and 0 otherwise. Thus, the sum counts the number of divisors of .
This implies:
where is the number of divisors of .
### Step 2: Consider
The condition implies that must be a power of a prime, say .
For prime powers, , and divides .
### Step 3: Prime Power Condition
Using the formula for the number of divisors of a prime power:
Hence, .
### Step 4: Maximize
To find the largest , assume is the smallest prime, (since 2 will not satisfy for powers greater than 1).
Thus, .
Hence, the largest satisfying both and is:
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.