Zeigen Sie, dass 2^(n+1) für alle n ∈ N ein Teiler von (3^2^n) − 1 ist.

Question

Aufgabe:

Zeigen Sie, dass 2^(n+1) für alle n ∈ N ein Teiler von (3^2^n) − 1 ist.

Hinweis: Vollständige Induktion und dritte binomische Formel.

Problem/Ansatz:

Ich hab den Induktionsanfang und die Induktionsvoraussetzung, dass es eine natürliche Zahl geben muss, sodass (3^2^n) -1 = m * 2^(n+1) mit m ∈ N.

Dann hab ich den Induktionsschritt, aus n wird n+1 und zu zeigen ist, dass (3^2^(n+1)) - 1 = m' * 2^(n+2) mit m' ∈ N. Links ist aus n einfach n+1 geworden und rechts ist aus der Potenz (n+1) die Potenz (n+2) geworden.

So, jetzt hab ich die linke Seite so umgeformt:

(3^2^(n+1)) - 1 = (3^(2*2n)) - 1 = ((3^2n)^2) - 1^2, damit ich dann mit der 3. binom. Formel komme auf:

((3^2n)-1) * ((3^2n)+1)     die erste Klammer ist genau meine Ind.voraussetzung, somit

(m * 2^(n+1)) * ((3^2n)+1)

Jetzt ist mein Problem, dass ich ja zeigen muss, dass die linke Seite, also das, womit ich angefangen hab, gleich .... (irgendwas) multipliziert mit 2^(n+2) ist. Ich habe aber nirgends eine n+2 in der Potenz, sondern nur n+1.

Answer 1

Du kannst doch umschreiben:

2^(n + 2) = 2·2^(n + 1)

Comments

Richtig, aber ich sehe nicht, wo das mein Problem löst.

Ich hab am Ende (m * 2^(n+1)) * ((32n)+1) da stehen.

Wie krieg ich da irgendwo 2^(n+2) raus?

---

Induktionsschritt: n → n + 1

2^((n + 1) + 1) | 3^(2^(n + 1)) - 1
2^(n + 2) | 3^(2·2^n) - 1
2·2^(n + 1) | (3^(2^n))^2 - 1
2·2^(n + 1) | (3^(2^n) + 1)·(3^(2^n) - 1)

Nun gilt aber

2 | 3^(2^n) + 1 und
2^(n + 1) | 3^(2^n) - 1

und damit ist die Aussage wahr.

---

"Nun gilt aber

2 | 3^(2n) + 1 und
2^(n + 1) | 3^(2n) - 1

und damit ist die Aussage wahr."

Wieso gilt das?

Wir haben die Aussage 2·2^(n + 1) | (3^(2n) + 1)·(3^(2n) - 1)

Wieso kann man daraus schließen, dass der eine Faktor den anderen Faktor teilt?

2 * 5 teilt auch 7 * 10. Trotzdem teilt 2 nicht die 7.

---

2 teilt 3^(2n) + 1

Weil die rechte Seite eine gerade Zahl ist.

3^k ist definitiv eine ungerade Zahl, weil alle Faktoren ungerade sind. Damit muss 3^k + 1 definitiv eine gerade Zahl sein.

---

Wow, das stimmt. Hätte ich so niemals gesehen.

Aber in deinem Beweis ist nirgends die Induktionsvoraussetzung eingebaut und das ist Pflicht bei uns. Betont der Prof immer wieder. Ich muss also irgendwo auf ein (3^2^n)-1 kommen und das dann nach Ind.vss zu m * 2^(n+1) umwandeln.

---

2^(n + 1) | 3^(2n) - 1

ist doch die Induktionsvoraussetzung die ich ganz am Schluss auch benutzt habe.