Proving that $5^n+6^n$ and $5^{n+1}+6^{n+1}$ are coprime for all $n \in \mathbb{N}^*$

Question

I need to prove, using Bézout's identity, that $5^n+6^n$ and $5^{n+1}+6^{n+1}$ are coprime for all $n \in \mathbb{N}^*$. I know that if they are coprime there exist $u,v \in \mathbb{Z}$ such that:

$u(5^n+6^n)+v(5^{n+1}+6^{n+1})=1$,

but I am unsure on how to proceed from here. Any help would be much appreciated.

Answer 1

Let $$a_n=5^n+6^n$$

Since $5,6$ are the roots of $$0=(x-5)(x-6)=x^2-11x+30$$ we deduce that the $a_n$ satisfy the recursion $$a_n=11a_{n-1}-30a_{n-2}\quad a_0=2\quad a_1=11$$

From this it is clear that if any $a_n,a_{n-1}$ have a common factor for any $n$, that factor also divides $a_{n-2}$. (Note: we have $\gcd(a_n,30)=1$ for all $n$ so we can disregard the coefficient of the $a_{n-2}$ term). Since $a_0,a_1$ have no common factors, we are done.

Answer 2

Hint $ $ By Euclid: $(a\!+\!b,\,5a\!+\!6b) = (a\!+\!b,\,5a\!+\!6b-5(a\!+\!b)) = (a\!+\!b,\,b) = (a,b)$

Answer 3

You want Bezout's identity? Here is one.

$(6^n,5^n)=1$,so integers $s,t$ exist such that $s*6^n+t*5^n=1$.

Then we have $(s-t)(6^{n+1}+5^{n+1})+(-5s+6t)(6^n+5^n)=1$

Answer 4

You can also do it as, let $d_n=(5^n+6^n,5^{n+1}+6^{n+1})$. Since $d_n\mid 5^n+6^n$, $d_n\mid 5^{n+1}+5\cdot 6^n$, hence, $d_n\mid 5^{n+1}+6^{n+1}-(5^{n+1}+5\cdot 6^n)=6^n$. If $p\mid d_n$ a prime, then $p\in\{2,3\}$. Now, run the same argument, this time noticing $d_n\mid (6\cdot 5^n+6^{n+1})-(5^{n+1}+6^{n+1})=5^n$, hence, any $p\mid d_n$ satisfy $p\in\{5\}$, contradiction.