Let and denote the set of all positive integers and the set of all integers, respectively. Find all functions satisfying: divides if and only if divides , for all positive integers and .
Solution
Answer:
If , then take , since , so but , a contradiction. Hence .
Below we prove that for all positive integers , .
By contradiction, suppose there exists a positive integer such that , and suppose is the smallest such one, then for all we have
but does not divide ,
that is, but does not divide .
Take a prime , and substitute , we get
so , but , a contradiction.
Therefore .
For any positive integer , take a sufficiently large , then
since can be arbitrarily large, therefore only . Q.E.D.!
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.