Maths Olympiad Prep

Library / /14 of 16

Number theory Difficulty 6.6 National Olympiad Prove it Italy

Problem:

a. Suppose that n=k2n = k^{2} is a perfect square. Prove that the number of positive divisors of nn strictly less than kk is equal to the number of divisors of nn strictly greater than kk.

b. Suppose that n=k2n = k^{2} is a perfect square. Prove that nn has at most 2k12k-1 positive divisors.

c. Find all positive integers kk such that k2k^{2} has exactly 2k12k-1 positive divisors.

Solution

Solution:

a. If dd is a divisor of nn then n/dn / d is also a divisor of nn. It follows that for every divisor dd of n=k2n = k^{2} with 0<d<k0 < d < k there exists a corresponding divisor n/dn / d with n/d=k2/d>kn / d = k^{2} / d > k, and conversely for every divisor dd of k2k^{2} with d>kd > k there exists a corresponding divisor 0<n/d<k0 < n / d < k.
The positive divisors of k2k^{2} less than kk are therefore just as many as those greater than kk, as required.

Alternative solution. If nn is a perfect square, its prime factorization has the form n=p12α1p22α2pi2αin = p_{1}^{2\alpha_{1}} \cdot p_{2}^{2\alpha_{2}} \cdots p_{i}^{2\alpha_{i}}. Its divisors are numbers of the form p1β1piβip_{1}^{\beta_{1}} \cdots p_{i}^{\beta_{i}}, with 0βj2αj0 \leq \beta_{j} \leq 2\alpha_{j} for every j=1,,ij = 1, \ldots, i. In particular k=p1α1p2α2piαik = p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdots p_{i}^{\alpha_{i}}. If we write n=dndn = d \cdot \frac{n}{d} as a product of two of its divisors, we must redistribute the prime factors of nn between the two divisors considered. We will thus have that the two factors are of the form
d=p1β1piβi,nd=p12α1β1pi2αiβi d = p_{1}^{\beta_{1}} \cdots p_{i}^{\beta_{i}}, \quad \frac{n}{d} = p_{1}^{2\alpha_{1} - \beta_{1}} \cdots p_{i}^{2\alpha_{i} - \beta_{i}}
which we can write, in terms of kk, as
d=kp1β1α1piβiαi,nd=kp1α1β1piαiβi: d = k \cdot p_{1}^{\beta_{1} - \alpha_{1}} \cdots p_{i}^{\beta_{i} - \alpha_{i}}, \quad \frac{n}{d} = k \cdot p_{1}^{\alpha_{1} - \beta_{1}} \cdots p_{i}^{\alpha_{i} - \beta_{i}}:
we are multiplying kk by a number and by its reciprocal, so one of dd and n/dn / d will be greater than kk and the other will be less than kk. In particular, for every divisor less than kk there is one greater than kk.

b. By what was shown in part (a), the divisors in total are twice those less than kk plus 1 (that is, the divisor kk). The positive integers less than kk are k1k-1, so nn can have at most 2(k1)+1=2k12(k-1)+1 = 2k-1 divisors.

c. Continuing the reasoning made in part (b), saying that n=k2n = k^{2} has 2k12k-1 divisors means that all positive integers less than or equal to kk divide nn. Observe that for k=1k = 1 we have n=1n = 1, which has a unique positive divisor (itself), so indeed the number of divisors is 2k1=2112k-1 = 2 \cdot 1 - 1. Similarly, for k=2k = 2 we have n=4n = 4, whose divisors are 1,21, 2 and 44, as required: 221=32 \cdot 2 - 1 = 3. We then observe that an integer nn has no divisors >1>1 in common with n1n-1. If k3k \geq 3 this leads to a contradiction: we observed that k1>1k-1 > 1 must divide k2k^{2}, and this is absurd because k1k-1 divides n1=k21=(k+1)(k1)n-1 = k^{2} - 1 = (k+1)(k-1). There are therefore no solutions for k3k \geq 3, so the desired kk are only k=1k = 1 and k=2k = 2.

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 translated into English from it; metadata (topic, difficulty) added by this project.