Olympiad Maths Prep

Library / /20 of 21

Number theory Difficulty 7.0 National olympiad Prove it Ukraine

Let's call a positive integer square-free, if it's not divisible by p2p^2 for any prime pp. You are given a squarefree integer n>1n > 1, which has precisely dd positive divisors. What largest number of divisors of this number can you choose, so that for any two of them, let's denote them by aa and bb, the number a2+abna^2 + ab - n isn't a square of an integer?
(Oleksii Masalitin)

Solution

Answer: d2\frac{d}{2}

As n>1n > 1 is squarefree, it can't be a square of an integer. Then all divisors of nn can be split into pairs (t1,t2)(t_1, t_2), (t3,t4)(t_3, t_4), ..., (td1,td)(t_{d-1}, t_d) in such a way, that the product of numbers in each pair is nn. If we choose (a,b)(a, b) from the same pair, then a2+abn=a2a^2 + ab - n = a^2, contradiction. So, we chose at most one number from each pair, so we selected at most d2\frac{d}{2} in total.

Let's show that we can always choose d2\frac{d}{2} integers. Consider any prime divisor pp of nn and choose all divisors of nn, which are divisible by pp. It's easy to see that there are d/2d/2 of them. Let's show that they satisfy the condition from the statement. Let a=kp,b=lpa = kp, b = lp be any divisors from the chosen group, and n=ptn = pt. Note that l,k,tl, k, t aren't divisible by pp. Then a2+abn=p(pk2+pklt)a^2 + ab - n = p(pk^2 + pkl - t) and the number in brackets isn't divisible by pp, as tt isn't divisible by pp. So, a2+abna^2 + ab - n is divisible by pp, but not by p2p^2, and, therefore, can't be a square of an integer.

Looking for a route rather than 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.