3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Hint $\ $ Do a covering congruence argument as in this answer. $\endgroup$ Jun 17, 2015 at 15:03
  • $\begingroup$ @BillDubuque Hagen's answer is essentially a duplicate of your answer there. $\endgroup$
    – user26486
    Jun 17, 2015 at 15:39
  • $\begingroup$ @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. $\endgroup$ Jun 17, 2015 at 15:42

2 Answers 2

12
$\begingroup$

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}$$

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

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).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.