Prove that the number $19\cdot8^n+17$ is not prime, $n\in\mathbb{Z}^+$ On a Google search, I've notice that often the "trick" involves factoring the expression (and thus showing that the expression isn't prime), but I can't see it. Is this how you would go about it in this case, or would that be a dead end? Any hints?
 A: 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^+$.
A: 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 prototypical application of covering congruences.  See also this question, and see this question for a polynomial analog, and a link to a paper of Schinzel.
A: Not sure whether this qualifies for it as answer but if you reduce it mod $3$ you can see that the expression is divisible by $3$ if $n$ is even.
If you reduce it mod $13$ then you see that the expression is divisible by $13$ if $n \equiv 1$ mod $4$. ($8^4 \equiv 1$ mod $13$ )
If you reduce it mod $5$ then the expression is divisible by $5$ if $n$ is $3$ mod $4$.
I sort of calculated a few numbers and then tried some numbers. I don't think this is a good way at all but I guess it works.
