Let denote the set of all positive integers and denote the set of all prime numbers. For subsets and of , is called -proper if there exists a positive integer such that for all and integer with there exist not necessarily distinct elements of satisfying the conditions and . Find a subset of for which is -proper but is not.
Solution
We will show that the set is an appropriate example.
We first prove that is -proper for . Let be prime and . Then by Chinese remainder theorem there exists a positive integer satisfying the conditions and . Therefore, by Fermat's theorem we obtain that . For ; as , works.
Now suppose that is -proper. Then there exists a positive integer satisfying the given conditions. Therefore we can get any residue in as sum of at most elements of . Since for all , we have that for each integer , there exist non-negative integers such that
and . Observe that for each , we get a different -tuple. On the other hand, the number of -tuples of non-negative integers satisfying is and hence we get a contradiction.
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.