Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer

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$
share|improve this answer
    
very clever, I like this approach with modular arithmetic! –  ray Sep 8 '12 at 21:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.