We say that three different integers are friendly if one of them divides the product of the other two. Let n be a positive integer. a) Show that, between n2 and n2+n, exclusive, does not exist any triplet of friendly numbers. b) Determine if for each n exists a triplet of friendly numbers between n2 and n2+n+3√n , exclusive.
Problem
Source: Cono Sur Olympiad 2016, problem 6
Tags: number theory, cono sur
29.08.2017 00:24
a) Assume the contrary. Then there exist three distinct integers 0<a,b,c<n such that n2+a∣(n2+b)(n2+c). This means (n2+a)∣(b−a)(c−a)But 0<|(b−a)(c−a)|<n2<n2+awhich is a contradiction.
29.12.2018 05:07
b) I am going to solve this for sufficiently large n only, because I'm too tired to work on the details. However, the inequalities are effective, and a solution covering small n can be written. Also, I have checked that such an n exists for all n up to some thousands, so at least the answer to the question is "yes". I'm writing this like a story on how to solve this problem, which makes the solution rather long (and some people probably don't appreciate this way of writing). I decided so because I thought the solution was difficult to find, and it was hard to get a proper grip of the problem. Let f(n)=n+3√n. We want to find integers a,b,c, so that the following conditions hold: 1. 0<a,b,c<f(n). 2. a,b,c are all distinct 3. n2+a|(b−a)(c−a) As the numbers a,b,c are quite small, condition 3 actually forces us to have n2+a=|(b−a)(c−a)|. We note two things: (i) a must be quite small or quite large, or otherwise the product |(b−a)(c−a)| is too small. (ii) Taking x=b−a and y=c−a we want n2+a=|xy| with −a<x,y<f(n)−a. That is, n2+a=xy with 0≤x,y<max. We can, of course, forget about b and c, and focus on x and y only. The last inequality of (ii) tells us that if we pick a to be very small or very large, we may pick x and y to be quite big (a lot of options), and (i) says that we are actually forced to do so. We will pick this bound to be 2\sqrt{n} (the bound \sqrt{n} was my first guess, but does not quite work I think), that is, we will only focus on the integers a such that a < 2\sqrt{n} or a > f(n) - 2\sqrt{n}. In fact, we will only need the very big values of a, and not the small ones. Since either a < 2\sqrt{n} or a > f(n) - 2\sqrt{n}, by the bound of (ii) we can always, for all a, choose x and y to be at most f(n) - 2\sqrt{n} = n + \sqrt{n}. Keep in mind that x and y both have to be around n for n^2 + a = xy to work. Thus, it is intuitive to write x = n + p, y = n - q. We have to have p \le \sqrt{n}, and q probably has to be quite small too. Now, xy = n^2 + n(p - q) - pq. This number should either be between n^2 and n^2 + 2\sqrt{n} (small a), or between n^2 + f(n) -2\sqrt{n} and n^2 + f(n) (large a). We shall aim for a large a. p - q = 1 won't suffice, so we try for p - q = 2. Therefore we look at numbers of the form \begin{align*} n^2 + 2n - q(q+2) \end{align*} Now, we will choose q depending on how big the fractional part of \sqrt{n} is (this case really turned out to be a lot messier than I originally thought, but I hope the final version works. On the other hand, I think this also works for small n). Remember that our target is to choose q so that n^2 + n + \sqrt{n} < n^2 + 2n - q(q+2) < n^2 + f(n). Case 1. 0 \le \lbrace \sqrt{n} \rbrace < 0.5. We choose q = \sqrt{n} - 2, rounded down. A lower-bound for n^2 + n - q(q+2) is n^2 + 2n - (\sqrt{n} - 2)(\sqrt{n}) = n^2 + n + 2\sqrt{n}, which is fine. For the upper-bound, we have q > \sqrt{n} - 2.5, so n^2 + 2n - q(q+2) < n^2 + 2n - (\sqrt{n} - 2.5)(\sqrt{n} - 0.5) = n^2 + n + 3\sqrt{n} + 2.5 \cdot 0.5 < n^2 + n + f(n). Case 1 is solved. Case 2. \lbrace \sqrt{n} \rbrace > 0.5 We choose q = \sqrt{n} - 1, rounded down. For the lower-bound we note q < \sqrt{n} - 1.5, and therefore n^2 + 2n - q(q+2) > n^2 + 2n - (\sqrt{n} - 1.5)(\sqrt{n} - 0.5) = n^2 + n + 2\sqrt{n} - 1.5 \cdot 0.5 > n^2 + n + \sqrt{n}. For the upper-bound we note q > \sqrt{n} - 2, and so n^2 + 2n - q(q+2) \le n^2 + 2n - (n - 2\sqrt{n}) = n^2 + n + 2\sqrt{n}. Case 2 is solved. So, we are done! To wrap up, here's what we do: pick x and y to be about n + \sqrt{n} and n - \sqrt{n} (details above). The product xy is a number between n^2 + n + \sqrt{n} and n^2 + n + 3\sqrt{n}, exclusive. Therefore there exists such an a that n^2 + a = xy, and n + \sqrt{n} < a < n^2 + n + 3\sqrt{n}. Let b = a - x and c = a - y. By the choice of x and y, and the bound on a we have b, c > 0, and also of course b, c < f(n). Therefore, there exists such integers a, b, c that satisfy the three conditions mentioned before. The conditions 1 and 3 have been handled already, and the condition 2 is a direct consequence of the construction (just note that x, y, a \approx n, so b, c \approx \sqrt{n} or something, so b, c \neq a. b and c are distinct, of course). Also, interesting note: by computer we can find that there are no a, b, c with 0 < a, b, c < n + 2\sqrt{n}. I feel like (2 + \epsilon )\sqrt{n} works for all \epsilon > 0 and n large enough, but I'm not sure. The constant 3 is not optimal, that's for sure.
11.08.2019 13:50
for part b), I got the following construction. For each positive integer n, let u be the maximal integer which satisfies u^2 - u < n, then we have (u+1)^2 - (u+1) \geq n, or n \leq u^2+u. Let p = n-u+1 and q = n+u. It is easy to see that a=p(q+1), b=(p+1)q and c=pq are friendly as c divides ab. Since c<a<b, we now check that c>n^2 and b<n^2+n+3\sqrt{n}. Indeed, c=pq=(n-u+1)(n+u) = n^2 - u^2 + n + u > n^2 is already established by the definition of u. Notice that b = (p+1)q = (n-u+2)(n+u) = n^2 - u^2 + 2n + 2u, we need to show that n^2 - u^2 + 2n + 2u < n^2 + n + 3\sqrt{n}, which is equivalent to n-3\sqrt{n} < u^2 - 2u. By using \sqrt{n}\leq\sqrt{u^2+u}, the above inequality is easy to check.