# Is it a composite number? [duplicate]

How do I prove $19\cdot8^n+17$ is a composite number?

Or is that number just a prime?

So I tried to find a divisor in the cases $n = 2k$ and $n = 2k + 1$. But I had no success.

Do you have any ideas?

• Hint $\$ Do a covering congruence argument as in this answer. Jun 17, 2015 at 15:03
• @BillDubuque Hagen's answer is essentially a duplicate of your answer there. Jun 17, 2015 at 15:39
• @user26486 Indeed. I didn't notice before that they are exactly the same numbers. Readers may find of interest the paper of Schinzel linked there. Jun 17, 2015 at 15:42

Three cases:

• $n$ is even. Then $$19\cdot 8^n+17\equiv 1\cdot (-1)^n+17\equiv 1+17\equiv 0\pmod{\! 3}$$

• $n=4k+1$ for some $k\in\Bbb Z_{\ge 0}$. Then $$19\cdot 8^{4k+1}+17\equiv 6\cdot \left(8^2\right)^{2k}\cdot 8+4\equiv 6\cdot (-1)^{2k}\cdot 8+4$$

$$\equiv 48+4\equiv 52\equiv 0\pmod{\! 13}$$

• $n=4k+3$ for some $k\in\Bbb Z_{\ge 0}$. Then $$19\cdot 8^{4k+3}+17\equiv (-1)\cdot \left(8^2\right)^{2k}\cdot 8^3+17\equiv (-1)\cdot (-1)^{2k}\cdot 8^3+17$$

$$\equiv -(-2)^3+17\equiv 8+17\equiv 25\equiv 0\pmod{\! 5}$$

• Impressive, but can you indicate how you came up with these divisors, and with (mod 4) for the cases? Jun 17, 2015 at 13:16
• @alexis Hagen clearly shows the reasoning you can use to come up with this solution. Jun 17, 2015 at 13:29
• Thanks, just upvoted Hagen's answer. Jun 17, 2015 at 13:29

Note that $8^4\equiv 1\pmod{3^2\cdot 5\cdot 7\cdot 13}$. Thus if you find a divisor $\in\{3,5,7,13\}$ for $n=r$, then the same divisor works for $n=4k+r$. So check $r=0,1,2,3$ for these divisors. (Clearly, $19\cdot 8^n+17>13$ so these divisors are proper).