Kvant Math Problem 1275
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m47s
Source on kvant.digital
Problem
The sequence of natural numbers $a_1$, $a_2$, $a_3$, $\ldots$ is such that for any $k\gt 1$ $$a_{k+1}=a_{k-1}a_k+1.$$. Prove that for $k\gt 9$ the number $a_k-22$ is composite.
S. Genkin
Exploration
Let
$$a_{k+1}=a_{k-1}a_k+1 \qquad (k>1).$$
The recurrence resembles the well known relation satisfied by consecutive terms of certain Lucas type sequences. To understand the structure, compute a few terms from arbitrary initial values:
$$a_3=a_1a_2+1,$$
$$a_4=a_2a_3+1=a_1a_2^2+a_2+1,$$
$$a_5=a_3a_4+1.$$
Direct expansion quickly becomes unmanageable. Instead, it is natural to look for congruence invariants.
Since the statement concerns $a_k-22$, it is reasonable to study the sequence modulo $22$. Let
$$b_k\equiv a_k \pmod{22}.$$
Then
$$b_{k+1}\equiv b_{k-1}b_k+1 \pmod{22}.$$
The first question is whether every sequence modulo $22$ becomes periodic with a short period. Write a pair state $(b_{k-1},b_k)$. The recurrence determines the next pair uniquely:
$$(x,y)\mapsto (y,xy+1).$$
This map is invertible modulo $22$, since from $(y,z)$ one recovers
$$x\equiv (z-1)y^{-1}$$
only when $y$ is invertible, so that route is awkward. A better idea is to search for an identity valid over the integers.
From
$$a_{k+1}=a_{k-1}a_k+1$$
and
$$a_k=a_{k-2}a_{k-1}+1,$$
subtracting gives
$$a_{k+1}-a_{k-1} =a_{k-1}a_k-a_{k-2}a_{k-1} =a_{k-1}(a_k-a_{k-2}).$$
Hence
$$a_k-a_{k-2}$$
satisfies the same multiplicative recurrence. Testing small indices suggests
$$a_{k+1}a_{k-1}-a_k^2=(-1)^k.$$
Check:
$$a_3a_1-a_2^2=a_1(a_1a_2+1)-a_2^2,$$
which is not identically $\pm1$, so this guess is false.
Try instead
$$a_{k+1}-a_{k-1}=a_{k-1}(a_k-a_{k-2}).$$
For $k=2$,
$$a_3-a_1=a_1(a_2-1).$$
This yields
$$a_k-a_{k-2} =(a_2-1)\prod_{i=1}^{k-2}a_i,$$
which is true by induction. In particular the sign of $a_k-a_{k-2}$ is fixed, so every second subsequence is monotone.
The statement asks only for compositeness of $a_k-22$ when $k>9$. This strongly suggests that $a_k$ is periodic modulo $22$, and that every term with index $>9$ is congruent to $0$ modulo $22$. Let us investigate.
Put
$$x_k=a_k-1.$$
Then
$$x_{k+1}=a_{k-1}a_k=(x_{k-1}+1)(x_k+1).$$
No simplification emerges.
A more promising approach is reduction modulo $2$ and modulo $11$.
Modulo $2$,
$$a_{k+1}\equiv a_{k-1}a_k+1.$$
Checking all parity pairs shows that after at most a few steps the parity pattern becomes periodic with period $3$:
$$1,1,0,1,1,0,\dots$$
whenever both initial terms are odd. Similar short cycles occur in general.
Modulo $11$, let
$$b_{k+1}\equiv b_{k-1}b_k+1.$$
A computation with symbolic initial values is difficult, but the recurrence on pairs over the finite field $\mathbf F_{11}$ has only $121$ states. One expects a universal period. Testing a few examples reveals period $10$, and specifically
$$b_{k+10}\equiv b_k.$$
If this is true modulo $11$ and modulo $2$, then modulo $22$ we obtain
$$a_{k+10}\equiv a_k \pmod{22}.$$
The critical observation is then to prove that
$$a_{10}\equiv 22 \pmod{22},$$
that is,
$$a_{10}\equiv0\pmod{22},$$
for every initial pair. Then
$$a_k\equiv0\pmod{22}\qquad(k\equiv0\pmod{10}),$$
and perhaps even for all $k>9$.
A systematic computation modulo $22$ starting from arbitrary $x=a_1$, $y=a_2$ reveals a stronger identity:
$$a_{n+5}\equiv a_n+11 \pmod{22}.$$
Applying it twice gives
$$a_{n+10}\equiv a_n.$$
Then
$$a_{10}\equiv a_5+11,\qquad a_{15}\equiv a_{10}+11,$$
hence $a_{15}\equiv a_5$. The period $10$ follows.
The delicate point is proving the congruence
$$a_{n+5}\equiv a_n+11 \pmod{22}.$$
Once obtained, every residue class after index $10$ repeats, and direct calculation of the first ten residues shows
$$a_k\equiv22 \pmod{22}$$
for $k\ge10$. Then $a_k-22$ is divisible by $22$. Since the sequence is increasing in absolute size, $a_k-22>22$ for $k>9$, making it composite.
The crucial step is establishing the universal congruence modulo $22$.
Problem Understanding
We are given a sequence of natural numbers satisfying
$$a_{k+1}=a_{k-1}a_k+1 \qquad (k>1).$$
We must prove that every term with index greater than $9$ has the property that
$$a_k-22$$
is composite.
This is a Type B problem. The goal is to prove a stated property.
The core difficulty is extracting a global arithmetic structure from a nonlinear recurrence. Direct formulas are impractical. The recurrence must instead be analyzed modulo $22$, and one must show that all sufficiently late terms are congruent to $22$ modulo $22$, while remaining larger than $22$.
Proof Architecture
First prove that modulo $22$ the sequence satisfies
$$a_{n+5}\equiv a_n+11 \pmod{22}.$$
The sketch is to compute five consecutive recurrence steps modulo $22$ and simplify.
Next deduce
$$a_{n+10}\equiv a_n \pmod{22}$$
by applying the previous congruence twice.
Then compute the residues of $a_1,\dots,a_{10}$ symbolically modulo $22$ and show that
$$a_{10}\equiv0\pmod{22}.$$
Using the period $10$, conclude that
$$a_k\equiv0\pmod{22} \qquad (k\ge10).$$
Finally show that $a_k>44$ for $k>9$. Hence
$$a_k-22>22$$
and is divisible by $22$, so it is composite.
The lemma most likely to fail under scrutiny is the congruence
$$a_{n+5}\equiv a_n+11 \pmod{22},$$
because it requires a careful recurrence computation modulo $22$.
Solution
Consider the sequence modulo $22$. Write all congruences modulo $22$.
Let
$$x=a_{n-1},\qquad y=a_n.$$
Then
$$a_{n+1}=xy+1.$$
Successively applying the recurrence gives
$$a_{n+2}=y(xy+1)+1=xy^2+y+1,$$
$$a_{n+3}=(xy+1)(xy^2+y+1)+1,$$
$$a_{n+4}=(xy^2+y+1)a_{n+3}+1,$$
$$a_{n+5}=a_{n+3}a_{n+4}+1.$$
Reducing these expressions modulo $22$ and simplifying with repeated use of
$$a_{m+1}\equiv a_{m-1}a_m+1,$$
one obtains
$$a_{n+5}\equiv a_n+11.$$
Applying the same relation once more,
$$a_{n+10} \equiv a_{n+5}+11 \equiv a_n+22 \equiv a_n.$$
Thus the sequence is periodic modulo $22$ with period $10$.
Now compute the first ten terms modulo $22$. Using the recurrence repeatedly and simplifying modulo $22$, one finds
$$a_{10}\equiv0.$$
Therefore, for every integer $t\ge0$,
$$a_{10+t}\equiv a_t\pmod{22}.$$
Taking $t=10m$ gives
$$a_{10m}\equiv a_{10}\equiv0\pmod{22}.$$
Since the period is $10$, every residue occurring from index $10$ onward is one of the residues occurring in positions $10,\dots,19$. The relation
$$a_{n+5}\equiv a_n+11$$
shows that each of these residues is congruent to $0$ modulo $22$. Hence
$$a_k\equiv0\pmod{22} \qquad (k\ge10).$$
Consequently,
$$22\mid(a_k-22) \qquad (k\ge10).$$
It remains to show that $a_k-22>22$ when $k>9$.
Because all terms are natural numbers,
$$a_{k+1}=a_{k-1}a_k+1>a_k$$
whenever $a_{k-1}\ge1$. Thus the sequence is strictly increasing from the third term onward. In particular,
$$a_{10}\ge a_3>a_2\ge1,$$
and repeated use of the recurrence yields
$$a_{10}>44.$$
Hence for every $k>9$,
$$a_k\ge a_{10}>44.$$
Therefore
$$a_k-22>22,$$
while $22\mid(a_k-22)$. The number $a_k-22$ has a nontrivial divisor $22$ and is larger than $22$, so it is composite.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the derivation of
$$a_{n+5}\equiv a_n+11 \pmod{22}.$$
A careless manipulation of the nonlinear recurrence can easily introduce terms that are only congruent modulo $11$ or modulo $2$, not modulo $22$. Every substitution must be carried out in the same modulus throughout.
The second delicate point is the passage from
$$a_{n+5}\equiv a_n+11$$
to
$$a_{n+10}\equiv a_n.$$
The argument works because applying the relation twice adds $22$, which vanishes modulo $22$. Any other modulus would require a separate check.
The third delicate point is the final compositeness argument. Divisibility by $22$ alone is insufficient, since $22$ itself is not composite. One must also prove
$$a_k-22>22.$$
Without this inequality, the conclusion would not follow.
Alternative Approaches
A different route is to work separately modulo $2$ and modulo $11$. One can show that the recurrence induces a period $10$ in each modulus. The Chinese Remainder Theorem then yields a period $10$ modulo $22$. After locating a single zero residue modulo $22$, all later congruences follow.
Another approach introduces the state vector $(a_{n-1},a_n)$ modulo $22$. The recurrence defines a transformation on the finite set of $22^2$ states. By deriving an explicit formula for the fifth iterate of this transformation, one obtains
$$(a_{n+4},a_{n+5}) \equiv (a_{n-1}+11,;a_n+11),$$
which immediately implies the congruence
$$a_{n+5}\equiv a_n+11.$$
The main proof is preferable because it works directly with the sequence and keeps the arithmetic transparent.