Zeigen Sie, dass 1+2^{2^n}+2^{2^{n+1}} durch 7 teilbar ist

Question

Aufgabe:

Zeigen Sie, dass $$1+2^{2^n}+2^{2^{n+1}}$$ durch 7 teilbar ist

Problem/Ansatz:

Ich möchte den Beweis mit vollständiger Induktion führen. Im Zuge dessen habe ich für $$n+1$$ den Ausdruck $$1+2^{2^{n+1}}+2^{2^{n+2}}$$ bereits auf $$1+2^{2^n}+2^{2^{n+1}}+(8^{2^n}-1)\cdot 2^{2^n}$$ zurück geführt. Nach IV ist der Term $$1+2^{2^n}+2^{2^{n+1}}$$ durch 7 teilbar. Aber ich komme nicht weiter damit zu zeigen, dass auch $$(8^{2^n}-1)\cdot 2^{2^n}$$ durch 7 teilbar ist.

Kann jemand einen Tipp geben?

Answer 1

Es kann hier nützlich sein, die Potenzen anders auszudrücken:

\(1+2^{2^n}+2^{2^{n+1}}=1+2^{2^n}+2^{2^n\cdot 2^1}=1+2^{2^n}+\big(2^{2^n}\big)^{^2}\).

Nach Induktionsvoraussetzung gibt es für ein beliebiges, aber festes, \(n\in \mathbb{N}_{\geq 0}\) ein \(m\in \mathbb{Z}\), sodass \(7\cdot m=1+2^{2^n}+\big(2^{2^n}\big)^{^2}\) gilt,bzw

\(\big(2^{2^n}\big)^{^2}=7\cdot m-1-2^{2^n}\). (IV)

Induktionsschritt. \(n\rightarrow n+1\)

Es gilt \(1+2^{2^{n+1}}+2^{2^{n+2}}=1+\big(2^{2^n}\big)^{^2}+\big(2^{2^n}\big)^{^4}=1+\big(2^{2^n}\big)^{^2}\cdot \Big(1+\big(2^{2^n}\big)^{^2}\Big)\\ \stackrel{(IV)}{=}1+\Big(7\cdot m-1-2^{2^n}\Big)\cdot \Big(1+7\cdot m-1-2^{2^n}\Big)\\=1+\Big(7\cdot m-1-2^{2^n}\Big)\cdot \Big(7\cdot m-2^{2^n}\Big)\\=1+7^2\cdot m^2-7\cdot m-2^{2^n}\cdot 7\cdot m-7\cdot m\cdot 2^{2^n}+2^{2^n}+\big(2^{2^n}\big)^{^2}\\=1+7\cdot \Big(7\cdot m^2-m-2\cdot 2^{2^n}\cdot m\Big)+2^{2^n}+\big(2^{2^n}\big)^{^2}\\=1+2^{2^n}+\big(2^{2^n}\big)^{^2}+7\cdot \Big(7\cdot m^2-m-2\cdot 2^{2^n}\cdot m\Big)\\\stackrel{(IV)}{=}7\cdot m+7\cdot \Big(7\cdot m^2-m-2\cdot 2^{2^n}\cdot m\Big)\\=7\cdot \Big(7\cdot m^2-2\cdot 2^{2^n}\cdot m\Big)\)

Answer 2

8 = 1 mod 7

sollte genügen.

Comments

Oh ja. Viel einfacher...

---

Das sollte genügen, um zu zeigen, dass \( 2^{2^{n}} \) ≡  \( 2^{2^{n+2}} \) mod 7

\( 2^{2^{0}} \) ≡  \( 2^{2^{2}} \) mod 7 weil \(2 ^{1} \) * \(2 ^{3} \)=\(2 ^{4} \)

\( 2^{2^{1}} \) ≡  \( 2^{2^{3}} \) mod 7

weil \(2 ^{2} \)*\(2 ^{3*2} \)=\(2 ^{8} \)

\( 2^{2^{2}} \) ≡  \( 2^{2^{4}} \) mod 7

weil \(2 ^{4} \)*\(2 ^{3*4} \)=\(2 ^{16} \)

Ja, das genügt.

Answer 3

Du könntest eventuell vermuten wenn 2^2^n nicht durch 7 teilbar ist das 8^2^n - 1 hoffentlich immer durch 7 teilbar ist und dieses auch wieder mitteln vollständiger induktion zeigen.

Induktionsvoraussetzung

8^2^n - 1 ist durch 7 teilbar

dann muss auch

8^2^(n + 1) - 1 = 8^(2*2^n) - 1 = (8^2^n)^2 - 1 ist durch 7 teilbar gelten

Wir ersetzen mal 8^2^n = z

folgt aus z - 1 ist durch 7 teilbar

dann z^2 - 1 = (z + 1)(z - 1) ist durch 7 teilbar?

Das klingt doch gut oder mache ich hier einen Denkfehler? Natürlich kannst du probieren den Trick auch schon früher anzuwenden.