I don't understand a part of the solution involving Chinese remainder theorem This is the problem statement:
Prove there are infinitely many natural numbers $x = \overline{a_{k}a_{k-1}...a_{2}a_{1}}$,  (where $a_{k} \neq 0$) such that $x$ and $x^2$ have the same k-digit ending.
This is their solution:
We deduct from $x \equiv x^2\: (mod \:{10^k})$, that $10^k| x^2-x = x(x-1)$. We also have $x < 10^k$. Now it is enough to find $x\in\{0, 1, ..., 10^k-1 \} $ such that $2^k|x$ and $5^k|x-1$. According to the Chinese remainder theorem, $x$ exists for any $k \in{\mathbb{N}}$. Moreover, every one of those numbers $x$ can be obtained only for a finite number of values of $k$, so there is an infinite amount of numbers $x$.
What I don't understand:
I can't understand the usage of the CRT here. Also, shouldn't $x$ be limited to $S = \{10^{k-1}, ... 10^k-1\}$, since we have $a_{k} \neq 0$? How can we assure that the CRT gives us a number from that belongs to $S$?
 A: To use the Chinese remainder, we rewrite $2^k \mid x$ and $5^k \mid x-1$ as
$$
  \begin{cases}
      x \equiv 0 \pmod {2^k} \\
      x \equiv 1 \pmod {5^k}
  \end{cases}
$$
which is a system of equations to which the Chinese remainder theorem applies; it tells us that there is a unique $x$ modulo $10^k$ (and therefore a unique $x$ in the set $\{0, 1, \dots, 10^k - 1\}$) which solves the system of equations.
You are right to be concerned that we might get $x < 10^{k-1}$ from the Chinese remainder theorem. In fact, we do get such $x$ occasionally: when $k=5$, we get $x = 09376$. I think that the claim "every one of those numbers $x$ can be obtained only for a finite number of values of $k$" is trying to address this problem, but it needs more detail.
Taking the last $k-1$ digits of a $k$-digit solution always gives us the $(k-1)$-digit solution. So in cases where the $k$-digit solution has a leading $0$, it is equal to the $(k-1)$-digit solution.
However, the sequence $x_1, x_2, x_3, \dots$ where $x_k$ is the $k$-digit solution must have infinitely many different values, because any particular value $x>1$ only works for finitely many $k$. (There are only finitely many digits in which $x$ agrees with $x^2$, because $x \ne x^2$.) So there are infinitely many $k$ for which $x_k \ne x_{k-1}$. Every such $k$ gives us a solution in which the leading digit is not $0$.

We can actually say more. The solutions found in this problem are only half of the possible solutions; the entire list is in the OEIS sequence A003226. For each $k$, there is also another solution: $y = 10^k + 1 - x$, which satisfies
$$
  \begin{cases}
      y = 10^k + 1 - x \equiv 1 \pmod {2^k} \\
      y = 10^k + 1 - x \equiv 0 \pmod {5^k}
  \end{cases}
$$
and therefore $10^k \mid y^2-y$ just like for $x$. If $x$ has a leading digit of $0$, then $y$ has a leading digit of $9$, and we get a $k$-digit solution anyway. (Often, $x$ and $y$ are both valid solutions.)
For example, when the original set of equations for $k=5$ gives us $x =09376$, which has a leading $0$, then we can take $y = 100001 - 09376 = 90625$, which is also a solution: $90625^2 = 8212890625$.
