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?
 A: (3)If $x≡0\pmod{2^n}=a2^n$  for some integer $a$
$3x^2-2x^3=3(a2^n)^2-2(a2^n)^3$ is clearly divisible by $2^{2n}$ 
Here $x≡1\pmod{5^n}=(b5^n+1)$ for some integer $b$
$3x^2-2x^3=3(b5^n+1)^2-2(b5^n+1)^3=(b5^n+1)^2(3-2(b5^n+1))$
$≡(1+2b5^n+b^25^{2n})(1-2b5^n)≡(1+2b5^n)(1-2b5^n)=1-4b^25^{2n}≡1\pmod{5^{2n}}$
(4)If $x≡0\pmod{5^n}=c5^n$  for some integer $c$
$3x^2-2x^3=3(c5^n)^2-2(c5^n)^3$ is clearly divisible by $5^{2n}$ 
Here $x≡1\pmod{2^n}=(d2^n+1)$ for some integer $d$
$3x^2-2x^3=3(d2^n+1)^2-2(d2^n+1)^3=(d2^n+1)^2(3-2(d2^n+1))$
$≡(1+2d2^n)(1-2d2^n)=1-4b^22^{2n}≡1\pmod{2^{2n}}$
Alternatively, if $x=ma+b$  where $0 ≤b<m$ So,$x≡b\pmod {m}≡b\pmod {m^2}$,
$3x^2-2x^3=3(ma+b)^2-2(ma+b)^3≡3b^2-2b^3-6mab(b-1)\pmod {m^2}$
If  $3b^2-2b^3-6mab(1-b)≡b\pmod {m^2}$
$m^2\mid 2b^3-3b^2+b+6mab(b-1)$ 
$m^2\mid b(b-1)(2b-1+6ma)$ 
Clearly two of the three solutions are $b=0,1\pmod {m^2}$
$\implies$ 
if $x=ma,m^2\mid(3x^2-2x^3)$
if $x=ma+1≡1\pmod {m}, 3x^2-2x^3≡1\pmod {m^2}$
A: It is the special case $\rm\ c=10,\ \,g(x) = 0\ $ of the following, where $\rm\ c,x,z\in\Bbb Z,\ \, c\ne \pm 1.$
Theorem $\rm\ \ c^n|\:x^2\!-\!x\:\Rightarrow\:c^{2n}|\:z^2\!-\!z,\ \ z = x^2 f(x),\ \ f(x) = 3\! -\! 2x + (x\!-\!1)^2 g(x),\ \ g(x)\in \Bbb Z[x]$ 
Proof $\rm\,\ \ c^n|\:x(x\!-\!1)\:\Rightarrow\: c^n|\:x\ \ or\ \ c^n|\:x\!-\!1\:$ by $\rm\:(x,x\!-\!1) = 1.\:$ $\rm\:c^n|\:x\:\Rightarrow\:c^{2n}|\:x^2\:|\:x^2f=z\:|\:z^2\!-\!z.\:$ Otherwise $\rm\:c^n|\:x\!-\!1\:\Rightarrow\:c^{2n}|\:(x\!-\!1)^2|\:z\!-\!1\:$ since
$$\rm z-1\ =\ {-}1 + x^2 (3-2x+(x-1)^2 g(x))\ =\ (x-1)^2 (-1 - 2x + x^2 g(x)) $$
Remark $\ $ The form of $\rm\,f(x)\,$ follows from the requirement that $\rm\: y = z\!-\!1 = x^2f(x)-1\,\:$ is divisible by $\rm\:(x\!-\!1)^2,\:$ which is true iff $\rm\:y(1) = 0 = y'(1).\: $ Thus $\rm\:y'(1) = 0\:\Rightarrow\:f(1) = 1,\:$ and $\rm\:y'(1) = 0\:$ implies $\rm\:2\,f(1) + f'(1) = 0,\:$ so $\rm\:f'(1) = -2\, f(1) = -2.\:$ Therefore, applying Taylor's formula yields $\rm\:f(x)\, =\, f(1) + f'(1)\,(x\!-\!1) + (x\!-\!1)^2g(x) =\, 3- 2x + (x\!-\!1)^2 g(x).$ 
A: 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$

A: Since $x$ and $x-1$ are coprime, it is true that $x(x-1)$ can only be a multiple of $p^n$ if and only if either $x$ or $x-1$ is one.
But then,
if $x \equiv 0 \mod m$, then $3x^2-2x^3 = (3-2x)x^2 \equiv 0 \mod m^2$  ,
and if $x \equiv 1 \mod m$, then $3x^2-2x^3 = 1-(1+2x)(x-1)^2 \equiv 1 \mod m^2$  
You should work on those congruences separately from each other and keep things simple. Unless you undo the work of the chinese theorem and think "well if $x \equiv 0 \mod 2^n$ and $5^n$ then $x \equiv 0 \mod 10^n$ and then I will do some computation and prove the result" (which is making everything complicated again), there shouldn't be any difficulty in the last two caes compared to the first two.
