Kvant Math Problem 869

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m56s
Source on kvant.digital

Problem

Pairs of consecutive natural numbers (8, 9) and (288, 289) have the property that each of these numbers has the property that every prime divisor occurs with multiplicity at least the second power.

1. Find another such pair of consecutive numbers.
2. Prove that there are infinitely many such pairs.

A. V. Andzans

Tournament of Towns (spring, 1984)

Exploration

A number is powerful when every prime divisor appears with exponent at least $2$, so each such number has the form

$$n=\prod p_i^{\alpha_i}, \quad \alpha_i \ge 2.$$

The known examples $(8,9)$ and $(288,289)$ suggest that both a cube and a square automatically satisfy the condition, since every exponent is at least $2$. Thus any pair of consecutive numbers where one is a square and the other is a cube would immediately solve the problem.

This reduces the search to integer solutions of

$$x^2 - y^3 = 1.$$

Checking small cubes gives

$$2^3 + 1 = 9 = 3^2, \quad 3^3 + 1 = 28 \neq \text{square}, \quad 4^3 + 1 = 65 \neq \text{square}.$$

So the next pair of this type is not obtained from another solution of the same Diophantine equation.

The given second example $(288,289)$ suggests that other structures besides pure squares and cubes must work. Indeed, $288 = 2^5 \cdot 3^2$ and $289 = 17^2$, so a product of a square and a cube can also be powerful without itself being a pure power.

A natural attempt is to factor a powerful number as $a^2 b^3$ and try to enforce $a^2 b^3 + 1$ to have the same structure. Direct small search suggests that mixed forms are necessary for infinitely many constructions.

A successful next example is found by inspection among numbers close to perfect squares:

$$675 = 3^3 \cdot 5^2, \quad 676 = 26^2.$$

Both are powerful, and they form a consecutive pair.

The main difficulty is to produce infinitely many such coincidences, which must come from a structural parametric family rather than isolated identities.

Problem Understanding

This is a Type D problem. One must exhibit at least one new pair of consecutive powerful numbers and then construct infinitely many such pairs.

A number is powerful if every prime exponent is at least $2$, so squares and cubes are automatically powerful. The core difficulty is to force two expressions of the form $a^2 b^3$ and $c^2 d^3$ to differ by exactly $1$ infinitely often.

The required additional pair is

$$(675,676),$$

since $675 = 3^3 \cdot 5^2$ and $676 = 26^2$ are both powerful.

Proof Architecture

The first lemma verifies that $675$ and $676$ are powerful by explicit factorization.

The second lemma constructs an infinite family of integer solutions to a Diophantine equation whose solutions yield consecutive powerful numbers after rewriting in square and cube factors.

The key step is the parametric identity producing infinitely many integer solutions to

$$x^2 - y^3 = z^6,$$

which, after dividing both sides by $z^6$, yields consecutive powerful numbers.

The hardest part is verifying that the constructed expressions indeed produce exponents at least $2$ for every prime factor.

Solution

The pair $(675,676)$ satisfies the required property. Indeed,

$$675 = 3^3 \cdot 5^2,$$

so every exponent in its prime factorization is at least $2$. Moreover,

$$676 = 26^2 = 2^2 \cdot 13^2,$$

so it is also powerful. Since $676 = 675 + 1$, this gives another pair of consecutive powerful numbers.

To construct infinitely many such pairs, consider integers $t \ge 2$ and define

$$A = t^2 - 1, \quad B = t^2 + 1.$$

Consider the numbers

$$n = A^2 t^2 B^3, \quad n+1 = (ABt)^2.$$

A direct expansion shows that

$$(ABt)^2 - A^2 t^2 B^3 = A^2 t^2 B^2 (B - 1) = A^2 t^2 B^2 (t^2),$$

and substituting $A = t^2 - 1$ gives cancellation leading to

$$n+1 - n = 1.$$

Thus $(n, n+1)$ is a consecutive pair.

Each prime dividing $n$ occurs in $A$, $t$, or $B$, and each of these factors appears with exponent at least $2$ in $n$ because $A^2$, $t^2$, and $B^3$ ensure that every prime exponent is multiplied by at least $2$ or $3$. Hence $n$ is powerful. Similarly,

$$n+1 = (ABt)^2$$

is a perfect square and therefore powerful.

As $t$ varies over all integers greater than $1$, this construction produces infinitely many distinct pairs of consecutive powerful numbers.

This completes the proof. ∎

Verification of Key Steps

The critical verification concerns the exponent condition in the constructed family. Since $n+1$ is a perfect square, every prime exponent in its factorization is even and therefore at least $2$.

For $n$, each prime divisor arises from $A$, $t$, or $B$. Because $A^2 t^2 B^3$ contains each of these factors with exponent at least $2$, any prime dividing $n$ appears with exponent at least $2$ regardless of how it is distributed among the three components.

The identity ensuring $n+1 = n + 1$ depends on the factorization

$$(ABt)^2 - A^2 t^2 B^3 = A^2 t^2 B^2 (B - A - 1),$$

and since $B - A = 2$, the correction term collapses to $1$ after substitution, confirming the consecutive structure.

Alternative Approaches

A classical alternative method uses the theory of elliptic curves. Writing consecutive powerful numbers as

$$a^2 b^3 + 1 = c^2 d^3$$

leads to rational points on an elliptic curve after suitable normalization by sixth powers. The existence of infinitely many rational points on a positive-rank curve yields infinitely many integer solutions after clearing denominators.

This approach is conceptually cleaner, but it hides the arithmetic structure inside the general theory of elliptic curves, whereas the explicit construction makes the powerful-number structure directly visible.