1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.