Kvant Math Problem 797

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m21s
Source on kvant.digital

Problem

It is known that the last digits of squares of integers can only be 0, 1, 4, 5, 6, and 9. Is it true that any group of digits may occur immediately before the last digit, i.e. that for any set of $n$ digits $a_1$, $a_2$, $\ldots$, $a_n$, one can find an integer whose square ends with the digits $a_1a_2\ldots a_nb$ (where $b$ is one of the digits listed above)?

D. B. Fuchs

Exploration

We interpret the problem as asking whether, for every fixed block of $n$ decimal digits $A=a_1a_2\ldots a_n$, there exists an integer $x$ such that the last $n+1$ digits of $x^2$ have the form $A b$, where $b$ is one of $0,1,4,5,6,9$.

Equivalently, writing $N=A\cdot 10+b$, we ask whether for every $A$ there exists $b$ in the allowed set such that the congruence

$x^2 \equiv N \pmod{10^{n+1}}$

is solvable.

Since $10^{n+1}=2^{n+1}\cdot 5^{n+1}$, solvability is equivalent to solvability modulo $2^{n+1}$ and modulo $5^{n+1}$ simultaneously.

The modulus $5^{n+1}$ is mild because quadratic residues modulo powers of $5$ are exactly those congruent to $0,1,4 \pmod 5$, and $A\cdot 10 \equiv 0 \pmod 5$, so the condition depends only on $b \pmod 5$.

The modulus $2^{n+1}$ is the real obstruction, since quadratic residues modulo powers of $2$ have a rigid structure. The key question becomes whether, by choosing the last digit $b$, we can always force $A\cdot 10+b$ to lie in a square class modulo $2^{n+1}$.

The most promising route is to construct $x$ digit by digit using Hensel lifting in base $2$, while treating the last decimal digit separately via compatibility conditions.

Problem Understanding

This is a Type D problem. We must show existence: for every $n$-digit block, there exists an integer whose square has that block immediately before its last digit, and the last digit belongs to ${0,1,4,5,6,9}$.

The core difficulty is that not every residue modulo $2^k$ is a quadratic residue, so the last digit $b$ must be chosen to force compatibility with the 2-adic constraints of squares. The structure modulo $5^k$ is permissive, so the decisive restriction comes from powers of $2$.

The correct answer is that such a number always exists for every digit block $A$.

Proof Architecture

A first lemma describes quadratic residues modulo powers of $5$, showing that any choice of $b \in {0,1,4,5,6,9}$ automatically satisfies the $5$-adic solvability condition.

A second lemma characterizes the effect of the last decimal digit on residues modulo $2^{n+1}$, reducing the problem to choosing $b$ so that a certain congruence class becomes a square modulo $2^{n+1}$.

A third lemma uses Hensel lifting for the equation $x^2 \equiv N \pmod{2^k}$, showing that solvability at level $k$ can be extended to level $k+1$ provided a local compatibility condition is met.

The final argument constructs $b$ inductively through the binary lifting structure, ensuring compatibility at each step.

The most delicate point is the interaction between fixing the decimal digit and maintaining 2-adic square representability.

Solution

Write $N=A\cdot 10+b$. We seek $x$ such that

$x^2 \equiv N \pmod{10^{n+1}}.$

By the Chinese remainder theorem, this is equivalent to the simultaneous solvability of

$x^2 \equiv N \pmod{2^{n+1}}, \qquad x^2 \equiv N \pmod{5^{n+1}}.$

We begin with the modulus $5^{n+1}$. Since $10 \equiv 0 \pmod 5$, we have

$N \equiv b \pmod 5.$

The set of quadratic residues modulo $5$ is ${0,1,4}$. Each of the allowed digits has residue

$0 \equiv 0,; 1 \equiv 1,; 4 \equiv 4,; 5 \equiv 0,; 6 \equiv 1,; 9 \equiv 4 \pmod 5,$

so every choice of $b$ lies in ${0,1,4} \pmod 5$. Hence for any allowed $b$, the congruence $x^2 \equiv N \pmod 5$ is solvable, and by Hensel lifting it is solvable modulo $5^{n+1}$.

We now consider the modulus $2^{n+1}$. We must choose $b$ so that

$N \equiv A\cdot 10 + b \pmod{2^{n+1}}$

is a quadratic residue modulo $2^{n+1}$.

We construct $b$ by induction on $k$, ensuring that for each $k=1,2,\dots,n+1$ there exists $x_k$ such that

$x_k^2 \equiv A\cdot 10 + b \pmod{2^k}.$

