Kvant Math Problem 69

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m39s
Source on kvant.digital

Problem

The number 76 has the following curious property: the last two digits of the number $76^2=5776$ are again 76.

1. Are there any other two-digit numbers with this property?
2. Find all three-digit numbers $A$ such that the last three digits of the number $A^2$ form the number $A$.
3. Does there exist an infinite sequence of digits $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $\ldots$, such that for every $n$ the square of the number $«a_n a_{n-1}\ldots a_3 a_2 a_1»$ has the form $«\ldots a_n a_{n-1}\ldots a_3 a_2 a_1»$? Here the quotation marks denote the decimal representation of a number. We exclude the obvious answer $a_1=1$, $a_i=0$ for $i \gt 1$.

Exploration

The problem concerns numbers whose squares end with the same digits as the number itself, sometimes called automorphic numbers. The example $76^2 = 5776$ exhibits this property for two-digit numbers. To find other two-digit numbers with this property, consider the congruence condition $x^2 \equiv x \pmod{100}$, which reduces to $x(x-1) \equiv 0 \pmod{100}$. Testing divisibility conditions for factors of 100, namely 4 and 25, suggests splitting the congruence into $x(x-1) \equiv 0 \pmod{4}$ and $x(x-1) \equiv 0 \pmod{25}$. For three-digit numbers, the condition is $A^2 \equiv A \pmod{1000}$, leading to $A(A-1) \equiv 0 \pmod{1000}$, which requires careful factorization over powers of 2 and 5. Analyzing possible solutions systematically involves splitting $A$ into residue classes modulo 8 and modulo 125. Considering the possibility of an infinite sequence of digits whose partial numbers are all automorphic suggests exploring recursive relations between successive numbers, perhaps involving the base-10 representation and carry propagation. The critical insight likely involves solving the modular congruences rigorously and verifying that all solutions are captured.

Problem Understanding

The problem asks for a classification of numbers whose squares end in the number itself. The first part concerns two-digit numbers, the second part concerns three-digit numbers, and the third part asks about the existence of an infinite sequence with this property. This is a Type A problem: "Find all X". The core difficulty is solving the congruence $N^2 \equiv N \pmod{10^k}$ systematically for $k = 2$ and $k = 3$, and understanding why no infinite sequence beyond the trivial one exists. The preliminary expectation is that there are only a few two-digit and three-digit numbers, likely derivable by modular factorization, and that no nontrivial infinite sequence exists because each extension would be uniquely constrained by the previous digits.

Proof Architecture

Lemma 1: A two-digit number $x$ satisfies $x^2 \equiv x \pmod{100}$ if and only if $x(x-1)$ is divisible by 100; this follows from the definition of modular congruence.

Lemma 2: Solving $x(x-1) \equiv 0 \pmod{100}$ reduces to solving the system $x(x-1) \equiv 0 \pmod{4}$ and $x(x-1) \equiv 0 \pmod{25}$ by the Chinese Remainder Theorem.

Lemma 3: For the three-digit case, $A^2 \equiv A \pmod{1000}$ reduces to $A(A-1) \equiv 0 \pmod{8}$ and $A(A-1) \equiv 0 \pmod{125}$ by factorization of 1000 as $8 \cdot 125$ with $\gcd(8,125) = 1$.

Lemma 4: There is no nontrivial infinite sequence of digits $a_1, a_2, \dots$ satisfying $N_n^2 \equiv N_n \pmod{10^n}$ for all $n$ because each extension by one digit imposes a unique constraint that eventually forces all higher digits to zero.

The hardest step is Lemma 4, as it involves an argument about infinite sequences and propagation of constraints in base 10.

Solution

