A number theory problem by Pi Han Goh

Before we begin, let's insert the recurrence relation for $a_{n+1}$ into $b_n$ to get $\begin{aligned} b_n&=\gcd(n+1,\:a_{n}),&&& a_1&=7\\[.5em] a_{n+1}&=a_{n}+b_n \end{aligned}$

We need to prove that $\gcd(..)$ is either $1$ or a prime for all $n$ ! However, the sequence $a_n$ has no obvious symmetry or periods. It increases by (at least) one at every step because of $\gcd(..)\geq 1$ but that's it. Let's take a look at the first few elements of both sequences. For those values, $b_n$ is not a composite number. $\begin{array}{ r | r r r r r r r r r r r r r r} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & \cdots\\ \hline a_n & 7 & 8 & 9 & 10 & \red{15} & \red{18} & 19 & 20 & 21 & 22 & \red{33} & \red{24} & 23 &\\[.5em] b_n & 1 & 1 & 1 & \green{5} & \green{3} & 1 & 1 & 1 & 1 & \green{11} & \green{3} & 1 & 1 \end{array}$

---

Notice that when $\red{a_n}$ increases by more than one, it always increase to $\red{a_n=3n}$ ? And how $\green{b_{n}>1}$ only around those values? Let's formalise these discoveries in the following

Proposition: The following assumptions are true: $\begin{aligned} n&\geq 2:&a_n&\in\{a_{n-1}+1;\:3n\},&&&&&b_n&\in\{1,\:p_n\}&\text{for some primes }p_n \end{aligned}$

Before we begin the proof, let's recall a useful property of the gcd we will use quite a few times: $\begin{aligned} \gcd(x,\:y)&=\gcd(x,\:mx+y)=\gcd(x,\:mx-y),&&x,\:y,\:m\in\mathbb{Z}&&&&(*) \end{aligned}$

Proof: We prove both statements by one induction. Looking at the table, they are true until $a_n=3n$ (e.g. at $n=5$ ). Let's see what happens to $b_n$ at this step: $\begin{aligned} b_n&=\gcd(n+1,\:3n)\underset{(*)}=\gcd(n+1,\:3)\in\{1;\:3\}&\Rightarrow&& a_{n+1}&=3n+b_n\in\{a_n+1;\:3n+3\} \end{aligned}$ If $b_n=3$ , we are done. Otherwise, let $1\leq i$ be the number of iterations such that $b_n$ equals one: $\begin{aligned} b_{n}&=\ldots=b_{n+i-1}=1,&b_{n+i}&>1,&&&&&a_n&=3n&\Rightarrow&&a_{n+j}=3n+j,&&&&1\leq j \leq i \end{aligned}$ $\begin{aligned} \Rightarrow&&b_{n+j-1}&=\gcd(n+j,\:3n+j-1)\underset{(*)}{=}\gcd(n+j,\:2n-1)=1,&&&& 1\leq j\leq i \end{aligned}$ We notice that $2n-1$ is coprime to $i$ consecutive integers. Then it cannot have any factor $1<q\leq i$ , because one of those consecutive integers would be a multiple of $q$ and thus not be coprime to $2n-1$ : $\begin{aligned} \gcd(n+j,\:2n-1)&=1,&1&\leq j\leq i&\Rightarrow && \gcd(q,\:2n-1)&=1,&1&<q\leq i \end{aligned}$

Consider the values $b_{n+i}>1$ can take. As a factor of $2n-1$ , it also cannot have any odd factor $1<q\leq i$ : $\begin{aligned} b_{n+i}&=\gcd(n+i+1,\:2n-1)\underset{(*)}{=}\gcd(n+i+1,\:2i+3)\leq 2i+3 \end{aligned}$ But $b_{n+i}$ also has no more than one odd factor $q>i$ - if it had, we get a contradiction: $\begin{aligned} p,\:q&>i\geq1\text{ odd}&\Rightarrow&& pq\geq 3(i+1)>2i+3\geq b_{n+i}\neq pq&&(**) \end{aligned}$ We have shown that $b_{n+i}$ has no factor $1< q\leq i$ and (at most) one factor $q>i$ , so it can be only one or an odd prime! Using the same argument as in $(**)$ , we find $b_{n+i}=2i+3$ and $a_{n+i+1}=3(n+i+1)\quad\square$