Automorphic numbers

Question

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?

Answer 1

(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}$

Answer 2

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.

Answer 3

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).$

Answer 4

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$