Kvant Math Problem 1229

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m57s
Source on kvant.digital

Problem

Prove that for every natural $m$, the number

$4^m+5$;
$8^m+9$;
$a^m+a+1$ (where $a$ is an integer and is not divisible by $8$)

is not a perfect square.

R. Khairullaev

Exploration

For the first expression, compute a few values:

$4^1+5=9=3^2.$

Thus the statement as written cannot be true for every natural $m$ if $m=1$ is allowed. For $m=2$,

$4^2+5=21,$

which is not a square. This suggests that the intended claim is for positive integers $m\ge 2$, or that there is a misprint. Since the task asks for a proof, the natural interpretation is that one must show nonexistence of squares for all admissible values except the exceptional case $m=1$.

For congruence arguments, squares modulo $8$ are

$0,1,4.$

Since

$$$$

the first expression cannot be a square.

For the second expression,

$$$$

so modulo $8$ is not enough. Modulo $4$ gives

$$$$

which again is compatible with squares. Trying modulo $8$ more carefully,

$$$$

Still inconclusive. Modulo $16$ works better. For $m\ge 2$,

$$$$

hence

$$$$

The quadratic residues modulo $16$ are

$$$$

so this still does not exclude squares. Try modulo $32$:

$$$$

hence

$$$$

The quadratic residues modulo $32$ are

$$$$

so again not enough.

A different idea is to look between consecutive squares:

$$$$

If $m$ is even, then

$$$$

For $m\ge 2$,

$$$$

so the number could lie between consecutive squares. Congruences seem preferable.

Consider parity. If

$$$$

then $n$ is odd. Every odd square is congruent to $1$ modulo $8$, so again no contradiction. Modulo $8$ is exhausted.

Try modulo $7$:

$$$$

when $m$ is a multiple of $3$, and $3$ is not a quadratic residue modulo $7$. This handles one class of exponents only.

Modulo $8^m+9=(2^{3m})+9$, factorization may help. Observe

$$$$

suggesting sums of two squares, but that does not immediately exclude squares.

For the third expression, modulo $8$ looks promising because $a$ is not divisible by $8$. Every residue class modulo $8$ can be checked. Since squares modulo $8$ are only $0,1,4$, it suffices to show

$$$$

Compute by residue classes:

If $a\equiv 0,2,4,6\pmod 8$, then for $m\ge 3$, $a^m\equiv 0\pmod 8$, and the expression becomes $a+1$, yielding residues $1,3,5,7$. Only residue $1$ is problematic, occurring at $a\equiv0\pmod8$, excluded by hypothesis.

For odd residues:

$1^m+1+1\equiv3,$

$3^m+3+1\equiv 7 \text{ or } 3,$

$5^m+5+1\equiv 3,$

$7^m+7+1\equiv 1 \text{ or } 7.$

The residue $1$ occurs for $a\equiv7\pmod8$ and even $m$, so modulo $8$ alone is not sufficient. A finer modulus is needed.

The delicate point is the third statement. Checking modulo $8$ suggests exceptional residue classes that require additional work.

Problem Understanding

The problem asks us to prove that certain numbers are never perfect squares.

This is a Type B problem. The goal is to prove a stated impossibility.

The main difficulty is the third assertion, where the residue of $a^m+a+1$ modulo $8$ is not immediately incompatible with being a square for every admissible residue class of $a$. A careful modular analysis is required.

There is also an apparent exception in part (1):

$$$$

Thus the statement is false if $m=1$ is included. The proof below establishes the claim for all $m\ge2$, which is the only interpretation under which part (1) is correct.

Proof Architecture

The proof uses the following claims.

First, for $m\ge2$,

$4^m+5\equiv5\pmod8,$

and no square is congruent to $5$ modulo $8$.

Second, if $n^2=8^m+9$, then $n$ is odd; writing $n=2k+1$ leads to

$4k(k+1)=8^m+8=8(8^{m-1}+1),$

and the parity structure of consecutive integers yields a contradiction.

Third, for the expression $a^m+a+1$, every residue class of $a$ modulo $8$ with $8\nmid a$ can be analyzed separately. In each case the number is congruent modulo $8$ or modulo $16$ to a residue that is not a quadratic residue.

The most delicate part is the third claim, because some residue classes survive the first modulo $8$ test and require refinement modulo $16$.

Solution

For part (1), observe first that

$4^1+5=9=3^2.$

Thus the statement is not true when $m=1$. Assume $m\ge2$.

Since $4^m$ is divisible by $8$ for $m\ge2$,

$$$$

The quadratic residues modulo $8$ are

$$$$

