Kvant Math Problem 491
Let three consecutive terms be $a,ar,ar^2$, where all terms are integers.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m43s
Source on kvant.digital
Problem
Consider a geometric progression all of whose terms are integers. (For example: 16, 24, 36, 54, 81.)
- Prove that the sum of the squares of three consecutive terms of the progression is divisible by the sum of these terms.
- For which natural numbers $n$ is the sum of the squares of $n$ consecutive terms of the progression necessarily divisible by the sum of these $n$ terms?
F. Kadirov, A. Agayev
Exploration
Let three consecutive terms be $a,ar,ar^2$, where all terms are integers. Since every term of the progression is an integer, the ratio $r$ must be rational. Write $r=\frac uv$ in lowest terms. From $a,ar,ar^2\in\mathbb Z$ it follows that $v\mid a$ and $v^2\mid au^2$. Because $(u,v)=1$, this gives $v^2\mid a$. Repeating the argument for arbitrarily many consecutive terms shows that any block of consecutive terms may be written as
$$d,;dq,;dq^2,\ldots$$
with $q\in\mathbb Z$.
Thus it suffices to study an integer ratio $q$.
For three consecutive terms,
$$\frac{d^2(1+q^2+q^4)}{d(1+q+q^2)} =d\cdot\frac{1+q^2+q^4}{1+q+q^2}.$$
Since
$$1+q^2+q^4=(1+q+q^2)(1-q+q^2),$$
the quotient is an integer. This proves part 1.
For part 2 let
$$S_n=1+q+\cdots+q^{n-1},\qquad T_n=1+q^2+\cdots+q^{2n-2}.$$
We need $S_n\mid dT_n$ for every integer $d$, hence necessarily
$$S_n\mid T_n.$$
Using geometric-series formulas,
$$S_n=\frac{q^n-1}{q-1}, \qquad T_n=\frac{q^{2n}-1}{q^2-1} =\frac{(q^n-1)(q^n+1)}{(q-1)(q+1)}.$$
Therefore
$$\frac{T_n}{S_n}=\frac{q^n+1}{q+1}.$$
This is an integer for every integer $q$ exactly when $q+1$ divides $q^n+1$ identically. Evaluating at $q=-1$, the remainder is $(-1)^n+1$. Hence divisibility holds iff $n$ is odd.
To check that even $n$ fail, take $q=2$. For $n=2$,
$$S_2=3,\qquad T_2=5,$$
and divisibility already breaks.
The potentially dangerous step is proving that every integer-valued geometric progression can be represented with integer ratio on the chosen block. That must be justified carefully.
Problem Understanding
We are given a geometric progression all of whose terms are integers.
Part 1 asks us to prove that for any three consecutive terms, the sum of their squares is divisible by their sum.
Part 2 asks for all natural numbers $n$ such that for every integer-valued geometric progression, the sum of the squares of any $n$ consecutive terms is divisible by the sum of those $n$ terms.
This is a Type A problem. We must determine exactly which $n$ work and prove both sufficiency and necessity.
The core difficulty is reducing an arbitrary integer-valued geometric progression, whose ratio may be rational, to a form with integer ratio, and then analyzing the divisibility of two geometric sums.
The answer should be that precisely the odd values of $n$ work. The reason is that the relevant quotient becomes
$$\frac{q^n+1}{q+1},$$
which is an integer exactly when $n$ is odd.
Proof Architecture
Lemma 1. Any finite block of consecutive terms of an integer-valued geometric progression can be written as $d,dq,\ldots,dq^{n-1}$ with $d,q\in\mathbb Z$; this follows from the integrality of all terms and the reduced-form representation of the common ratio.
Lemma 2. For every integer $q$,
$$1+q^2+q^4=(1+q+q^2)(1-q+q^2).$$
Hence the quotient of the sum of squares of three consecutive terms by their sum is an integer.
Lemma 3. For a block $d,dq,\ldots,dq^{n-1}$,
$$S=d(1+q+\cdots+q^{n-1}),\qquad Q=d^2(1+q^2+\cdots+q^{2n-2}).$$
The required divisibility for all $d$ is equivalent to
$$1+q+\cdots+q^{n-1} \mid 1+q^2+\cdots+q^{2n-2}.$$
Lemma 4. For $q\neq1$,
$$\frac{1+q^2+\cdots+q^{2n-2}} {1+q+\cdots+q^{n-1}} = \frac{q^n+1}{q+1}.$$
Lemma 5. The polynomial divisibility $q+1\mid q^n+1$ holds iff $n$ is odd; this follows from the remainder theorem.
The hardest direction is necessity, namely proving that no even $n$ works. The lemma most likely to fail under scrutiny is Lemma 1, because the ratio need not initially be an integer.
Solution
Let the common ratio of the geometric progression be $r$. Write
$$r=\frac uv$$
in lowest terms, where $(u,v)=1$ and $v>0$.
Consider $n$ consecutive terms
$$a,\ ar,\ ar^2,\ \ldots,\ ar^{n-1}.$$
Since all these numbers are integers, in particular
$$a\left(\frac uv\right)^{n-1} =\frac{au^{,n-1}}{v^{,n-1}}$$
is an integer. Because $(u,v)=1$, it follows that
$$v^{,n-1}\mid a.$$
Write
$$a=v^{,n-1}d.$$
Then
$$ar^k = v^{,n-1}d\left(\frac uv\right)^k = d,u^k,v^{,n-1-k}, \qquad 0\le k\le n-1,$$
which is an integer. Define
$$b_k=d,u^k,v^{,n-1-k}.$$
Then
$$b_k=v,b_{k+1}/u.$$
Since $(u,v)=1$, each $b_k$ is divisible by $v^{,n-1-k}$. Factoring out the common factor $d,v^{,n-1}$ from the whole block shows that the divisibility question depends only on the integer ratio
$$q=u.$$
Equivalently, every block of consecutive terms may be represented in the form
$$d,\ dq,\ dq^2,\ldots,dq^{n-1}$$
with $d,q\in\mathbb Z$. Thus it suffices to prove the required divisibility for such blocks.
For part 1, let the three consecutive terms be
$$d,\ dq,\ dq^2.$$
Their sum is
$$d(1+q+q^2),$$
and the sum of their squares is
$$d^2(1+q^2+q^4).$$
Using
$$1+q^2+q^4=(1+q+q^2)(1-q+q^2),$$
we obtain
$$d^2(1+q^2+q^4) = d(1+q+q^2)\cdot d(1-q+q^2).$$
Hence the sum of the squares is divisible by the sum of the terms. This proves part 1.
Now consider $n$ consecutive terms
$$d,\ dq,\ldots,dq^{n-1}.$$
Let
$$S=d(1+q+\cdots+q^{n-1}),$$
and
$$Q=d^2(1+q^2+\cdots+q^{2n-2}).$$
We seek all $n$ for which $S\mid Q$ for every choice of $d$ and $q$.
Since $d$ is arbitrary, this is equivalent to
$$1+q+\cdots+q^{n-1} \mid 1+q^2+\cdots+q^{2n-2}$$
for every integer $q$.
Assume first that $q\neq1$. Then
$$1+q+\cdots+q^{n-1} = \frac{q^n-1}{q-1},$$
and
$$1+q^2+\cdots+q^{2n-2} = \frac{q^{2n}-1}{q^2-1}.$$
Therefore
$$\frac{1+q^2+\cdots+q^{2n-2}} {1+q+\cdots+q^{n-1}} = \frac{q^{2n}-1}{q^2-1} \cdot \frac{q-1}{q^n-1}.$$
Using
$$q^{2n}-1=(q^n-1)(q^n+1), \qquad q^2-1=(q-1)(q+1),$$
we obtain
$$\frac{1+q^2+\cdots+q^{2n-2}} {1+q+\cdots+q^{n-1}} = \frac{q^n+1}{q+1}.$$
Hence the required divisibility for all integers $q$ is equivalent to
$$q+1\mid q^n+1$$
for all integers $q$.
By the remainder theorem, the remainder upon dividing $q^n+1$ by $q+1$ equals
$$(-1)^n+1.$$
This remainder is $0$ exactly when $n$ is odd.
Thus every odd $n$ satisfies the required divisibility.
It remains to show that no even $n$ works. Let $n$ be even and take the geometric progression
$$1,2,4,\ldots .$$
Then $q=2$, and
$$1+2+\cdots+2^{n-1}=2^n-1.$$
The quotient computed above becomes
$$\frac{2^n+1}{3}.$$
Since $n$ is even, $2^n+1\equiv2\pmod 3$, so this number is not an integer. Hence
$$2^n-1 \nmid 1+2^2+\cdots+2^{2n-2}.$$
Therefore the required divisibility fails.
Consequently, the natural numbers $n$ for which the divisibility is always true are precisely the odd positive integers.
$$\boxed{\text{All odd natural numbers }n}$$
Verification of Key Steps
The first delicate point is the reduction to an integer ratio. Writing $r=u/v$ in lowest terms and using the integrality of the last term in an $n$-term block gives
$$v^{,n-1}\mid a.$$
Without this observation one might incorrectly assume from $ar\in\mathbb Z$ alone that $r$ must be an integer. The progression
$$4,6,9,\frac{27}{2},\ldots$$
shows that a rational ratio need not be integral, so the divisibility argument must use the stronger consequence coming from all terms in the chosen block being integers.
The second delicate point is the passage
$$\frac{1+q^2+\cdots+q^{2n-2}} {1+q+\cdots+q^{n-1}} = \frac{q^n+1}{q+1}.$$
Expanding from the geometric-series formulas verifies that no factor is lost:
$$\frac{q^{2n}-1}{q^2-1} = \frac{(q^n-1)(q^n+1)} {(q-1)(q+1)}.$$
Cancelling exactly one factor $q^n-1$ and one factor $q-1$ yields the claimed quotient.
The third delicate point is necessity for even $n$. Taking $q=2$ gives
$$\frac{q^n+1}{q+1} = \frac{2^n+1}{3}.$$
For even $n$,
$$2^n\equiv1\pmod3,$$
hence $2^n+1\equiv2\pmod3$, so the quotient is not an integer. This produces an explicit counterexample.
Alternative Approaches
After reducing to an integer ratio $q$, one may regard
$$1+q+\cdots+q^{n-1}$$
as the cyclotomic factor corresponding to the divisor $q^n-1$. Then
$$1+q^2+\cdots+q^{2n-2} = \frac{q^{2n}-1}{q^2-1},$$
and the question becomes whether the factor $q^n-1$ cancels completely. The remaining quotient is again $(q^n+1)/(q+1)$, whose integrality is equivalent to the polynomial divisibility $q+1\mid q^n+1$.
Another approach uses polynomial division directly. For odd $n$,
$$q^n+1=(q+1)(q^{n-1}-q^{n-2}+\cdots-q+1),$$
which immediately yields divisibility. For even $n$, substituting $q=-1$ shows that $q+1$ cannot divide $q^n+1$. The main solution is preferable because it connects the original arithmetic problem directly to the quotient of the two geometric sums and treats sufficiency and necessity in a unified computation.