Maths Olympiad Prep

Library / /17 of 33

, 2011

Number theory Difficulty 7.8 National Olympiad, round 2 Prove it Baltic Way

Nonnegative integers aa and bb have the following property: d(na)d(nb)d(na) \ge d(nb) for each positive integer nn (where d(k)d(k) is the number of divisors of kk). Prove that aa is divisible by bb.

Solution

Let a=p1α1pmαma = p_1^{\alpha_1} \dots p_m^{\alpha_m}, b=p1β1pmβmb = p_1^{\beta_1} \dots p_m^{\beta_m} be the prime decompositions of these numbers (we assume that some αk,βk\alpha_k, \beta_k can be equal to 00). Let us check that for each kk αkβk\alpha_k \ge \beta_k. Indeed, if the inequality does not hold for some kk, say, α1<β1\alpha_1 < \beta_1, then for n=p2spmsn = p_2^s \dots p_m^s we have
1d(na)d(nb)=α1(s+α2)(s+αm)β1(s+β2)(s+βm) 1 \le \frac{d(na)}{d(nb)} = \frac{\alpha_1(s + \alpha_2) \dots (s + \alpha_m)}{\beta_1(s + \beta_2) \dots (s + \beta_m)}
For big ss this fraction is close to α1β1<1\frac{\alpha_1}{\beta_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.