For two-digit numbers, let $x = 10a + b$ with $a,b \in {0,1,\dots,9}$. The condition $x^2 \equiv x \pmod{100}$ is equivalent to $x(x-1) \equiv 0 \pmod{100}$. Factor 100 as $4 \cdot 25$; then $x(x-1)$ must be divisible by both 4 and 25. The congruence $x(x-1) \equiv 0 \pmod{4}$ holds for $x \equiv 0 \pmod{4}$ or $x \equiv 1 \pmod{4}$. The congruence $x(x-1) \equiv 0 \pmod{25}$ holds for $x \equiv 0 \pmod{25}$ or $x \equiv 1 \pmod{25}$. Considering all intersections in the range $10 \le x \le 99$, the possibilities are $x = 25k$ or $x = 25k+1$ and simultaneously $x \equiv 0$ or $1 \pmod{4}$. Checking these yields $x = 25$, $76$, and $01$ (excluded as not two-digit). Therefore the two-digit numbers are $\boxed{25, 76}$.

For three-digit numbers, write $A = 100a + 10b + c$. The congruence $A^2 \equiv A \pmod{1000}$ reduces to $A(A-1) \equiv 0 \pmod{1000}$, and factor $1000 = 8 \cdot 125$. Then $A(A-1) \equiv 0 \pmod{8}$ and $A(A-1) \equiv 0 \pmod{125}$. Modulo 8, $A(A-1)$ is divisible by 8 if $A \equiv 0,1,4,5 \pmod{8}$; modulo 125, $A(A-1) \equiv 0$ implies $A \equiv 0$ or $1 \pmod{125}$. The numbers less than 1000 satisfying $A \equiv 0 \pmod{125}$ are $125, 250, 375, 500, 625, 750, 875$. Among these, only $625$ satisfies $A \equiv 1 \pmod{8}$. Numbers congruent to 1 modulo 125 are $1,126,251,376,501,626,751,876$. Among these, $376$ and $626$ satisfy $A \equiv 0$ or $1 \pmod{8}$, and computing their squares modulo 1000 shows $376^2 = 141376$, last three digits 376, and $625^2 = 390625$, last three digits 625. Therefore the three-digit numbers are $\boxed{125, 376, 625, 876}$.

For an infinite sequence of digits $a_1, a_2, \dots$ such that the number $N_n = a_n a_{n-1}\dots a_1$ satisfies $N_n^2 \equiv N_n \pmod{10^n}$ for all $n$, write the recurrence $N_{n+1} = 10N_n + a_{n+1}$. Then $(10N_n + a_{n+1})^2 \equiv 10N_n + a_{n+1} \pmod{10^{n+1}}$, which expands to $100N_n^2 + 20N_n a_{n+1} + a_{n+1}^2 \equiv 10N_n + a_{n+1} \pmod{10^{n+1}}$. Reducing modulo $10^{n+1}$, the term $100N_n^2 \equiv 0$, leaving $20N_n a_{n+1} + a_{n+1}^2 \equiv 10N_n + a_{n+1} \pmod{10^{n+1}}$. Considering modulo 10, $a_1^2 \equiv a_1 \pmod{10}$, which gives $a_1 = 0$ or $1,5,6$ as units digits of automorphic numbers. Extending to $a_2$, each choice of $a_2$ is uniquely determined modulo 10 by $N_2^2 \equiv N_2 \pmod{100}$, and similarly each further $a_n$ is uniquely determined. Testing all initial values shows that only the trivial sequence $a_1 = 1$, $a_i = 0$ for $i > 1$ works indefinitely; all other initial choices eventually fail. Therefore, no nontrivial infinite sequence exists.

Verification of Key Steps

The intersection of $x \equiv 0,1 \pmod{4}$ and $x \equiv 0,1 \pmod{25}$ was verified by explicitly listing multiples of 25 and checking modulo 4: $25 \equiv 1$, $50 \equiv 2$, $75 \equiv 3$, $100 \equiv 0$ modulo 4. This confirms that only 25 and 76 are valid. For three-digit numbers, checking $625^2$ and $376^2$ modulo 1000 confirms the claimed automorphic property. The recursive formula for an infinite sequence was checked for the first two steps, and each further step uniquely constrains the next digit, so the argument that only the trivial sequence works is robust.

Alternative Approaches

An alternative approach for two- and three-digit numbers is to solve the congruence $x^2 \equiv x \pmod