Initially a number $6$ is written on a blackboard. At $n$-th step an integer $k$ on the blackboard is replaced by $k+gcd(k,n)$. Prove that at each step the number on the blackboard increases either by $1$ or by a prime number.
Problem
Source:
Tags: GCD, number theory, prime
SnowPanda
19.01.2022 04:54
The first step is $6 \to 7$, the second step is $7 \to 8$, and the third step is $8 \to 9$.
Claim: Suppose that after step $n$, the number on the blackboard is $3n$. Then if the number next increases by more than $1$ on step $m$, it increases by a prime and becomes $3m$.
Proof. We have that $m$ is the smallest integer greater than $n$ for which \[\gcd(m, 3n + m - n - 1) = \gcd(m, 2n - 1) > 1.\]But if $p$ is any prime dividing $2n - 1$, then $n \equiv \tfrac{p + 1}{2} \pmod{p}$, so the smallest $m > n$ with $p \mid m$ is \[m = n + \frac{p - 1}{2}.\]So then the first $m$ for which the gcd is not $1$ is $m = n + \tfrac{p - 1}{2}$ where $p$ is the smallest prime dividing $2n - 1$, and here the gcd is \[\gcd(2n + p - 1, 2n - 1) = p.\]So step $m$ is \[3n + \tfrac{p - 1}{2} - 1 \to 3n + \tfrac{p - 1}{2} - 1 + p = 3m,\]as desired. $\blacksquare$
Since after step $3$ the number is $3\cdot 3$, by induction this means all additions are $1$ or prime, and each prime addition results in $3m$ on the board after turn $m$.