# Prove that gcd between two consecutive terms in a sequence is constant (and find it)

I've stumble across the following exercise in a test. I'm trying to solve it but I need some help.

Let $$(a_n)_{n \in \Bbb N}$$ be the sequence defined as: $$a_1 = 14$$ $$a_{n+1}=5 a_n - 6$$ Prove that the gcd between two consecutive terms is constant and find its value.

For instance by checking the first terms of the sequence I've come up with 2 as a common factor. I can prove this by induction:

$$P(n) = 2 \mid a_n$$

$$P(1) = 2 \mid 14$$

$$P(n) \implies P(n+1)$$:

$$2\mid 5 a_n - 6$$

As 2 divides 6 it must be that 2 divides $$a_n$$ because it does not divide 5, and so it happens to be my hypothesis.

The same way I've proved that 4 doesn't divide $$a_n$$ so 1 is the highest power of 2 that divides the sequence.

Then I've tried to find the $$\gcd$$ doing as above for two consecutive terms of the sequence and with a generic $$\gcd=d$$:

$$\gcd(a_n, a_{n+1})=\gcd(a_n, 5 a_n - 6)=d$$

$$d\mid 5 a_n - 6$$

As d divides $$a_n$$ it must be that it also divides 6, then the possible values are 1,2,3,6.

I can see that the only one that is common to my previous assumptions is 2. But I can't put all the information together. Any suggestions will be helpful, thanks!

If $d\mid a_n$, and $d\mid a_{n+1}=5a_n-6$, then $d\mid 6a_n-6=6(a_n-1)$. Now let $d=ij$, such that $i\mid 6$ and $j\mid a_n-1$. Note that $j\mid d\mid a_n$ and since $j\mid a_n-1$, we know $j=1$. Thus, $d=ij=i$ so that $d\mid 6$.

It is clear that $2\mid a_n$ (easy with induction; $2\mid a_1$, and $2\mid a_n$ means $2\mid 5a_n-6=a_{n+1}$). We also know $a_0\equiv 2\mod 3$. Assume now $a_n\equiv 2\mod 3$; then $5a_n\equiv 1\mod 3$ so that $5a_n-6\equiv a_{n+1}\equiv 1\mod 3$. Now $5a_{n+1}\equiv 2\mod 3$ meaning $5a_{n+1}-6\equiv a_{n+2}\equiv 2\mod 3$, so that $a_n$ is never divisible by $3$.

Thus, the $\gcd$ is constant and equal to $2$.

You can prove by induction that $3 \nmid a_n$ for all $n$.

Base case: $3 \nmid 14$.

Induction hypothesis: $3 \nmid a_n$.

Induction step: Suppose $3 \mid a_{n+1}$, then $3 \mid 5a_n-6$, hence $3 \mid 5a_n$ and hence $3 \mid a_n$.
This contradicts the induction hypothesis that $3 \nmid a_n$

Hence $3$ is not a factor of $\gcd(a_n,a_{n+1})$, and $\gcd(a_n,a_{n+1}) \mid 2$.

Since you already showed that $2$ is a divisior of all $a_n$, you are done.