Kvant Math Problem 267

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m37s
Source on kvant.digital

Problem

In the sequence of triples of integers (2, 3, 5), (6, 15, 10), $\ldots$ each triple is obtained from the previous one as follows: the first number is multiplied by the second, the second by the third, and the third by the first, and the resulting products form the new triple.

Prove that none of the numbers obtained in this way will be a power of an integer: square, cube, etc.

F. A. Bartenev

Exploration

Let the $n$th triple be $(a_n,b_n,c_n)$, with

$$(a_0,b_0,c_0)=(2,3,5),$$

and

$$a_{n+1}=a_nb_n,\qquad b_{n+1}=b_nc_n,\qquad c_{n+1}=c_na_n.$$

Computing a few terms,

$$(2,3,5),\qquad (6,15,10),\qquad (90,150,60).$$

Every number occurring in the process is composed only of the primes $2,3,5$. It is natural to track the exponents of these primes. For example,

$$a_0=2^1 3^0 5^0,\qquad b_0=2^0 3^1 5^0,\qquad c_0=2^0 3^0 5^1.$$

If we write the exponent vector of a prime in the three positions, then one step sends

$$(x,y,z)\mapsto (x+y,;y+z,;z+x).$$

Thus the exponent vectors for $2,3,5$ evolve independently and all satisfy the same linear recurrence.

For the prime $2$, starting from $(1,0,0)$, we obtain

$$(1,0,0),\ (1,0,1),\ (1,1,2),\ (2,3,3),\dots$$

For the prime $3$, starting from $(0,1,0)$, we obtain

$$(0,1,0),\ (1,1,0),\ (2,1,1),\ (3,2,3),\dots$$

For the prime $5$, starting from $(0,0,1)$, we obtain

$$(0,1,1),\ (1,2,1),\ (3,3,2),\dots$$

A number is a perfect power $m^k$ with $k>1$ precisely when the exponents of all primes have a common divisor greater than $1$. Hence it suffices to show that in every entry of every triple, the exponents of $2,3,5$ have greatest common divisor $1$.

The exponents in a fixed position seem always to add up to the same quantity. For instance, in the first position:

$$(1,0,0),\ (1,1,0),\ (1,2,1),\ (2,3,3),$$

whose coordinate sums are

$$1,2,4,8.$$

This suggests powers of $2$.

Let

$$M=\begin{pmatrix} 1&1&0\ 0&1&1\ 1&0&1 \end{pmatrix}.$$

The exponent vectors for the three primes are $M^n e_1$, $M^n e_2$, $M^n e_3$. The columns of $M^n$ therefore give the exponents of $2,3,5$ in each position. The crucial point is to understand these columns modulo a common divisor.

A useful observation is

$$(1,1,1)M=2(1,1,1).$$

Hence the entries in every column of $M^n$ sum to $2^n$.

If a column had all entries divisible by some $d>1$, then its sum $2^n$ would be divisible by $d$, so $d$ would have to be a power of $2$. Thus it remains to show that no column of $M^n$ consists entirely of even numbers.

Modulo $2$,

$$M\equiv \begin{pmatrix} 1&1&0\ 0&1&1\ 1&0&1 \end{pmatrix}.$$

A direct calculation gives

$$M^3\equiv I \pmod 2.$$

Hence $M^n$ is invertible modulo $2$ for every $n$, so no column of $M^n$ can be the zero column modulo $2$. Therefore no column has all entries even.

This yields gcd $1$ for every column, which is exactly what is needed.

Problem Understanding

We are given a sequence of triples of positive integers. From a triple $(a,b,c)$ we obtain the next triple

$$(ab,\ bc,\ ca).$$

Starting from $(2,3,5)$, we must prove that no number appearing anywhere in the sequence is a nontrivial perfect power, that is, no number is a square, cube, fourth power, and so on.

This is a Type B problem. The statement itself is to be proved.

The difficulty is that the numbers grow rapidly, so direct factorization is useless. The natural invariant is the vector of exponents of the primes $2,3,5$, whose evolution is linear.

Proof Architecture

Let

$$M=\begin{pmatrix} 1&1&0\ 0&1&1\ 1&0&1 \end{pmatrix}.$$

The proof uses the following claims.

First, the exponents of each prime in the three positions evolve by multiplication by $M$, because forming products adds exponents.

Second, the exponents of $2,3,5$ in any fixed position are exactly the entries of a column of $M^n$, because the initial exponent vectors are the standard basis vectors.

Third, the sum of the entries of every column of $M^n$ equals $2^n$, because $(1,1,1)$ is a left eigenvector of $M$ with eigenvalue $2$.

Fourth, no column of $M^n$ is entirely even. Modulo $2$, one has $M^3\equiv I$, hence $M^n$ is invertible modulo $2$ for every $n$, and therefore none of its columns is the zero column modulo $2$.

Fifth, the three entries of any column of $M^n$ have greatest common divisor $1$. Any common divisor must divide the column sum $2^n$, hence is a power of $2$; the previous claim excludes divisibility by $2$.

Finally, a positive integer is a nontrivial perfect power if and only if the exponents in its prime factorization have a common divisor greater than $1$. Since the exponent triple for every number has gcd $1$, no number obtained is a perfect power.

The most delicate point is the passage from the matrix description to the statement that the gcd of each column equals $1$.

