Prove that the number $19\cdot8^n+17$ is not prime, $n\in\mathbb{Z}^+$

Solution 1:

If $n\equiv 1\pmod {4}$, then $8^n\equiv 8\pmod {13}$ and so $$19\cdot 8^n+17\equiv 19\cdot 8 + 17\equiv 0\pmod {13}$$

If $n\equiv 3\pmod{4}$, then $8^n\equiv 2\pmod {5}$ and so $$19\cdot 8^n + 17\equiv 19\cdot 2 + 17\equiv 0\pmod {5}$$

If $n$ is even, then $19\cdot 8^n + 17$ is divisible by $3$.

And clearly $19\cdot 8^n + 17>13, \forall n\in\mathbb Z^+$.

Solution 2:

Hint $\ $ Looking at the prime factorizations of the first $\,\color{#c00}4\,$ elements we notice the following.

$ 8^{\large\color{#c00}4}\!-1 = 3^2\cdot 5\cdot 7\cdot 13 = \prod p_i ,\,$ and some prime $\,p_i\mid f_K\! = 19\cdot 8^{K}\!+17\,$ for all $\,K <\color{#c00} 4,\,$ therefore some $\,p_i\mid f_N\,$ for all $\,N,\,$ so $\,f_N\,$ is composite for all $\,N\ge 0.\,$

Proof $\ $ Dividing $\,N\,$ by $\,4\,$ yields $\,N = K\!+4J\,$ for $\,K < 4.\ $ By hypothesis some $\,p = p_i\mid f_K$

${\rm mod}\ p\!:\,\ \color{#c00}{8^{ 4}}\equiv\color{#c00} 1\,\Rightarrow\, \color{#0a0}{8^N} \equiv 8^{K+4J}\!\equiv 8^K(\color{#c00}{8^4})^J\equiv 8^K\color{#c00}1^J\equiv \color{#0a0}{8^K}\ $ by $ $ Congruence Rules.

$p\mid f_K\Rightarrow\, 0\equiv 19\cdot \color{#0a0}{8^K}\!+17\equiv 19\cdot \color{#0a0}{8^N}\!+17 \equiv f_N\Rightarrow p\mid f_N,\,$ properly by $\,p < f_4 \le f_N$

Remark $\ $ This is a typical application of covering congruences. See also this question, and see this question for a polynomial analog, and a link to a paper of Schinzel.