# How prove this congruence equation has four zeros solution

Question:

let congruence equation $$\begin{cases} \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv \overline{a_{m}}(\mod 10)\\ \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv \overline{a_{m-1}a_{m}}(\mod 10^2)\\ \cdots\cdots\cdots\cdots\\ \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv \overline{a_{1}a_{2}\cdots a_{m}}(\mod 10^m) \end{cases}$$

show that: this congruence equation has $four$ zeros solution.

where $m\ge 2,a_{i}\in\{0,1,2,\cdots,9\}$

My try:

for example

when $m=2$ then $25$and $76$ ,$0,1$this four solution such

first $0$ and $1$ is such it

and $$25^2=625\equiv 5(\mod 10),76^2=5776\equiv 6(\mod 10)$$ $$25^2=625\equiv25(\mod 10^2),76^2=5776\equiv 76(\mod 10^2)$$ $$25^2=625\equiv 625(\mod 10^3),76^2=5776\equiv 776(\mod 10^3)$$

But My problem I can't prove it,Thank you very much!

-
@Ivan Loh,can you see this problem? This is nice number theory problem –  user94270 Dec 1 '13 at 14:49

As @Hurkyl pointed out, if we let $x=\overline{a_1a_2\ldots a_m}$, it suffices to prove that $x^2 \equiv x \pmod{10^m}$ has exactly four solutions $\pmod{10^m}$.

This is straightforward; we get $2^m(5^m)=10^m \mid x(x-1)$. Note that $\gcd(x, x-1)=1$, so we have four cases:

\begin{align} x \equiv 0 \pmod{2^m}, x \equiv 0 \pmod{5^m} \\ x \equiv 0 \pmod{2^m}, x \equiv 1 \pmod{5^m} \\ x \equiv 1 \pmod{2^m}, x \equiv 0 \pmod{5^m} \\ x \equiv 1 \pmod{2^m}, x \equiv 1 \pmod{5^m} \end{align}

For each case, Chinese Remainder Theorem ensures the existence of a unique solution for $x \pmod{10^m}$. We thus get exactly four solutions.

-

It will probably help to eschew digits and write it as an ordinary algebra problem: all of your equations are just

$$x^2 \equiv x \pmod{10^k}$$

Furthermore, you can eliminate all of the equations but the last one: any solution to

$$x^2 \equiv x \pmod{10^m}$$

will automatically be a solution to all of the others.

-