Problem:
For positive integers and , define to be -nice if there exists a positive integer such that has exactly positive divisors. Find the number of positive integers less than that are neither -nice nor -nice.
Solution:
Consider numbers of the form , where is a prime and is a nonnegative integer. Then has positive divisors. Thus all numbers that are one more than a nonnegative multiple of are -nice. Conversely every -nice number must be one more than a nonnegative multiple of . This is because if an integer can be written in the form , where are distinct primes and are nonnegative integers, then has positive divisors, and by considering each parenthesized factor of modulo , it is clear that . It follows that there are positive integers less than that are -nice. Thus there are positive integers less than that are -nice, and there are positive integers less than that are -nice. Because and are relatively prime, there are positive integers less than that are both -nice and -nice. Thus there are a total of positive integers less than 1000 that are neither -nice nor -nice.
The problems on this page are the property of the MAA's American Mathematics Competitions