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?

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$

