It appears that $a_3=5\cdot 2-6\cdot 1=4$, so $\gcd(a_2,a_3)>1$....

There must be a mistake in the problem because the recursion has the solution $a_n=2^{n-1}$.

Easy to see that $a_n=2^n+3^n$. In particular, $a_n$ is coprime to $6$. a) Suppose that $d \mid a_n,a_{n+1}$ for some $n$. Then $d \mid 5a_n-a_{n+1}=6a_{n-1}$. But $d$ is coprime to $6$, so $d \mid a_{n-1}$. So by induction we must have $d \mid a_1,a_2$ and hence $d \mid (5,13)=1$. b) Let $p$ be a prime factor of $a_{2^k}$. Note that $p \ne 2,3$. So $p \mid 2^{2^k}+3^{2^k}$. So $\left(\frac{2}{3}\right)^{2^k} \equiv -1 \mod p$. So the order of $\frac{2}{3}$ modulo $p$ is $2^{k+1}$. But the order divides $p-1$ by Little Fermat and we are done.

Tintarn wrote: So $p \mid 2^{2^k}+3^{2^k}$. So $\left(\frac{2}{3}\right)^{2^k} \equiv -1 \mod p$. Why is this true?

Because $(3;p)=1 \implies $ exist $m$ such that: $3m \equiv 1 \pmod p$ $\implies p|(2m)^{2^k}+(3m)^{2^k} \iff p|(2m)^{2^k}+1 \iff \left(\frac{2}{3}\right)^{2^k} \equiv (2m)^{2^k} \equiv -1 \pmod p$

Here is my solution for this problem Solution a) It's easy to see that: $a_n = 2^n + 3^n, \forall n \in \mathbb{N}$ Let $d_n = \gcd(a_n; a_{n + 1}), \forall n \in \mathbb{N}$ Then: $d_n | \gcd(3a_n - a_{n + 1}; a_{n + 1} - 2a_n)$ or $d_n | \gcd(2^n; 3^n)$ Hence: $d_n = 1$ or $\gcd(a_n; a_{n + 1}) = 1$ b) Since: $p$ is a prime factor of $a_{2^k} = 2^{2^k} + 3^{2^k}$, we have: $\gcd(p; 2) = \gcd(p; 3) = 1$ So there exists $x \in \mathbb{Z}$ such as $3x \equiv 1$ (mod $p$) Then: $(2x)^{2^k} \equiv - (3x)^{2^k} \equiv - 1$ (mod $p$) or $(2x)^{2^{k + 1}} \equiv 1$ (mod $p$) By Fermat little theorem, we have: $(2x)^{p - 1} \equiv 1$ (mod $p$) Let $h = \text{ord}_p(2)$ so: $h | 2^{k + 1}$ and $h | p - 1$ If $h \le 2^k$ then: $p | (2x)^h - 1 | (2x)^{2^k} - 1$ But: $(2x)^{2^k} \equiv - 1$ (mod $p$) hence: $p | 2$, which is a contradiction Then: $h = 2^{k + 1}$ or $2^{k + 1} | p - 1$

The solution for part a This is just a simple recurrence relation, when solving this part we have that the characteristic polynomial is: $$t^2-5t+6=0$$$$\left(t-3\right)\left(t-2\right)=0$$$$t \in \left\{ 3,2\right\}$$From here we have that: $$a_n = A.2^n+B.3^n$$From the conditions we have that $A=B=1$. Now plugging in $a_n=2^n+3^n$, we get: $$\left(a_{n+1},a_n\right)=\left(2^{n+1}+3^{n+1},2^n+3^n\right)=\left(2^{n+1}+3^{n+1}-2^{n+1}-2.3^{n}\right)=\left(3^n,2^n+3^n\right)=1$$The solution for part b Let $p$ divide $a_{2^k}$, from here we have that $2^{2^k} \equiv -3^{2^k} \; (mod \; p)$, since $p \notin \left\{ 2,3\right\}$, we have that: $$\left(\frac{2}{3}\right)^{2^k} \equiv -1 \; (mod \; p)$$Since every element (except $0$) of the group $\mathbb{Z}/p\mathbb{Z}$ has a unique inverse we have that, there exists an $m$ such that $3m \equiv 1 \; (mod \; p)$. we have that: $$\left(2m\right)^{2^k} \equiv -1 \; (mod \; p) \implies \left(2m\right)^{2^{k+1}} \equiv 1 \; (mod \; p)$$As said before every element of the group $\mathbb{Z}/p\mathbb{Z}$ has an unique inverse, that means that $m$ isn't the inverse of $2$. Now denote by $g=ord_p(2m)$, we have that: $$g \mid 2^{k+1}$$and as usual by FLT we have that $g \mid p-1$. Now let's say that $g \leq 2^k$, from here we have that: $$p \mid \left(2m\right)^{g}-1 \mid \left(2m\right)^{2^k}-1$$this holds since $g$ is a power of $2$. From here we have that $\left(2m\right) \equiv 1 \; (mod \; p)$, a clear contradiction. So we got that $g = 2^{k+1}$, which implies $2^{k+1} \mid p-1$.

Nice Problem! trito11 wrote: Let a sequence $(a_n)$ satisfy: $a_1=5,a_2=13$ and $a_{n+1}=5a_n-6a_{n-1},\forall n\ge2$ a) Prove that $(a_n, a_{n+1})=1,\forall n\ge1$ b) Prove that: $2^{k+1}|p-1\forall k\in\mathbb{N}$, if p is a prime factor of $a_{2^k}$ Claim :$a_n=2^n+3^n$ Proof :Induction, $$a_n=5a_{n-1}-6a_{n-2}=5.2^{n-1}+5.3^{n-1}-6.2^{n-2}-6.3^{n-2}=2.2^{n-1}+3.3^{n-1}=2^n+3^n$$Part a is trivial now(It could also be done with induction without using the above claim). Part (b) We have $p$ such that $p$ is a prime and $p|a_{2^k}=2^{2^k}+3^{2^k}$ or, $$\stackrel{\text{By Euler}}\implies \text{ord}_p\{\frac{2}{3}\}|\text{gcd}(2^{k+1},p-1) \stackrel{\text{By a standard argument}}\implies \text{ord}_p\{\frac{2}{3}\}=2^{k+1} \implies 2^{k+1}|p-1$$The End $\blacksquare$