3

I tried to demonstrate the next equation is divisible by 19:

$$ 2^{2^{n}} + 3^{2^{n}} + 5^{2^{n}} $$

When $n$ is $1$:

$$ 2^{2^1} + 3^{2^1} + 5^{2^1} $$ $$ 4 + 9 + 25 = 38 $$

When $n$ is $k$:

$$ 2^{2^k} + 3^{2^k} + 5^{2^k} $$

Finally, when $n$ is $k+1$:

$$ 2^{2^{k+1}} + 3^{2^{k+1}} + 5^{2^{k+1}} $$

I try by expanding, by subtraction, but no solution /:

Michael Hardy
  • 1
jtwalters
  • 155

3 Answers3

3

Hint: $$2^{n+6}+3^{n+6}+5^{n+6}=2^6\cdot2^n+3^6\cdot 3^n+5^6\cdot5^n\equiv7\cdot2^n+7\cdot3^n+7\cdot5^n\ \ (\text{mod }19)$$

What can $2^k\text{ mod }6$ be?

user2345215
  • 16,422
  • Really, I don't understand, how you got $2^{n+6}$ and how the last step prove that? – jtwalters Apr 07 '14 at 23:43
  • @JettT: You don't prove it by induction directly. Instead prove it holds for all $2^{2+6k}+3^{2+6k}+5^{2+6k}$ and you need just a little bit more. – user2345215 Apr 07 '14 at 23:45
  • Mmm... but i don't use $2^k$, I use $2^{2^k}$ – jtwalters Apr 07 '14 at 23:51
  • @JettT Start with $5$ as the $2$'s are clearly confusing you. Instead of $5^{2^k}!+!\ldots$ prove $5^{2+6k}!+!\ldots$ and $5^{4+6k}!+!\ldots$. It follows from that. – user2345215 Apr 07 '14 at 23:53
  • Yeah, I'm really confusing with this problem (so hard for me), but if I prove $5^{2+6k}$ why is the same to $5^{2^k}$? – jtwalters Apr 07 '14 at 23:59
  • @JettT Because $2^{\text{odd}}-2$ is divisible by $6$ and $2^{\text{even}}-4$ is divisible by $6$ too. You can prove this by induction if you want. – user2345215 Apr 08 '14 at 00:02
  • My god, I'm sorry but I dont undestand /: Is complex... – jtwalters Apr 08 '14 at 00:23
1

Not with induction:

The residues of each term cycle since $a^{2^{n+1}} = (a^{2^n})^2$

$2^{2^n} \pmod {19}$ with $4, 16, 9, 5, 6, 17, 4, \dots$

$3^{2^n} \pmod {19}$ with $9, 5, 6, 17, 4, 16, 9, \dots$

$5^{2^n} \pmod {19}$ with $6, 17, 4, 16, 9, 5, 6, \dots$

By adding terms pairwise, you can see that the statement is true. This also provides some motivation for induction using $k+6$ rather than $k+1$.

MT_
  • 19,603
  • 9
  • 40
  • 81
  • And it's legal to use $k+6$ underside $k+1$ ? – jtwalters Apr 07 '14 at 23:48
  • 1
    So long as you do base cases for $n = 1, 2, 3, 4, 5, 6$. If we know $n = 1$ works, then by the inductive proof, we know $n = 1, 7, 13, \dots$ all work. Same goes for $2, 3, 4, 5, 6$, so we have thus covered all possibilities. – MT_ Apr 07 '14 at 23:53
  • Oh, so, in induction if I prove $k+6$ I prove all the combinations? And what happend for $1,2,3,4,5$ ? – jtwalters Apr 08 '14 at 00:03
  • 1
    You seem to not understand the theory behind induction. When we use $k + 1$ and have a base case of $n = 1$, we say that, if we were to plug in $k = 1$ into our inductive formula, we will then know that it holds for $k = 2$. Since it holds for $k = 2$, if we plug $k = 2$ into the inductive formula we will then know that it holds for $k = 3$. This goes ad infinitum, so it holds for all $k$. – MT_ Apr 08 '14 at 00:20
  • Well my math profesor isn't good for explain, but in a video I view we use the $k+1$ because when we prove $n=1$ is corrent and we prove $k+1$ we can use recursivity to demostrate is correct in $1,2,3,4,5,...,\infty$. But if we use $k+6$ we only demostrate $1,7,13,...,\infty$ ?? but the others numbers? – jtwalters Apr 08 '14 at 00:30
  • 1
    @JettT that's why we need six base cases. $n = 1$ establishes $1, 7, 13, \dots$. $n = 2$ establishes $2, 8, 14, \dots$. $n = 3$ establishes $3, 9, 15, \dots,$, ... $n = 6$ establishes $6, 12, 18, \dots$, so we have thus shown it to be true for all $n \geq 1$. – MT_ Apr 08 '14 at 01:05
  • Ohh!! OMG, you are god eh! I prove the modules in another (more simples) examples and I see that is true. I got a question! If i prove all the base cases $n = 1,2,3,4,5,6$, to stay 100% secure if that is true I need prove $k+6$ ?? – jtwalters Apr 08 '14 at 02:11
  • 1
    To complete induction in this case, you need to show the $k + 6$ case and show all six base cases, yes. – MT_ Apr 08 '14 at 02:16
  • Nice! I'll go to write all! – jtwalters Apr 08 '14 at 02:20
1

By Fermat's little theorem, if $n\equiv m\ \ \text{mod}\ (p-1)$, then $a^m \equiv a^n\ \ \text{mod}\ p$. Now, since any power of two modulo $18$ is one of the six numbers in $S=\{2,4,8,10,14,16\}$, it remains to check that: $$2^k+3^k+5^k \equiv 0 \ \ \text{mod}\ 19$$ For all $k\in S$.

Nathaniel Bubis
  • 33,018