6

Okay so ive been trying to prove this for about 5 hours... really need salvation from the geniouses around here.

prove by induction $7\mid 3^{3^n}+8$ i really need some directions on what to do here...

Michael Hardy
  • 1
Tal
  • 315
  • Start with the base case $n=1$, then assume it holds for $n$ and try to show that consequently it also holds for $n+1$. – Hakim Aug 02 '14 at 22:15
  • sorry i wasnt clear in my post, but i tried that but it got me no where... and I cant stop thinking theres a trick because of that +8... cause it could also be +1... so i just wanted to let you start fresh... help me find the tricky part. – Tal Aug 02 '14 at 22:17
  • Do you know modular arithmetic? – Hakim Aug 02 '14 at 22:30
  • well, now i know. but im pretty sure this isnt how they want me to prove this.. is there a way to solve this not using modular arithmetic? – Tal Aug 02 '14 at 23:39
  • See Sami's answer. – Hakim Aug 02 '14 at 23:47

5 Answers5

3

Hint

The inductive step

$$3^{3^{n+1}}+8= 3^{3\times3^n}+8=\left(3^{3^n}\right)^3+8=(7q-8)^3+8\\=7\times k-8\times 8\times(8-1)=7\times k'$$

1

Suppose it holds for $n$, so that $7|3^{3^n}+8$. For $n+1$, we would like to prove that $7|3^{3^{n+1}}+8$, or equivalently that $7|3^{3^{n}\times 3}+8$, or equivalently that $7|(3^{3^{n}})^3+8$. From the base ($n$) case, we know that $3^{3^n} \equiv -1 \mod 7$. This allows us to conclude that $(3^{3^{n}})^3+8 \equiv (-1)^3 + 8 \equiv 0\mod 7$.

Lord Soth
  • 7,750
  • 20
  • 37
1

We have to show that : $$3^{3^n}+8 \equiv 0 \pmod 7 \Rightarrow 3^{3^n}+1 \equiv 0 \pmod 7$$

$$n=1: 3^{3}+1=3^{2+1}+1=3^2 \cdot 3+1=2 \cdot 3+1=7 \equiv 0 \pmod 7 \checkmark$$

$$\text{We suppose that the relation stands for n: } \ 3^{3^n}+1 \equiv 0 \pmod 7$$

For $n+1$:

$$ 3^{3^{n+1}}+1=3^{3^n \cdot 3}+1 \equiv (3^{3^n})^3+1 \equiv (-1)^3+1 \equiv -1+1 \equiv 0 \pmod 7$$

evinda
  • 7,823
0

If $x=7a$, what can you say about $(x-8)^3+8$..?

Peter Franek
  • 11,522
0

First note that this is equivalent to $7$ dividing $3^{3^n}+1$. Clearly if $n=1$, then $3^{3^1}+1 = 28$ and $7$ divides this.

Let's suppose it's true for $n$. Then $3^{3^{n+1}} = 3^{3\cdot3^n} = (3^{3^n})^3$. We want then to show that $7$ divides $(3^{3^n})^3+1$. A nice factorization is that $a^3+b^3 = (a+b)(a^2-ab+b^2)$. So then we can write $(3^{3^n})^3+1$ as $(3^{3^n}+1)((3^{3^n})^2-3^{3^n}+1)$. Can you take it from here?

Cameron Williams
  • 29,432