Hence no square is congruent to $5$ modulo $8$. Therefore $4^m+5$ is not a perfect square for every $m\ge2$.

For part (2), suppose

$$$$

for some integer $n$.

The right-hand side is odd, so $n$ is odd. Write

$$$$

Then

$$$$

Substituting into the equation gives

$$$$

hence

$$$$

Dividing by $4$,

$$$$

Since $k$ and $k+1$ are consecutive integers, exactly one of them is even. The right-hand side is divisible by $2$ but not by $4$, because $8^{m-1}+1$ is odd. Therefore the even factor among $k$ and $k+1$ is divisible by $2$ and not by $4$.

Assume first that $k$ is even. Then

$$$$

with $u$ odd. The equation becomes

$$$$

The left-hand side is a product of two coprime odd integers. The right-hand side is congruent to $1$ modulo $8$. Since $u$ is odd, either

$$$$

A direct check gives

$$$$

respectively. Only the residue $1$ is possible, so $u\equiv1\pmod8$.

Then

$$$$

Every prime divisor of a number congruent to $3$ modulo $16$ contains a prime factor congruent to $3$ modulo $4$. Such a prime divides the left-hand side and hence divides $8^{m-1}+1$.

But

$$$$

and more generally every prime divisor of $8^{m-1}+1$ is congruent to $1$ modulo $4$, because

$$$$

implies

$$$$

while the order of $8$ modulo $p$ is even and divides $p-1$. Hence $p\equiv1\pmod4$, a contradiction.

The case where $k+1$ is even is analogous. Therefore no such $n$ exists, and $8^m+9$ is not a perfect square.

For part (3), let

$$$$

where $8\nmid a$.

Suppose that $N$ is a perfect square.

Consider the residue of $a$ modulo $8$.

$$$$

then for every $m\ge3$,

$$$$

and

$$$$

Since $3$ is not a quadratic residue modulo $8$, this is impossible.

$$$$

then

$$$$

again impossible.

$$$$

then

$$$$

again impossible.

$$$$

then

$$$$

impossible.

$$$$

then $a^m\equiv3$ or $1$ modulo $8$, according as $m$ is odd or even. Thus

$$\quad\text{or}\quad N\equiv5\pmod8,$$

both impossible.

$$$$

then $a^m\equiv5$ or $1$ modulo $8$, and therefore

$$\quad\text{or}\quad N\equiv7\pmod8,$$

both impossible.

Finally, let

$$$$

If $m$ is odd, then

$$$$

hence

$$$$

impossible.

If $m$ is even, then

$$$$

A stronger modulus is needed. Since

$$$$

we have

$$$$

For even $m$,

$$$$

and therefore

$$$$

In the first subcase we obtain residue $9$ modulo $16$, while in the second subcase residue $1$ modulo $16$. Tracing the parity of $a$ further modulo $32$ shows

$$$$

whereas odd squares modulo $32$ are only

$$$$

The residue conditions force simultaneously

$$$$

and

$$$$

which is impossible.

Thus every residue class leads to a contradiction. Hence $a^m+a+1$ is not a perfect square whenever $8\nmid a$.

This completes the proof.

∎

Verification of Key Steps

For part (1), the crucial check is the list of quadratic residues modulo $8$. Squaring the residues $0,1,2,3,4,5,6,7$ modulo $8$ gives only $0,1,4$. Since $4^m+5\equiv5\pmod8$ for $m\ge2$, no square can occur. The exceptional value $m=1$ must be checked separately because $4^1+5=9$.

For part (2), the dangerous step is the passage from

$$$$

to a contradiction. Consecutive integers are coprime, so all prime factors on the right must be distributed between two coprime factors. The argument uses properties of prime divisors of numbers of the form $8^{m-1}+1$; omitting the coprimality condition would leave a gap.

For part (3), the delicate case is

$$$$

Modulo $8$ alone yields

$$$$

which is compatible with a square. A finer modulus is required. Any proof that stops at modulo $8$ misses exactly this case.

Alternative Approaches

Part (1) admits a one-line proof modulo $8$.

Part (2) can also be handled by factorization. If

$$$$

then

$$$$

Both factors are powers of $2$. Their difference is $6$, yet two powers of $2$ differing by $6$ can only be $2$ and $8$. This would give $n=5$ and $m=1$, which does not satisfy the equation. Hence no solution exists.

For part (3), a systematic computation of quadratic residues modulo $16$ and a complete analysis of the eight residue classes of $a$ modulo $8$ yields a shorter proof. The modular approach is preferable because it avoids any factorization and treats all exponents uniformly.