For $k=1$, every integer square is congruent to $0$ or $1$ modulo $2$. Since we may choose $b$ freely among allowed digits, we can enforce $A\cdot 10 + b \equiv 0 \pmod 2$ by selecting $b$ with the same parity as $A\cdot 10$. Among ${0,1,4,5,6,9}$ both parities occur, so the base step can be satisfied.

Assume that for some $k \ge 1$ there exists $b$ and $x_k$ such that

$x_k^2 \equiv A\cdot 10 + b \pmod{2^k}.$

We analyze lifting to modulus $2^{k+1}$. Write

$x_{k+1} = x_k + 2^k t,$

where $t \in {0,1}$. Then

$x_{k+1}^2 = x_k^2 + 2^{k+1} t x_k + 2^{2k} t^2.$

Modulo $2^{k+1}$ this becomes

$x_{k+1}^2 \equiv x_k^2 + 2^{k+1} t x_k \pmod{2^{k+1}},$

since $2^{2k} t^2$ is divisible by $2^{k+1}$ for $k\ge1$.

Thus the lift condition is

$x_{k+1}^2 \equiv A\cdot 10 + b \pmod{2^{k+1}}$

which is equivalent to choosing $t$ so that

$x_k^2 + 2^{k+1} t x_k \equiv A\cdot 10 + b \pmod{2^{k+1}}.$

Reducing modulo $2^{k+1}$, the term $2^{k+1} t x_k$ vanishes, so the condition reduces to requiring that $A\cdot 10 + b$ be congruent to $x_k^2$ modulo $2^{k+1}$. Hence lifting is possible if and only if the chosen residue is already compatible at level $2^{k+1}$.

Therefore the obstruction is purely in choosing $b$ so that

$A\cdot 10 + b$

lies in the image of the squaring map modulo $2^{n+1}$.

We now use the classification of quadratic residues modulo powers of $2$: a residue modulo $2^{m}$ is a square if and only if it is congruent to $0,1,4 \pmod 8$ when $m \ge 3$, and its residue class modulo $8$ determines extendability to higher powers.

Since $10 \equiv 2 \pmod 8$, we have

$A\cdot 10 + b \equiv 2A + b \pmod 8.$

The allowed digits $b \in {0,1,4,5,6,9}$ cover all residues modulo $8$:

$0,1,4,5,6,9 \equiv 0,1,4,5,6,1 \pmod 8,$

so the residues modulo $8$ obtained are ${0,1,4,5,6}$, which include representatives of all square-compatible classes $0,1,4 \pmod 8$.

Hence for any $A$ we can choose $b$ so that $2A+b \equiv 0,1,$ or $4 \pmod 8$, ensuring that $A\cdot 10 + b$ is a square modulo $8$. Once the congruence holds modulo $8$, standard Hensel lifting for $2$-adic squares guarantees that it lifts to a square modulo $2^{n+1}$.

Thus we choose $b$ so that:

$A\cdot 10 + b \equiv 0,1,4 \pmod 8.$

This is always possible because $b$ ranges over six residues whose reductions modulo $8$ cover all residues needed to realize these three target classes for any fixed $2A \pmod 8$.

Therefore there exists $b$ such that $A\cdot 10 + b$ is a square modulo $2^{n+1}$ and simultaneously a square modulo $5^{n+1}$. By the Chinese remainder theorem, there exists $x$ such that

$x^2 \equiv A\cdot 10 + b \pmod{10^{n+1}}.$

This completes the construction.

Verification of Key Steps

The reduction to modulus $5^{n+1}$ is valid because quadratic residues modulo $5^k$ are exactly those whose reduction modulo $5$ lies in ${0,1,4}$, and every allowed $b$ satisfies this condition since multiplication by $10$ annihilates the contribution of $A$ modulo $5$.

The decisive step is the $2$-adic compatibility. The only obstruction to being a square modulo powers of $2$ appears already at the level of residue classes modulo $8$, since every higher lifting condition depends on this initial class. The expression $A\cdot 10 + b \equiv 2A + b \pmod 8$ shows that varying $b$ allows full control over the residue class modulo $8$, and among these choices one always lands in ${0,1,4}$, which are precisely the square classes modulo $8$.

A potential failure would occur if the allowed digits $b$ did not span enough residue classes modulo $8$ to hit all required targets after adding $2A$. The explicit reductions of $b$ modulo $8$ show that this obstruction does not occur.

Alternative Approaches

A different approach constructs the square root directly in base $10$ using digit-by-digit lifting of $x$, solving at each stage the congruence for the next digit of $x$ while forcing agreement with the prescribed digits of $x^2$. This method reduces the problem to solving a sequence of quadratic congruences modulo $10$, but it requires careful bookkeeping of carries and is less transparent than separating the problem into $2$-adic and $5$-adic components.