Find all pairs $(n,d)$ of positive integers such that $d\mid n^2$ and $(n-d)^2<2d$. Linus Tang
Problem
Source: ELMO Shortlist 2024/N1
Tags: Elmo, number theory
22.06.2024 18:57
If $n=d$, then the conditions hold, so assume $n\neq d$. Write $a = n-d \neq 0$, then $d$ divides $(a+d)^2$, i.e. $d$ divides $a^2$; and also $a^2 < 2d$. Since $d$ and $a^2$ are positive, the only option is $d = a^2$. This gives the solutions $(n, d) = (a^2 + a, a^2)$ for arbitrary $a\neq 0, -1$.
22.06.2024 20:00
IAmTheHazard wrote: Find all pairs $(n,d)$ of positive integers such that $d\mid n^2$ and $(n-d)^2<2d$. Linus Tang Note that $d|(n-d)^2$. So $(n-d)^2=0$ or $(n-d)^2=d$. In first case we get $n=d$, which works. In second case for some $k \in \mathbb{Z^+}$ holds $d=k^2$ and $k=|n-d|=|n-k^2|$. So $n=k^2+k$ or $n=k^2-k$. Answer: $(d,n)=(k,k); (k^2, k^2+k); (k^2, k^2-k)$ for some $k \in \mathbb{Z^+}$ (in last case also $k>1$). All cases are works.
23.06.2024 14:31
IAmTheHazard wrote: Find all pairs $(n,d)$ of positive integers such that $d\mid n^2$ and $(n-d)^2<2d$. Linus Tang Let $(d,n)=x$ and $d=xa$,$n=mx$ then we have that: $xa|m^2x^2$ and $x^2(m-a)^2<2ax$ since $(a,m)=1$ we get that: $a|x$ and $x(m-a)^2<2a$ If $a\neq x\Rightarrow a\leqslant \frac{x}{2}$ contradiction to inequaliti unless $m=a$ and becuse $(a,m)=1$ we get that $a=m=1$ and so $d=n$ So $a=x$ and we get that $(m-a)^2<2$ Which gives:$(d,n)=(k,k); (k^2, k^2+k); (k^2, k^2-k)$
24.06.2024 00:10
Trivially $(n,d)=(k, k)$ works, now suppoose $n \ne d$ then $(n-d)^2>0$, so we have $d \mid (n-d)^2$ which in fact from $2d>(n-d)^2$ this implies that $d=(n-d)^2$ which is $d^2-(2n+1)d+n^2=0$, and by quadratic formula we get $d=\frac{2n+1 \pm \sqrt{4n+1}}{2}$, now this clearly means $n=k^2+k$ (since odd squares are $1 \pmod 4$) so we get $d=k^2$ or $d=(k+1)^2$. Therefore all duples are $(n,d)=(k,k), (k^2+k, k^2), (k^2+k, (k+1)^2)$ thus we are done .
24.06.2024 06:12
The answer is $(n,d) = (x^2 + x,x^2), (x,x), (x^2 + x, (x+1)^2 ) $ for any positive integer $x$. These clearly work. Now we prove they are the only solutions. Assume $n \ne d$ since $n = d$ clearly works. Let $d = a^2 b$, where $a, b \in \mathbb N$ and $b$ is squarefree. We have $a^2 b \mid n^2$, so $ab\mid n$. But then $ab\mid |n-d|$, so $|n-d| \ge ab$, meaning that $(ab)^2 < 2d$, so $db < 2d \implies b < 2 \implies b = 1$, so $d = a^2$. Now if $|n-d| = k\cdot a$, then $(n-d)^2 = k^2 a^2$, but this must be less than $2a^2$, so $k^2 < 2 \implies k\in \{-1,1\}$, so $n \in \{d - a, d + a\}$. If $n = d-a$, then $n = a^2 - a\implies a > 1$. Now if $x = a - 1$, we have $n = x^2 + x$ and $d = (x+1)^2$, giving the desired solution. If $n = d + a$, then $n = a^2 + a, d = a^2$, so setting $x = a$ gives the desired solution.
06.08.2024 16:13
$n = d$ clearly works, so assume $n \neq d$. Note that $d \mid n^2 \implies d \mid (n - d)^2$. Since $0 < (n - d)^2 < 2d$, we have $(n - d)^2 = d$. This means $d$ is a perfect square, so let $d = k^2$. $(n - d)^2 = d \implies n = k^2 - k$ (where $k \neq 1$) or $n = k^2 + k$. Clearly, these both work, so we are done.