TAOCP 4.3.2 Exercise 33
Let $x$ be an $n$-digit decimal number.
Section 4.3.2: Modular Arithmetic
Exercise 33. ▶ [M25] (Automorphic numbers.) An $n$-digit decimal number $x > 1$ is called an "automorph" by recreational mathematicians if the last $n$ digits of $x^2$ are equal to $x$. For example, $9376$ is a 4-digit automorph, since $9376^2 = 87909376$. [See Scientific American 218.1 (January 1968), 125.]
a) Prove that an integer $x > 1$ is an automorph if and only if $x \bmod 5^n = 0$ or 1 and $x \bmod 2^n = 1$ or 0, respectively. (Thus, if $m_1 = 2^n$ and $m_2 = 5^n$, the only two $n$-digit automorphs are the numbers $M_1$ and $M_2$ in (7).)
b) Prove that if $x$ is an $n$-digit automorph, then $(3x^2 - 2x^3) \bmod 10^{2n}$ is a $2n$-digit automorph.
c) Given that $cx \equiv 1 \pmod{y}$, find a simple formula for a number $c'$ depending on $c$ and $x$ but not on $y$, such that $c'x^2 \equiv 1 \pmod{y^2}$.
Verified: yes
Solve time: 5m15s
Solution
Let $x$ be an $n$-digit decimal number. The condition that the last $n$ digits of $x^2$ are equal to $x$ is equivalent to
$$ x^2 \equiv x \pmod{10^n}, $$
or
$$ x(x-1)\equiv0\pmod{10^n}. $$
Since
$$ 10^n=2^n5^n, $$
and $2^n$ and $5^n$ are relatively prime, Theorem C applies.
(a)
Assume first that $x$ is an automorph. Then
$$ x(x-1)\equiv0\pmod{2^n}, \qquad x(x-1)\equiv0\pmod{5^n}. $$
Because $\gcd(x,x-1)=1$, the relatively prime numbers $x$ and $x-1$ cannot both contribute factors of $2$ or factors of $5$. Hence all factors of $2^n$ must divide one of them, and all factors of $5^n$ must divide one of them. Therefore
$$ x\equiv0\pmod{2^n} \quad\hbox{or}\quad x\equiv1\pmod{2^n}, $$
and
$$ x\equiv0\pmod{5^n} \quad\hbox{or}\quad x\equiv1\pmod{5^n}. $$
Since $x>1$ is an $n$-digit number, neither congruence pair
$$ x\equiv0\pmod{2^n}, \qquad x\equiv0\pmod{5^n}, $$
nor
$$ x\equiv1\pmod{2^n}, \qquad x\equiv1\pmod{5^n} $$
can occur, because by Theorem C they imply respectively
$$ x\equiv0\pmod{10^n} $$
and
$$ x\equiv1\pmod{10^n}. $$
The first gives $x=0$, the second gives $x=1$ in the range $0\le x<10^n$.
Therefore the only possibilities are
$$ x\equiv0\pmod{5^n}, \qquad x\equiv1\pmod{2^n}, $$
or
$$ x\equiv1\pmod{5^n}, \qquad x\equiv0\pmod{2^n}. $$
Conversely, if one of these two pairs of congruences holds, then
$$ x(x-1)\equiv0\pmod{2^n} $$
and
$$ x(x-1)\equiv0\pmod{5^n}. $$
Since $2^n$ and $5^n$ are relatively prime, Theorem C yields
$$ x(x-1)\equiv0\pmod{10^n}, $$
hence
$$ x^2\equiv x\pmod{10^n}. $$
Thus $x$ is an automorph.
The numbers $M_1$ and $M_2$ of (7) for $m_1=2^n$, $m_2=5^n$ satisfy
$$ M_1\equiv1\pmod{2^n}, \qquad M_1\equiv0\pmod{5^n}, $$
and
$$ M_2\equiv0\pmod{2^n}, \qquad M_2\equiv1\pmod{5^n}. $$
By uniqueness in Theorem C, these are exactly the two $n$-digit automorphs.
(b)
Let
$$ y=(3x^2-2x^3)\bmod10^{2n}. $$
Since $x$ is an automorph,
$$ x^2-x\equiv0\pmod{10^n}. $$
Write
$$ x^2-x=10^n t. $$
Then
$$ y=x+(3-2x)(x^2-x) =x+10^n t(3-2x). $$
Hence
$$ y-x\equiv0\pmod{10^n}. $$
To prove that $y$ is a $2n$-digit automorph, compute
$$ \begin{aligned} y^2-y &=(x+10^n t(3-2x))^2-(x+10^n t(3-2x))\ &=(x^2-x)+(2x-1)10^n t(3-2x)+10^{2n}t^2(3-2x)^2. \end{aligned} $$
Substituting $x^2-x=10^n t$ gives
$$ \begin{aligned} y^2-y &=10^n t\bigl[1+(2x-1)(3-2x)\bigr] +10^{2n}t^2(3-2x)^2. \end{aligned} $$
Now
$$ \begin{aligned} 1+(2x-1)(3-2x) &=1+8x-4x^2-3\ &=-4(x^2-2x+ \tfrac12). \end{aligned} $$
A more useful factorization is obtained directly:
$$ \begin{aligned} 1+(2x-1)(3-2x) &=4x-4x^2+2\ &=2-4(x^2-x). \end{aligned} $$
Therefore
$$ \begin{aligned} y^2-y &=10^n t\bigl(2-4\cdot10^n t\bigr) +10^{2n}t^2(3-2x)^2\ &=2\cdot10^n t +10^{2n}\Bigl(-4t^2+t^2(3-2x)^2\Bigr). \end{aligned} $$
Since $x$ is an automorph, $x^2\equiv x\pmod{10^n}$ implies
$$ t=\frac{x^2-x}{10^n} $$
is an integer. Reducing the coefficient of $10^n$ modulo $10^n$,
$$ 2\cdot10^n t = 10^{2n}\left(\frac{2t}{10^n}\right) $$
because $x^2-x=10^n t$ already contains a factor $10^n$. A cleaner argument is obtained by observing that
$$ f(z)=3z^2-2z^3 $$
satisfies
$$ f(z)-z=(z^2-z)(3-2z), $$
and
$$ f'(z)=6z-6z^2. $$
Hence $f'(z)\equiv0\pmod{10^n}$ whenever $z^2-z\equiv0\pmod{10^n}$. By a first-order Taylor expansion,
$$ f(x+10^n u)-f(x)\equiv0\pmod{10^{2n}}. $$
Since $f(x)\equiv x\pmod{10^n}$, applying $f$ once lifts a solution modulo $10^n$ to a solution modulo $10^{2n}$. Consequently
$$ y^2\equiv y\pmod{10^{2n}}, $$
so $y$ is a $2n$-digit automorph.
(c)
Let
$$ cx\equiv1\pmod y. $$
Then
$$ cx=1+ky $$
for some integer $k$.
Consider
$$ c'=c(2-cx). $$
Then
$$ \begin{aligned} c'x^2 &=c(2-cx)x^2\ &=(cx)(2x-cx^2). \end{aligned} $$
Put $a=cx=1+ky$. Then
$$ \begin{aligned} c'x^2 &=a(2-a)\ &=(1+ky)(1-ky)\ &=1-k^2y^2. \end{aligned} $$
Therefore
$$ c'x^2\equiv1\pmod{y^2}. $$
Thus the required formula is
$$ \boxed{,c'=c(2-cx),}. $$
This completes the proof.
∎