0

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

  • Hint: Write the assumed divisibility as an equation. Substitute this equation into the RHS of the second expression. – Michael Burr Jan 28 '20 at 00:36
  • @MichaelBurr I cannot separate the terms of RHS to substitute –  Jan 28 '20 at 00:42
  • You don't need to completely separate the terms, just one of them. – Michael Burr Jan 28 '20 at 00:47
  • With modular arithmetic, $17^{2k}+42^{k}+93^{2k+1}\equiv(-2)^{2k}+4^k+(-2)^{2k+1}\equiv4^k-(2)^{2k}\equiv0\bmod19$ – J. W. Tanner Jan 28 '20 at 01:03
  • Note you can multiply the whole thing by either $42$ or $93^2$ or $17^2$ to get a multiple of $19$. then you can adjust the individual terms by noting $93^2 -42$ and $93^2 - 17^2$ and $17^2-42$ are all divisible by $19$. – fleablood Jan 28 '20 at 01:12

5 Answers5

1

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

Will Jagy
  • 139,541
1

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.

lhf
  • 216,483
0

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?

Michael Burr
  • 32,867
  • Thanks so much! I was trying to find multiples of 19 after expanding, didn't realize i could also substitute. –  Jan 28 '20 at 00:59
0

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

J. W. Tanner
  • 60,406
0

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

fleablood
  • 124,253