Find all numbers $n$ that consist of three digits, so that $n^2$ satisfies two specified conditions

alternative-proofcontest-mathdiophantine equationsproof-writingsolution-verification

The following was a question in the final of the Flanders Mathematics Olympiad 2018:

Find all numbers $n$ that consist of three digits, so that $n^2$ consists of six digits and the sum of the number formed by the three first digits and the number formed by the three last digits of $n^2$, equals $n$.

Points are assigned not only for finding the right answer, but also for formulating a rigorous and mathematically sound proof. To solve this question, I used the following reasoning:

Call $x, y$ the number formed by the first and the last three digits of $n^2$, respectively. Then, we find:

$$
\begin{cases}
n^2 = 1000 x + y \iff y = n^2 – 1000x\\
n = x + y \iff y = n – x
\end{cases}
\Rightarrow
n^2 – n = n (n – 1) = 999 x
$$

In order for $n (n – 1)$ to be a multiple of $999 = 3^3 \cdot 37$, either:

  1. $n = 27 \cdot 37 = 999, n – 1 = 998, x = 998$
  2. $n = 27 k, n – 1 = 37 l, x = k \cdot l, k, l \in \mathbb{N}$
  3. $n = 37 k, n – 1 = 27 l, x = k \cdot l, k, l \in \mathbb{N}$
  4. $n = 1000, n – 1 = 27 \cdot 37 = 999, x = 1000$

The first case corresponds to a valid solution, while the last one does not. Solving the Diophantine equations using the extended Euclidean algorithm (details not presented), we find:

$$27 k = 37l + 1, k < 37 \iff k = 11, l = 8, x = 88$$

$$37 k = 27l + 1, k < 27 \iff k = 19, l = 26, x = 494$$

Since $x$ must consist of three digits, only the last equation results in a valid solution. We thus find two solutions to the problem: $n = 703$ and $n = 999$.

It seems to me that this approach is quite tedious, and that there might be a more straightforward way to tackle this problem. Especially the use of Diophantine equations worries me, since this is not usually taught at high school level. Are there any alternative approaches to solve this question?

Best Answer

The approach you've shown seems very feasible for a high school olympiad, and is likely the intended method. An alternative method, though quite similar, would be to solve $$1000x+y=n^2=(x+y)^2=x^2+2xy+y^2.$$ This is a quadratic in $x$, which immediately shows that $$x=500-y\pm\sqrt{500^2-999y},\tag{1}$$ and for this to be an integer you must have $$500^2-999y=z^2\qquad\text{ or equivalently }\qquad 999y=(500+z)(500-z),$$ for some integers $y$ and $z$ with $0\leq z<500$.

This yields four cases, as in your proof:

  • Either $3^3\cdot37$ divides $500+z$; then $z=499$.
  • Or $3^3$ divides $500+z$ and $37$ divides $500-z$, which is impossible.
  • Or $37$ divides $500+z$ and $3^3$ divides $500-z$, in which case $z=203$
  • Or $3^3\cdot37$ divides $500-z$, which is impossible.

Pluggin these two values of $z$ back in shows that either $y=1$ or $y=209$, and correspondingly $x=998$ or $x=494$, where in both cases we have the $+$-sign in equation $(1)$ as $x$ must have three digits. It follows that either $n=999$ or $n=703$.

Related Question