Kvant Math Problem 512

Compute the first few values of $f$ for small natural numbers greater than $1$.

kvantmathematicsolympiad

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

Problem

Let $f(x)=x^3-x+1$. Prove that for every natural number $m\gt1$, the numbers $m$, $f(m)$, $f(f(m))$, $f(f(f(m)))$, $\ldots$ are pairwise relatively prime.

A. T. Kolotov

All-Union Mathematical Olympiad for School Students (XII, 1978, Grade 10)

Exploration

Compute the first few values of $f$ for small natural numbers greater than $1$. For $m=2$, $f(2)=2^3-2+1=7$, $f(f(2))=f(7)=343-7+1=337$, $f(f(f(2)))=f(337)=337^3-337+1$, which is enormous. None of these numbers share obvious small prime factors. For $m=3$, $f(3)=27-3+1=25$, $f(f(3))=f(25)=15625-25+1=15601$, again seemingly coprime to 3 and 25. These calculations suggest a recursive pattern: if two numbers $f^k(m)$ and $f^l(m)$ had a common prime factor, it would satisfy a certain congruence, which seems difficult. The key step likely involves showing that a prime dividing both $f^k(m)$ and $f^l(m)$ leads to a contradiction modulo that prime.

Problem Understanding

The problem asks to prove that for any natural number $m>1$, the sequence

$m, f(m), f(f(m)), f(f(f(m))), \dots$

is pairwise relatively prime. This is a Type B problem since a specific statement is given to prove. The core difficulty is showing that if a prime $p$ divides both $f^k(m)$ and $f^l(m)$ for $k<l$, this leads to a contradiction. The intuitive reason the statement should hold is that the cubic map $x \mapsto x^3 - x + 1$ rapidly produces numbers with differing residues modulo any fixed prime, preventing repeated factors.

Proof Architecture

Lemma 1: If a prime $p$ divides both $f(a)$ and $f(b)$, then $f(a) \equiv f(b) \pmod p$ implies $a \equiv b \pmod p$ or $a \equiv b^{-1} \pmod p$ is impossible. Sketch: Consider the equation $f(x) \equiv f(y) \pmod p$ and factor it.

Lemma 2: If $p$ divides both $f^k(m)$ and $f^l(m)$ with $k<l$, then $p$ divides $f^{l-k}(f^k(m)) - f^k(m)$, which reduces to $f^n(x)-x$ for some $n$, leading to a polynomial congruence with no nontrivial solutions modulo $p$. Sketch: Iteratively reduce the problem using the functional equation.

Hardest direction: proving that $f^n(x) \equiv x \pmod p$ has no solution for $x$ divisible by $p$ and $n \ge 1$. This is most likely to fail if one assumes divisibility propagates without checking congruence conditions.

Solution

Assume for contradiction that there exists a natural number $m>1$ and two distinct indices $k<l$ such that $f^k(m)$ and $f^l(m)$ share a common prime factor $p$. Let $a=f^k(m)$ and $b=f^l(m)=f^{l-k}(a)$. Then $p \mid a$ and $p \mid f^{l-k}(a)$. Write $f(x)=x^3-x+1$, then $f^{l-k}(a) \equiv 0 \pmod p$.

Consider the congruence $f(x) \equiv 0 \pmod p$ with $x \equiv 0 \pmod p$. Then $f(x) = x^3 - x + 1 \equiv 1 \pmod p$. Therefore $f(a) \equiv 1 \not\equiv 0 \pmod p$, contradicting $p \mid f(a)$. More generally, suppose $p \mid f^n(a)$ for some $n \ge 1$, then $f(f^{n-1}(a)) \equiv 1 \pmod p$, because $f(0) \equiv 1 \pmod p$.

We now prove by induction on $n$ that for any integer $x$, if $p \mid x$, then $f^n(x) \equiv 1 \pmod p$ for all $n \ge 1$. The base case $n=1$ is $f(x) \equiv 1 \pmod p$. Assume $f^n(x) \equiv 1 \pmod p$, then $f^{n+1}(x) = f(f^n(x)) \equiv f(1) = 1^3 -1 +1 = 1 \pmod p$. Hence, the induction holds.

Applying this to $x=a=f^k(m)$, since $p \mid a$, we have $f^{l-k}(a) \equiv 1 \not\equiv 0 \pmod p$, a contradiction. Therefore no two distinct elements of the sequence share a common prime factor, and the numbers $m$, $f(m)$, $f(f(m))$, $f(f(f(m)))$, $\dots$ are pairwise relatively prime.

This completes the proof.

∎

Verification of Key Steps

The critical step is showing that if $p \mid a$, then $f(a) \equiv 1 \pmod p$. Test with $p=2$, $a=2$, $f(2)=7 \equiv 1 \pmod 2$. With $p=3$, $a=3$, $f(3)=25 \equiv 1 \pmod 3$. These confirm the induction base case. The inductive step is trivial because $f(1) = 1$, ensuring the congruence remains correct. Another subtlety is ensuring that $k<l$ implies $n = l-k \ge 1$, which is properly accounted for.

Alternative Approaches

An alternative approach is to consider the difference $f(x)-f(y) = (x-y)(x^2 + xy + y^2 -1)$ and show that if a prime divides two distinct sequence elements, it must divide a factorization of this form. Then one can argue that the second factor is never zero modulo $p$, forcing $x \equiv y \equiv 0 \pmod p$, reducing to the same argument as above. This approach is more algebraically explicit, but the induction-based congruence method is more direct and generalizes easily to any natural starting value $m$.