Consider a square-free even integer $n$ and a prime $p$, such that 1) $(n,p)=1$; 2) $p\le 2\sqrt{n}$; 3) There exists an integer $k$ such that $p|n+k^2$. Prove that there exists pairwise distinct positive integers $a,b,c$ such that $n=ab+bc+ca$. Proposed by Hongbing Yu
Problem
Source: 2012cmo,problem5
Tags: modular arithmetic, inequalities, number theory proposed, number theory
12.01.2012 17:54
Sorry, but what is $x$?
13.01.2012 05:59
I think $x$ should be replaced by $n$. I think this solution works (but I may have made a mistake). Solution Let $k \equiv m \pmod{p}$ where $0 \le m < p$. Note that $m>0$ since $p|k$ would imply that $p|n$ which is a contradiction. Since $\gcd(n,p)=1$ and $n$ is even, it follows that $p$ is odd. Hence $p-m$ and $m$ are of different parity. Let $c$ be the odd positive integer in the set $\{m, p-m \}$. Since $0<m<p$ and $p| n+k^2$, it follows that $c>0$ and that $p| n+c^2$. Now let $pq = n+c^2$ where $q\in \mathbb{N}$. Now note that by AM-GM, \[q=\frac{n+c^2}{p} \ge \frac{2c\sqrt{n}}{p} \ge c.\] However, since $n$ is square-free, it cannot follow that $n=c^2$ and therefore the inequality is strict and $q>c$. Now let $a=q-c$ and $b=p-c$ and note that \[n+c^2 = pq = (a+c)(b+c)=ab+ac+bc+c^2.\] This implies that $n=ab+bc+ca$ where $a,b,c>0$ since $c>0$, $q>c$ and $p>c$. Now it remains to show that $a$, $b$ and $c$ are pairwise distinct. If $b=c$, then $p=2c$ which contradicts the fact that $p$ is odd. If $a=b$, then $p=q$ which implies that $n=p^2 - c^2 = (p-c)(p+c)$. However, since $p$ and $c$ are both odd, $2|p-c$ and $2|p+c$ and hence $4|n$ which contradicts the fact that $n$ is square-free. If $a=c$, then $q=2c$ and $2pc-n=c^2$ which is a contradiction since $n$ is even and $c$ is odd. Hence $a$, $b$ and $c$ are pairwise distinct as desired.
12.03.2012 19:48
Solution : Let $0<k<p$ , $n=pl-k^2$ , for natural $l$ $n=pl-k^2>\frac{p^2}{4}$ , so $pl> \frac{p^2}{4}+k^2\ge pk$ , $l>k$ Let $a=k$ , $b=l-k$ , $c=p-k$ , easy to see that $ab+bc+ca=lp-k^2=n$ Easy to check that $a$ , $b$ , $c$ are distinct . done
06.11.2016 17:21
Mosquitall wrote: Solution : Let $0<k<p$ , $n=pl-k^2$ , for natural $l$ $n=pl-k^2>\frac{p^2}{4}$ , so $pl> \frac{p^2}{4}+k^2\ge pk$ , $l>k$ Let $a=k$ , $b=l-k$ , $c=p-k$ , easy to see that $ab+bc+ca=lp-k^2=n$ Easy to check that $a$ , $b$ , $c$ are distinct . done wouldn't be the whole solution as $n=pl-k^2$ isn't the only possible case
11.07.2021 15:29
Here's my solution. Hopefully different and (imho) easier. The solution is based on reverse engineering. Wlog assume $k<p$ (or else we can take $k\to k\pmod p$ ). One can rewrite the desired form of $n$ as $c(a+b)+ab$. So if there's such $c$, we must have $$a+b\mid n-ab\leftrightarrow a+b\mid n+a^2$$Why not $a=k, b=p-k \hspace{2 mm} \text{and} \hspace{2 mm} c=\frac{n-k(p-k)}{p}$ ? Note that $n+k^2>kp$ and clearly $a\neq b$. $\bullet \hspace{2 mm}$ if $a=c$, that is $2kp=n+k^2\to 4\mid n$, absurd. $\bullet \hspace{2 mm}$ if $b=c$, that is $n=p^2-k^2\to 4\mid n$, absurd. So the given construction works and we're done. $\blacksquare$ Remark. I wonder if All-Russian 2021/10.7 is inspired from this or not.