\section*{Problem 5 - 111245}

Determine all three-digit natural numbers \(x\), written in the decimal positional system, for which the following holds:

If one appends the digit sequence of the number \(x+1\) to the right of the digit sequence of the number \(x\), one obtains the digit sequence of a six-digit square number.
}

We denote the number that results from appending to \(x\) as \(y\). In the decimal system, \(x\) has the form \(a b c\), i.e., \(x=100 \cdot a+10 \cdot b+c\) with \(a, b, c \in\{0, \ldots, 9\}\). Additionally, \(a \neq 0\) since \(x\) should be a three-digit number, and \(x \neq 999\) since \(y\) should be a six-digit number.

It is

\[
y=\left(10^{3}+1\right)(100 \cdot a+10 \cdot b+c)+1=\left(10^{3}+1\right) x+1
\]

and this should always be equal to a square number \(n^{2}\) with \(n \in \mathbb{Z}\). Since \(10^{3}+1=7 \cdot 11 \cdot 13\) and \(7, 11, 13\) are prime numbers, it follows that \(n \equiv \pm 1 \bmod 7\), \(n \equiv \pm 1 \bmod 11\), and \(n \equiv \pm 1 \bmod 13\). This yields eight possible congruence systems modulo 7, 11, and 13 that \(n\) should satisfy.

Since 7, 11, and 13 are coprime, these congruence systems can be solved using the Chinese Remainder Theorem for integers (which can be quickly and elementarily proven and is therefore certainly usable in the Olympiad, as it is for class 12 and level 4).

According to the Chinese Remainder Theorem, \(n=\sum_{i=1}^{3} a_{i} e_{i}+k \cdot M\), where \(k\) is any integer and \(a_{i}\) represents the congruences (here 1 or -1). Additionally, \(e_{i}=s_{i} \cdot M_{i}\), with \(m_{1}=7\), \(m_{2}=11\), \(m_{3}=13\), and \(M=m_{1} \cdot m_{2} \cdot m_{3}\), \(M_{i}=M / m_{i}\). \(s_{i}\) is an integer derived from the extended Euclidean algorithm: Since \(m_{i}\) and \(M_{i}\) are coprime, there exist integers \(r_{i}, s_{i}\) such that \(r_{i} \cdot m_{i}+s_{i} \cdot M_{i}=1\). Using the extended Euclidean algorithm, we find \(\left(r_{1}, s_{1}\right)=(41,-2)\), \(\left(r_{2}, s_{2}\right)=(-33,4)\), \(\left(r_{3}, s_{3}\right)=(6,1)\) and obtain with the Chinese Remainder Theorem the solutions for \(n\) for the eight congruence systems to \(n \in\{1,-1,573,-573,727,-727,155,-155\}+7 \cdot 11 \cdot 13 \mathbb{Z}\).

Since \(10^{5}<n^{2}<10^{6}\), it follows that \(316<n<1000\) or \(-1000<n<-316\). Therefore, the only possible values for \(n\) are (remember \(7 \cdot 11 \cdot 13=1001\)): 573, \(-573+1001=428\), \(-155+1001=846\), 727 (here only the positive ones are listed).

Squaring yields \(y=328329\), \(y=183184\), \(y=715716\), \(y=528529\) and accordingly \(x=328\), \(x=183\), \(x=715\), \(x=528\), which are all the desired solutions.