Number theoryDifficulty 7.8National Olympiad, round 2Prove itBaltic Way
Nonnegative integers a and b have the following property: d(na)≥d(nb) for each positive integer n (where d(k) is the number of divisors of k). Prove that a is divisible by b.
Solution
Let a=p1α1…pmαm, b=p1β1…pmβm be the prime decompositions of these numbers (we assume that some αk,βk can be equal to 0). Let us check that for each kαk≥βk. Indeed, if the inequality does not hold for some k, say, α1<β1, then for n=p2s…pms we have 1≤d(nb)d(na)=β1(s+β2)…(s+βm)α1(s+α2)…(s+αm) For big s this fraction is close to β1α1<1. 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.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.