<s>[INST] Automorphic numbers 
Problem. We say that the $n$-digit number $x$ is automorphic iff $x^2\equiv x \mod(10^n)$. Prove that if $x$ is $n$-digit automorphic number then $(3x^2-2x^3)\mod(10^{2n})$ is $2n$-digit automorphic number. Hint: use Chinese reminder theorem to find the necessary and sufficient condition for number to be automorphic.

So from Chinese reminder theorem we have that $x$ is automorphic iff: $$ \begin{cases} x(x-1)\equiv 0 \mod(2^n)\\ x(x-1)\equiv 0 \mod(5^n)\end{cases} $$ which gives us four systems of equations:
$$ \begin{cases} x\equiv 0 \mod(2^n)\\ x\equiv 0 \mod(5^n)\end{cases} $$
$$ \begin{cases} x\equiv 1 \mod(2^n)\\ x\equiv 1 \mod(5^n)\end{cases} $$
$$ \begin{cases} x\equiv 0 \mod(2^n)\\ x\equiv 1 \mod(5^n)\end{cases} $$
$$ \begin{cases} x\equiv 1 \mod(2^n)\\ x\equiv 0 \mod(5^n)\end{cases} $$
and it's easy to check that thesis is true for the first two cases, just by simple operations. But how to check the last two?
 [/INST] To do the computation with modular arithmetic instead of divisibility....
If $x \equiv 0 \pmod{2^n}$, then $x \equiv x_1 2^n \pmod{2^{2n}}$ for some integer $x_1$. Then,
$$ 3x^2 - 2x^3 \equiv 3 x_1^2 2^{2n} - 2 x_1^3 2^{3n} \equiv 0 \pmod{2^{2n}}$$
Similarly, in the case of $x \equiv 1 + x_1 2^n \pmod{2^{2n}}$, then,
$$ \begin{align*} 3x^2 - 2x^3 &\equiv 3(1 + x_1 2^n)^2 - 2(1 + x_1 2^n)^3
\\& \equiv 3(1 + 2 x_1 2^n) - 2(1 + 3 x_1 2^n)
\\&\equiv 1  &\pmod{2^{2n}}\end{align*}$$
where this time I didn't bother writing the higher powers of $2$ that would appear but vanish modulo $2^{2n}$.
You should be made aware of the similarity to differential approximation: in fact, for any polynomial function $f(x)$, we have
$$ f(x_0 + x_1 p^n) \equiv f(x_0) + x_1 f'(x_0) p^n \pmod{p^{2n}} $$
(this can be generalized to Taylor series too. If this is interesting, look up "$p$-adic analysis")
If one had known this fact, one could have quickly solved the problem by setting $f(x) = 3 x^2 - 2 x^3$ and observing:


*

*$f(0) = 0$

*$f(1) = 1$

*$f'(0) = f'(1) = 0$

</s>