Example 9. Let be a strictly increasing function defined on the set of natural numbers and taking natural number values, with , and when , are coprime, . Prove that for all natural numbers , .
Solution
Proof Given that
If the proposition is not true, let the smallest positive integer for which be . Since , it follows that . Furthermore, because is strictly increasing, we have
When is odd, 2 and are coprime, so we have
Since , it follows that , which contradicts (1). When is even, 2 and are coprime, so we have
Clearly, , which contradicts (1).
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.