Divisibility Induction $17|18^{(5n+1)}+13^{(4n+1)}+3$

Question

Prove that by induction $17|18^{(5n+1)}+13^{(4n+1)}+3$ for all n∈N.

So far I'm stuck on the proof for n=k+1:

When n=k+1: $$RHS=18^{5k+6}+13^{4k+5}+3$$ $$= (18^{5k+1}+13^{4k+1}+3)+[(18^5-1)18^{5k+1}+(13^4-1)13^{4k+1}]$$

From the assumption n=k, I can prove the first part is divisible by 17, but unsure of how to prove for the second part.

Any help is appreciated.

Edit:word

Answer 1

$17 | (18^5-1)$ and $17 | (13^4-1)$, you can get this by computing these expressions. And after that you have three terms - each divisible by 17 so their sum is alos divisible by 17.

Answer 2

Hint:

$18^5-1=(18-1)( m)=17 m$

$13^4-1=(13^2+1)(13^2-1)=170(168)$

Answer 3

For completeness, here is another way to achieve the same result:

$$RHS=18^{5k+6}+13^{4k+5}+3$$ $$=18^5 \cdot 18^{5k+1}+ 13^4 \cdot 13^{4k+1}+3$$ $$=13^4 \cdot 18^{5k+1}+ 13^4 \cdot 13^{4k+1}+ (18^5-13^4)\cdot 18^{5k+1}+3$$ $$=13^4 (18^{5k+1}+ 13^{4k+1})+ (18^5-13^4)\cdot 18^{5k+1}+3$$ $$=13^4 (18^{5k+1}+ 13^{4k+1})+3\cdot13^4+ (18^5-13^4)\cdot 18^{5k+1}+3-3 \cdot13^{4}$$ $$=13^4 (18^{5k+1}+ 13^{4k+1}+3)+ (18^5-13^4)\cdot 18^{5k+1}+3-3 \cdot13^{4}$$

The first term is divisible by $17$ by the induction hypothesis. The second term is divisible by $17$ because $17$ divides $18^5-13^4 = 1861007$, and the same goes for $3 - 3 \cdot 13^4 = -85680$.

Answer 4

Hint:

If $f(n)=18^{5n+1}+13^{4n+1}+3,$

$f(m+1)-13^4f(m)=18^{5(m+1)+1}-13^418^{5m+1}-3(13^4-1)$

$=((18^5-1)-(13^4-1)18^{5m+1}-3(13^4-1)$

So, it is sufficient to establish $17$ divides $13^4-1,18^5-1$

Answer 5

Just get a calculator and do the math.

$$18^5-1 = 1889567 = 17 \times 111151$$

$$13^4 - 1 = 28560 = 17 \times 1680$$