Divisibility using induction

Question

Want to show $$17^{2k} + 42^k + 93^{2k+1}$$

is divisible by 19 for every natural number k.

I started with induction and showed base case when $$k =1$$

Then the induction hypothesis : Let this be true$$19 | 17^{2k} + 42^k + 93^{2k+1}$$

Induction Step: To prove $$19|17^{2k+2} + 42^{k+1} + 93^{2k+3}$$

I cannot figure how to simply the equation is multiples of 19

Answer 1

Idea: Even if a problem doesn't appear solvable, always try to rewrite the given information by expanding definitions and see where it leads you.

Since $19\mid 17^{2k}+42^k+93^{2k+1}$ is assumed to be true, from the definition of divisibility, there is some integer $n$ such that $$ 19n=17^{2k}+42^k+93^{2k+1}. $$ Rewriting this, we have $$ 93^{2k+1}=19n-17^{2k}-42^k. $$

Now, we observe that $17^{2k+2}+42^{k+1}+93^{2k+3}$ can be rewritten as \begin{align*} 17^{2k+2}+42^{k+1}+93^{2k+3}&=17^{2k+2}+42^{k+1}+93^2(93^{2k+1})\\ &=17^{2k+2}+42^{k+1}+93^2(19n-17^{2k}-42^k)\\ &=19(93^2n)+42^k(42-93^2)+17^{2k}(17^2-93^2)\\ &=19(93^2n)-19(453\cdot 42^k)-19(440\cdot 17^{2k}) \end{align*}

Can you complete it from here?

Answer 2

$$ 17^2 = 289 \equiv 4 \pmod {19} $$ $$ 42 \equiv 4 \pmod {19} $$ $$ 93 \equiv 17 \pmod {19} $$ $$ 93^2 \equiv 17^2 = 289 \equiv 4 \pmod {19} $$

The equation becomes $$ 4^k + 4^k + 17 \cdot 4^k \equiv 0 \pmod {19} $$ Which is just true, $$ (1 + 1 + 17) \cdot 4^k \equiv 0 \pmod {19} $$

Answer 3

Let $a_k=17^{2k} + 42^k + 93^{2k+1} = (17^2)^k + 42^k + 93 \cdot (93^2)^k$.

Let $x^3 = b_2 x^2 + b_1 x + b_0$ be the monic cubic equation having as roots $17^2$, $42$, $93^2$. Note that $b_2,b_1,b_0$ are integers.

Then $a_{k+3} = b_2 a_{k+2} + b_1 a_{k+1} + b_0 a_k$.

Thus, the claim follows by induction as soon as it is true for the base cases $a_0,a_1,a_2$, which should be simple to check. To avoid large numbers, it suffices to consider everything mod $19$.

This approach needs no spark of algebraic manipulation genius for proving inductions steps. It just explores the fact that linear combinations of geometric progressions satisfy linear recurrences.

Answer 4

Hints:

$17^{2k+2}+42^{k+1}+93^{2k+3}=17^2\cdot17^{2k}+42\cdot42^k+93^293^{2k+1}$

$=42(17^{2k}+42^k+93^{2k+1})+(17^2-42)17^{2k}+(93^2-42)93^{2k+1}$

and $17\equiv93\equiv-2\bmod19$ and $42\equiv(-2)^2\bmod 19.$

Answer 5

$17^{2k} + 42^{k} + 93^{2k+1}$ is divisible by $19$.

So $(17^{2k} + 42^{k} + 93^{2k+1})*93^2= 17^{2k}*93^2 + 42^{k}*93^2 + 93^{2k+3}$ is divisible by $19$.

$93^2 - 17^2 = (93+17)(93-17)=110*76 = 110*(19*4)$ is divisible by $19$, so

$17^{2k}*93^2- 17^{2k}(93^2 - 17^2) + 42^{k}*93^2 + 93^{2k+3}= $

$17^{2k}*17^{2k} + 42^{k}*93^2 + 93^{2k+3}=$

$17^{2k+2} + 42^{k}*93^2 + 93^{2k+3}$ is divisible by $19$.

And $93^2 - 42 =$ well, I have no idea but that must be divisible by $19$ some how.... $93 = 5*19 - 2$ so $93^2 - 42 = (5*19-2)^2 - 42=25*19^2- 20*19 + 4-42=19*K +38 = 19*K + 2*19$ is divisible by $19$.

So

$17^{2k+2} + 42^{k}*93^2- 42^k(93^2- 42) + 93^{2k+3}=$

$17^{2k+2} + 42^k*42 + + 93^{2k+3}=$

$17^{2k+2} + 42^{k+1} + + 93^{2k+3}$ is divisible by $19$