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 $n^2$ and $n^2+n$, exclusive, does not exist any triplet of friendly numbers. b) Determine if for each $n$ exists a triplet of friendly numbers between $n^2$ and $n^2+n+3\sqrt{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 $n^2+a \mid (n^2+b)(n^2+c)$. This means $$ (n^2+a) \mid (b-a)(c-a)$$But $$ 0<|(b-a)(c-a)| < n^2< n^2+a$$which 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\sqrt{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. $n^2 + a | (b - a)(c - a)$ As the numbers $a, b, c$ are quite small, condition 3 actually forces us to have $n^2 + 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 $n^2 + a = |xy|$ with $-a < x, y < f(n) - a$. That is, $n^2 + a = xy$ with $0 \le x, y < \max(a, f(n) - a)$. 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.