Solution

Let

$$(a_n,b_n,c_n)$$

denote the $n$th triple, where

$$(a_0,b_0,c_0)=(2,3,5),$$

and

$$a_{n+1}=a_nb_n,\qquad b_{n+1}=b_nc_n,\qquad c_{n+1}=c_na_n.$$

Since the initial numbers contain only the primes $2,3,5$, every number appearing later also contains only these primes.

For a fixed prime $p\in{2,3,5}$, let

$$x_n^{(p)},\ y_n^{(p)},\ z_n^{(p)}$$

be the exponents of $p$ in $a_n,b_n,c_n$ respectively. Because exponents add when numbers are multiplied,

$$x_{n+1}^{(p)}=x_n^{(p)}+y_n^{(p)},$$

$$y_{n+1}^{(p)}=y_n^{(p)}+z_n^{(p)},$$

$$z_{n+1}^{(p)}=z_n^{(p)}+x_n^{(p)}.$$

Writing

$$v_n^{(p)}= \begin{pmatrix} x_n^{(p)}\ y_n^{(p)}\ z_n^{(p)} \end{pmatrix},$$

we obtain

$$v_{n+1}^{(p)}=Mv_n^{(p)}, \qquad M= \begin{pmatrix} 1&1&0\ 0&1&1\ 1&0&1 \end{pmatrix}.$$

The initial exponent vectors are

$$v_0^{(2)}=e_1,\qquad v_0^{(3)}=e_2,\qquad v_0^{(5)}=e_3,$$

where $e_1,e_2,e_3$ are the standard basis vectors. Hence

$$v_n^{(2)}=M^n e_1,\qquad v_n^{(3)}=M^n e_2,\qquad v_n^{(5)}=M^n e_3.$$

Consider any fixed position, for example $a_n$. Its exponents of $2,3,5$ are the first entries of the vectors above. Equivalently, they are the three entries of the first column of $M^n$. The same statement holds for $b_n$ and $c_n$, using the second and third columns.

Thus it suffices to prove that every column of $M^n$ has greatest common divisor $1$.

Let

$$u=(1,1,1).$$

Since

$$uM=(2,2,2)=2u,$$

we have

$$uM^n=2^n u.$$

Therefore the sum of the entries of every column of $M^n$ equals $2^n$.

Let a column of $M^n$ have common divisor $d$. Then $d$ divides the sum of its entries, so

$$d\mid 2^n.$$

Consequently $d$ is a power of $2$.

We now show that no column of $M^n$ is entirely even. Reducing modulo $2$,

$$M\equiv \begin{pmatrix} 1&1&0\ 0&1&1\ 1&0&1 \end{pmatrix}.$$

A direct multiplication gives

$$M^2\equiv \begin{pmatrix} 1&0&1\ 1&1&0\ 0&1&1 \end{pmatrix},$$

and then

$$M^3\equiv I \pmod 2.$$

Hence for every $n$,

$$M^n$$

is invertible modulo $2$. An invertible matrix cannot have a zero column modulo $2$. Therefore every column of $M^n$ contains at least one odd entry.

So no column is divisible by $2$, and its common divisor cannot be a positive power of $2$. Since every common divisor was already shown to divide $2^n$, the greatest common divisor of the entries of every column is $1$.

Take any number occurring in the process. Its exponents of the primes $2,3,5$ are exactly the entries of one of these columns, whose gcd is $1$.

If that number were equal to $m^k$ with $k>1$, then every exponent in its prime factorization would be divisible by $k$. The gcd of the exponents would then be at least $k$, contradicting the fact that the gcd is $1$.

Thus no number appearing in the sequence is a square, cube, or any higher perfect power.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is identifying the exponents of a fixed number with a column of $M^n$. For $a_n$, the exponent of $2$ is the first component of $M^n e_1$, the exponent of $3$ is the first component of $M^n e_2$, and the exponent of $5$ is the first component of $M^n e_3$. These three quantities are precisely the entries of the first column of $M^n$. The same argument applies to the other positions. Confusing rows and columns here would invalidate the remainder of the proof.

The second delicate step is proving that every common divisor of a column divides $2^n$. Let the column entries be $r,s,t$. Since

$$(1,1,1)M^n=2^n(1,1,1),$$

their sum satisfies

$$r+s+t=2^n.$$

Any common divisor of $r,s,t$ divides $r+s+t$, hence divides $2^n$. This is the only place where the eigenvector relation is used.

The third delicate step is excluding divisibility by $2$. Computing modulo $2$,

$$M^3\equiv I.$$

Thus

$$M^n$$

is invertible modulo $2$ for every $n$. If some column were entirely even, that column would be zero modulo $2$, and a matrix with a zero column cannot be invertible. Hence every column contains an odd entry.

Alternative Approaches

One may diagonalize $M$. Its eigenvalues are $2$ and the complex cube roots of unity. From this one obtains explicit formulas for the entries of $M^n$. These formulas show that each column consists of three integers whose sum is $2^n$ and whose parities cycle with period $3$. The same gcd argument then finishes the proof.

The matrix modulo $2$ approach is preferable because it avoids explicit eigenvalue calculations. The only facts needed are the column-sum identity and the congruence $M^3\equiv I\pmod 2$, which together give the gcd immediately.