Maths Olympiad Prep

Library / /2 of 4

, 2020

Number theory Difficulty 8.3 Shortlist Prove it Netherlands

For a positive integer nn, let d(n)d(n) be the number of positive divisors of nn. Determine the positive integers kk for which there exist positive integers aa and bb satisfying
k=d(a)=d(b)=d(2a+3b). k = d(a) = d(b) = d(2a + 3b).

Solution

For i0i \ge 0, let a=25ia = 2 \cdot 5^i and b=35ib = 3 \cdot 5^i. Then both aa and bb have 2(i+1)2(i+1) divisors. Moreover, we have 2a+3b=45i+95i=135i2a+3b = 4 \cdot 5^i + 9 \cdot 5^i = 13 \cdot 5^i, which also has 2(i+1)2(i+1) divisors. Therefore all even values of kk satisfy the condition in the problem.

Now suppose that kk is odd. Then aa has an odd number of divisors and therefore is a square, say a=x2a = x^2. The same reasoning shows that bb is also a square, say b=y2b = y^2, and 2a+3b2a+3b is also a square, say 2a+3b=z22a+3b = z^2. Therefore we have
2x2+3y2=z2. 2x^2 + 3y^2 = z^2.
We show that this equation has no positive integer solutions.

Suppose for a contradiction that this equation does have a positive integer solution. Let (x,y,z)=(u,v,w)(x, y, z) = (u, v, w) be the solution with minimal x+y+zx+y+z. So 2u2+3v2=w22u^2 + 3v^2 = w^2. Modulo 33 this equation is 2u2w22u^2 \equiv w^2. If uu is not divisible by 33, then u21(mod3)u^2 \equiv 1 \pmod{3}, so w2=2u22(mod3)w^2 = 2u^2 \equiv 2 \pmod{3}, however, that isn't possible. Therefore uu is divisible by 33, from which it follows that ww is divisible by 33 as well. Now 2u22u^2 and w2w^2 are both divisible by 99, so 3v23v^2 is divisible by 99. It follows that vv is divisible by 33 as well. However, now (x,y,z)=(u3,v3,w3)(x, y, z) = (\frac{u}{3}, \frac{v}{3}, \frac{w}{3}) also satisfies the equation, and it is a solution with smaller x+y+zx+y+z than the supposed minimal one. This is a contradiction. Therefore the equation 2x2+3y2=z22x^2 + 3y^2 = z^2 has no positive integer solutions.

It follows that no odd kk satisfies the condition in the problem. The positive integers kk that satisfy that condition are therefore the even integers. \square

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 and solution reproduced as published; topic and difficulty added by this site.