TAOCP 4.3.2 Exercise 13

Section 4.3.2: Modular Arithmetic

Exercise 13. ▶ [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 $n$-digit number $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: 45m39s

Solution

(a)

An $n$-digit decimal number $x>1$ is an automorph iff $x^2 \equiv x \pmod{10^n}$.
Since $10^n = 2^n \cdot 5^n$ and $\gcd(2^n,5^n)=1$, this congruence is equivalent to the system [ x^2 \equiv x \pmod{2^n}, \qquad x^2 \equiv x \pmod{5^n}. ] Each congruence factors as $x(x-1)\equiv 0 \pmod{p^n}$ for $p=2,5$. Because $x$ and $x-1$ are consecutive integers, they are coprime. Hence a product $x(x-1)$ is divisible by $p^n$ exactly when one of the factors is divisible by $p^n$. Thus for each prime power we must have either $x\equiv 0 \pmod{p^n}$ or $x\equiv 1 \pmod{p^n}$. The four combinations are: \begin{align*} &x\equiv 0 \pmod{2^n},; x\equiv 0 \pmod{5^n} &&\Longrightarrow; x\equiv 0 \pmod{10^n},\ &x\equiv 1 \pmod{2^n},; x\equiv 1 \pmod{5^n} &&\Longrightarrow; x\equiv 1 \pmod{10^n},\ &x\equiv 1 \pmod{2^n},; x\equiv 0 \pmod{5^n},\ &x\equiv 0 \pmod{2^n},; x\equiv 1 \pmod{5^n}. \end{align*} The first gives $x=10^n k$; the only positive $n$-digit candidate is $10^n$, which has $n+1$ digits, and $x=0$ is excluded by $x>1$. The second gives $x=10^n k+1$; the smallest positive is $1$ (excluded) and the next is $10^n+1$ (also $n+1$ digits). The remaining two systems each have a unique solution modulo $10^n$ by the Chinese Remainder Theorem (Theorem C). These are precisely the numbers $M_1$ and $M_2$ defined in (7) with $m_1=2^n$, $m_2=5^n$, i.e. [ M_1\equiv 1 \pmod{2^n},; M_1\equiv 0 \pmod{5^n};\qquad M_2\equiv 0 \pmod{2^n},; M_2\equiv 1 \pmod{5^n}. ] Both satisfy $M_i^2\equiv M_i\pmod{10^n}$ and $M_i\not\equiv 0,1\pmod{10^n}$, so they are the only two nontrivial automorphs modulo $10^n$. Since an $n$-digit automorph must satisfy the congruence and lie in $[10^{n-1},10^n-1]$, it must be one of these two residues (the ones that fall in that range). This completes the proof. ∎

(b)

Let $x$ be an $n$-digit automorph, so $x^2 = x + k\cdot 10^n$ for some integer $k$. Define [ y = (3x^2 - 2x^3) \bmod 10^{2n}. ] We show that $y^2 \equiv y \pmod{10^{2n}}$ and $y\not\equiv 0,1\pmod{10^{2n}}$, making $y$ a $2n$-digit automorph.

Substitute $x^2 = x + k10^n$ into the expression for $y$: \begin{align*} 3x^2 - 2x^3 &= 3(x + k10^n) - 2x(x + k10^n) \ &= 3x + 3k10^n - 2x^2 - 2k x10^n \ &= 3x + 3k10^n - 2(x + k10^n) - 2k x10^n \ &= x + k10^n - 2k x10^n \ &= x + 10^n d, \end{align*} where $d = k(1-2x)$. Hence $y \equiv x + 10^n d \pmod{10^{2n}}$. Now compute $y^2 - y$: \begin{align*} y^2 &= x^2 + 2x\cdot 10^n d + 10^{2n}d^2 \ &= (x + k10^n) + 2x\cdot 10^n d + 10^{2n}d^2, \ y^2 - y &= (x + k10^n + 2x\cdot 10^n d + 10^{2n}d^2) - (x + 10^n d) \ &= 10^n(k + 2x d - d) + 10^{2n}d^2. \end{align*} Using $d = k(1-2x)$, \begin{align*} k + 2x d - d &= k + d(2x-1) \ &= k + k(1-2x)(2x-1) \ &= k - k(2x-1)^2 \ &= k\bigl[1 - (4x^2 - 4x + 1)\bigr] \ &= 4k(x - x^2). \end{align*} But $x - x^2 = -(x^2 - x) = -k10^n$, so [ k + 2x d - d = 4k(-k10^n) = -4k^2 10^n. ] Therefore [ y^2 - y = 10^n(-4k^2 10^n) + 10^{2n}d^2 = 10^{2n}(-4k^2 + d^2) \equiv 0 \pmod{10^{2n}}. ] Thus $y^2 \equiv y \pmod{10^{2n}}$.

Because $x$ is an $n$-digit automorph, $x\not\equiv 0,1\pmod{10^n}$. Since $y \equiv x \pmod{10^n}$, we also have $y\not\equiv 0,1\pmod{10^n}$, and consequently $y\not\equiv 0,1\pmod{10^{2n}}$. Hence $y$ is a nontrivial solution of $t^2\equiv t\pmod{10^{2n}}$, i.e. a $2n$-digit automorph. This completes the proof. ∎

(c)

We are given integers $c,x,y$ with $y>0$ such that $cx \equiv 1 \pmod{y}$. Write $cx = 1 + ky$ for some integer $k$. Consider [ c' = c^2(3 - 2cx). ] Then \begin{align*} c'x^2 &= c^2x^2(3 - 2cx) \ &= (cx)^2(3 - 2cx) \ &= (1+ky)^2\bigl(3 - 2(1+ky)\bigr) \ &= (1+2ky + k^2y^2)(1 - 2ky) \ &= 1 + 2ky + k^2y^2 - 2ky - 4k^2y^2 - 2k^3y^3 \ &= 1 - 3k^2y^2 - 2k^3y^3 \ &\equiv 1 \pmod{y^2}. \end{align*} The formula $c' = c^2(3 - 2cx)$ depends only on $c$ and $x$, not on $y$. This completes the proof. ∎

\boxed{c' = c^2(3 - 2cx)}