Kvant Math Problem 427
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m23s
Source on kvant.digital
Problem
- Prove that there exists an odd number $n$ such that, for no even $k$, is any of the numbers in the infinite sequence $$k^k+1,\ k^{k^k}+1,\ k^{k^{k^k}}+1,\ \ldots$$ divisible by $n$.
- Prove that for every positive integer $n$ there exists a positive integer $k$ such that every term of the infinite sequence $$k+1,\ k^k+1,\ k^{k^k}+1,\ k^{k^{k^k}}+1,\ \ldots$$ is divisible by $n$.
S. Lavrenchenko, Grade 9
Exploration
Let
$$a_0=k,\qquad a_{m+1}=k^{a_m}.$$
Then the sequences in the problem are
$$a_1+1,\ a_2+1,\ a_3+1,\dots$$
in part 1, and
$$a_0+1,\ a_1+1,\ a_2+1,\dots$$
in part 2.
The divisibility condition concerns numbers of the form $a_m+1$. A natural way to force divisibility by some modulus $n$ is to arrange
$$a_m\equiv -1\pmod n$$
for all $m$.
To understand when this can happen, first test a prime modulus. Suppose $p$ is odd and
$$k\equiv -1\pmod p.$$
If $k$ is odd, then every exponent $a_m$ is odd, hence
$$a_{m+1}=k^{a_m}\equiv (-1)^{a_m}\equiv -1\pmod p.$$
Thus $a_m\equiv -1\pmod p$ for every $m$.
This suggests that if $k\equiv -1\pmod n$ and $k$ is odd, then all terms might be congruent to $-1$ modulo every divisor of $n$. Indeed, if $d\mid n$, then $k\equiv -1\pmod d$, and the same induction works modulo $d$.
For part 2 this already suggests taking
$$k=n-1$$
when $n$ is even, and some odd number congruent to $-1$ modulo $n$ when $n$ is odd. A uniform choice is
$$k=2n-1,$$
which is always odd and satisfies $k\equiv -1\pmod n$.
For part 1 we need an odd modulus $n$ such that no term is divisible by $n$ for any even $k$.
Try a prime modulus $p$. If $k$ is even and $p\mid k+1$, then the first term is divisible by $p$, so such primes are unsuitable. We need a modulus for which the congruence
$$k^t\equiv -1\pmod p$$
never occurs when $k$ is even.
The prime $3$ is too small, because $k\equiv2\pmod3$ gives
$$k^1+1\equiv0\pmod3.$$
Consider $p=5$. The even residues modulo $5$ are $0,2,4$.
If $k\equiv0\pmod5$, then every $k^t+1\equiv1\pmod5$.
If $k\equiv4\equiv-1\pmod5$, then for divisibility by $5$ we would need the exponent $t$ odd. In our sequence the exponents are
$$k,\ k^k,\ k^{k^k},\dots$$
and every one of them is even because $k$ is even. Hence
$$(-1)^t=1,$$
so $k^t+1\equiv2\pmod5$.
If $k\equiv2\pmod5$, then powers of $2$ modulo $5$ are
$$2,4,3,1,$$
with period $4$. The value $-1\equiv4$ occurs only for exponents congruent to $2$ modulo $4$. Every exponent in our sequence is even, but more is true. Since $k$ is even,
$$k^m\equiv0\pmod4$$
for every positive $m$.
Hence every exponent after the first is divisible by $4$. Then
$$2^t\equiv1\pmod5,$$
never $-1$.
For the first exponent $t=k$, divisibility by $5$ would require
$$k\equiv2\pmod4.$$
Combining with $k\equiv2\pmod5$ gives examples such as $k=2$, and indeed
$$2^2+1=5.$$
So $5$ fails.
The problem is that the first exponent is only $k$, not an iterated power. We need a prime where even the first term never works.
Try $17$. The element $-1$ has order $2$. For $k\equiv -1\pmod{17}$, the exponent would need to be odd, impossible. For residues of even order, reaching $-1$ requires the exponent to lie in a specific congruence class modulo a power of $2$. Since every exponent in the sequence is even, and from the second stage onward divisible by $4$, a Fermat prime where the multiplicative group has order $16$ may eliminate all possibilities.
Take a systematic approach. Let $k$ be even.
If $17\mid k$, then all terms are $1$ modulo $17$.
Otherwise write $r\equiv k\pmod{17}$. The group $(\mathbb Z/17\mathbb Z)^\times$ has order $16$. Let $d$ be the order of $r$. Since $d\mid16$, it is a power of $2$.
The congruence
$$r^t\equiv -1$$
is possible only when $d\ge2$ and
$$t\equiv d/2\pmod d.$$
Since $d$ is a power of $2$, the residue $d/2$ is divisible by $d/2$ but not by $d$.
Every exponent occurring in the sequence is even; from the second stage onward it is divisible by $4$. If $d\ge4$, then $d/2$ is not divisible by $d$, whereas all sufficiently deep exponents are multiples of $d$ once they become large powers of an even number. A cleaner argument is needed.
Observe that for every positive exponent $e$ occurring in the sequence,
$$v_2(e)\ge1,$$
and for all except the first,
$$v_2(e)\ge2.$$
If $d=2^s$, then $r^e=-1$ requires
$$v_2(e)=s-1.$$
Indeed, in a cyclic group of order $2^s$, an element of order $2^s$ satisfies $g^e=-1$ exactly when $v_2(e)=s-1$.
The first exponent is $k$, whose $2$-adic valuation can vary, so this still needs care.
A better idea is to choose $17$ and use the fact that every even residue modulo $17$ has order $1,2,4,$ or $8$, never $16$. Checking quickly:
$$2 \text{ has order }8,\quad 4 \text{ has order }4,\quad 8 \text{ has order }8,\quad 16 \text{ has order }2.$$
The order of any even residue divides $8$ because even residues are powers of $2$ times odd residues, and the group order is $16$. The crucial observation is that if $d\le8$, then obtaining $-1$ requires the exponent to be congruent to $d/2$ modulo $d$, hence not divisible by $d$. But every exponent in the sequence is a multiple of $k$, and modulo powers of $2$ this forces enough divisibility. The cleanest route is to use a primitive root.
Let $g$ be a primitive root modulo $17$. Every even residue is $g^m$ with $m$ even, because $2=g^{14}$ and every even residue equals $2u$. Then
$$-1=g^8.$$
If $(g^m)^t=-1$, then
$$mt\equiv8\pmod{16}.$$
Since $m$ is even and $t$ is even, the left side is divisible by $4$, while $8$ is divisible by $8$ but not by $16$; this is still not enough.
Take $m=2u$. Then
$$ut\equiv4\pmod8.$$
Because $t$ is an even power-built exponent, $t$ is divisible by $2$, and after the first stage by $4$. Working modulo $8$, one finds that $ut$ can never be congruent to $4$ for all possible $u$? This route becomes cumbersome.
A simpler argument is available. Let $n=17$. Every even $k$ satisfies $k^m\equiv0,1,2,4,8,9,13,15,16\pmod{17}$ for any positive exponent $m$, because the subgroup generated by $2$ has order $8$ and consists exactly of
$${1,2,4,8,16,15,13,9}.$$
This subgroup does not contain $-1\equiv16$? It does contain $16$, so not good.
Try $257$? This is getting unnecessarily complicated.
Return to $5$. The only failure came from the first term when $k\equiv2\pmod5$ and $k\equiv2\pmod4$. We can eliminate that by squaring the modulus. Take $25$.
If $k^t\equiv-1\pmod{25}$, then modulo $5$ we also have $k^t\equiv-1\pmod5$. Thus $k\equiv2$ or $4\pmod5$.
For $k\equiv4\pmod5$, even exponents never give $-1$ modulo $5$.
For $k\equiv2\pmod5$, the order of $2$ modulo $25$ is $20$. To get $-1$, the exponent must be congruent to $10$ modulo $20$, hence congruent to $2$ modulo $4$. Every exponent after the first is divisible by $4$, and the first exponent equals $k$. If $k\equiv2\pmod{20}$, then indeed $k^k+1$ is divisible by $25$? Check:
$$2^2+1=5,$$
not $25$.
Modulo $25$, $2^{10}\equiv-1$, not $2^2$.
So the stronger modulus may work.
The key is to use $n=25$. For $k\equiv2\pmod5$, write $k=2u$ even. Any exponent occurring is even. If $k$ is not divisible by $5$, Euler gives order dividing $20$. Since $-1$ is the unique element of order $2$, $k^t\equiv-1$ implies the exponent is congruent to $10$ modulo $20/\gcd(20,\operatorname{ind}(k))$. A direct classification modulo $25$ is lengthy.
A cleaner standard solution is likely $n=25$: for even $k$, every exponent in the sequence is divisible by $2$, and from the second stage by $4$; the residues giving $-1$ modulo $25$ require exponents congruent to $2\pmod4$. This suggests a complete order argument.
Problem Understanding
This is a Type B problem.
For part 1 we must exhibit an odd integer $n$ such that, for every even integer $k$, none of the numbers
$$k^k+1,\quad k^{k^k}+1,\quad k^{k^{k^k}}+1,\dots$$
is divisible by $n$.
For part 2 we must show that for each positive integer $n$ there exists a positive integer $k$ for which every term of
$$k+1,\quad k^k+1,\quad k^{k^k}+1,\quad k^{k^{k^k}}+1,\dots$$
is divisible by $n$.
The core difficulty is understanding the iterated exponents modulo a fixed modulus. Part 2 is constructive and suggests forcing all iterated powers to be congruent to $-1$ modulo $n$. Part 1 requires finding a modulus for which the residue $-1$ is never attained by the relevant iterated powers when the base is even.
Proof Architecture
Let $a_0=k$ and $a_{m+1}=k^{a_m}$.
First, prove that if $k$ is odd and $k\equiv-1\pmod n$, then $a_m\equiv-1\pmod n$ for every $m$, by induction using the oddness of all exponents.
Second, deduce part 2 by choosing $k=2n-1$, which is odd and satisfies $k\equiv-1\pmod n$.
For part 1, take $n=25$.
Prove that if $25\mid k$ then every term equals $1$ modulo $25$.
Prove that if $k\equiv4\pmod5$, then every exponent occurring in the sequence is even, hence $k^t\not\equiv-1\pmod5$, so divisibility by $25$ is impossible.
Prove that if $k\equiv2\pmod5$ or $k\equiv3\pmod5$, then the residue class of $k$ modulo $25$ has order dividing $20$, and $k^t\equiv-1\pmod{25}$ can occur only when $t\equiv10\pmod{20}$. Show that every exponent appearing in the sequence is divisible by $4$ from the second stage onward, while the first exponent equals an even number. Hence no exponent is congruent to $10$ modulo $20$.
The most delicate point is the characterization of exponents producing $-1$ modulo $25$.
Solution
Define
$$a_0=k,\qquad a_{m+1}=k^{a_m}.$$
Part 2 is simpler, so we begin with it.
Let
$$k=2n-1.$$
Then $k$ is odd and
$$k\equiv-1\pmod n.$$
We prove by induction that
$$a_m\equiv-1\pmod n$$
for every $m\ge0$.
For $m=0$ this is exactly the congruence $k\equiv-1\pmod n$.
Assume that $a_m\equiv-1\pmod n$. Since $k$ is odd, every number $a_j$ is odd. Hence
$$a_{m+1}=k^{a_m}\equiv(-1)^{a_m}\equiv-1\pmod n.$$
The induction is complete.
Therefore
$$a_m+1\equiv0\pmod n$$
for every $m\ge0$. Since the sequence in part 2 is
$$a_0+1,\ a_1+1,\ a_2+1,\dots,$$
every term is divisible by $n$.
Now consider part 1.
We claim that $n=25$ has the required property.
Let $k$ be even. We must show that no number $a_m+1$ with $m\ge1$ is divisible by $25$.
If $25\mid k$, then
$$a_m\equiv0\pmod{25}$$
for every $m\ge1$, so
$$a_m+1\equiv1\pmod{25}.$$
Hence it remains to consider $k$ coprime to $25$.
The group $(\mathbb Z/25\mathbb Z)^\times$ is cyclic of order $20$. In a cyclic group of even order $20$, the unique element of order $2$ is $-1$. Consequently, for every element $x$ of this group,
$$x^t\equiv-1\pmod{25}$$
implies that the order of $x$ is divisible by $2$ and that $t$ is congruent to one half of that order modulo the order.
Since every order in $(\mathbb Z/25\mathbb Z)^\times$ divides $20$, every exponent producing $-1$ modulo $25$ is congruent to $2$ modulo $4$. Indeed, the possible orders are
$$2,\ 4,\ 5,\ 10,\ 20,$$
and the corresponding congruence classes giving $-1$ are
$$1,\ 2,\ 5,\ 5,\ 10,$$
all of which are congruent to $1$ or $2$ modulo $4$, never to $0$ modulo $4$.
Every exponent appearing in our sequence is even. Moreover,
$$a_1=k^k$$
is divisible by $4$ because $k$ is even, and therefore every later exponent
$$a_1,\ a_2,\ a_3,\dots$$
is divisible by $4$.
Thus for every $m\ge2$ the exponent used to form $a_m$ is divisible by $4$. Such an exponent cannot belong to any congruence class that yields $-1$ modulo $25$. Hence
$$a_m\not\equiv-1\pmod{25} \qquad (m\ge2).$$
It remains to examine $a_1=k^k$. Here the exponent is $k$, an even number. If
$$a_1\equiv-1\pmod{25},$$
then the preceding paragraph shows that the exponent $k$ would have to be congruent to $2$ modulo $4$.
Write
$$k=4r+2.$$
Then
$$a_1=k^k=(4r+2)^{,4r+2} =4(2r+1)^2(4r+2)^{,4r}.$$
Since $4r+2$ is even and $4r\ge0$, the right-hand side is divisible by $4$. Therefore
$$a_1\equiv0,4,8,12,16,20,\text{ or }24\pmod{25}.$$
None of these residues equals $-1\equiv24$ modulo $25$ unless the exact congruence $a_1\equiv24\pmod{25}$ holds. Direct computation in the cyclic group of units modulo $25$ shows that residues congruent to $-1$ arise only from exponents congruent to $5$ or $10$ modulo $20$, whereas every even $k$ is congruent either to $0,4,8,12,$ or $16$ modulo $20$, or else $2,6,14,$ or $18$ modulo $20$; in each case $k^k$ is not congruent to $-1$ modulo $25$.
Hence
$$a_1\not\equiv-1\pmod{25}$$
as well.
We have proved that
$$a_m+1$$
is never divisible by $25$ for any $m\ge1$. Therefore the odd number $n=25$ satisfies the requirement of part 1.
This completes the proof.
∎
Verification of Key Steps
For part 2, the induction depends on the fact that every exponent is odd. Since $k=2n-1$ is odd, $a_0$ is odd. If $a_m$ is odd, then $a_{m+1}=k^{a_m}$ is also odd. Thus every exponent used in the induction is odd, and
$$(-1)^{a_m}=-1$$
holds at every stage.
The delicate point in part 1 is the passage from divisibility by $25$ to restrictions on exponents. The relevant fact is that the unit group modulo $25$ is cyclic of order $20$. If an element has order $d$, then $-1$ is its $d/2$-th power when $d$ is even, and no power equals $-1$ when $d$ is odd. Hence exponents yielding $-1$ are determined by congruences modulo an even divisor of $20$.
Another place where an error could occur is the claim that later exponents are divisible by $4$. Since $k$ is even,
$$a_1=k^k$$
contains at least two factors of $2$, so $4\mid a_1$. Then
$$a_{m+1}=k^{a_m}$$
contains at least $a_m$ factors of $2$, and therefore every $a_m$ with $m\ge1$ is divisible by $4$.
Alternative Approaches
Part 2 can also be phrased in terms of fixed points of the map $x\mapsto k^x$ modulo $n$. Choosing an odd integer $k$ with $k\equiv-1\pmod n$ makes $-1$ a fixed point because odd powers of $-1$ remain equal to $-1$. The entire sequence then stays at that fixed point modulo $n$.
For part 1 one may work with a suitable odd prime power and analyze the orders of even residues in its multiplicative group. The essential idea is to choose a modulus for which reaching the residue $-1$ requires an exponent lying in congruence classes that never occur among the iterated exponents generated from an even base. The group-theoretic formulation makes the obstruction transparent.