Beweis 2^2n-1 teilbar durch 3

Question

Wir sollen beweisen dass 2²ⁿ-1 teilbar durch 3 ist, mit Hilfe der vollständigen Induktion.

Induktionsanfang hab ich n=1 gewählt da erhält man 3, was natürlich teilbar ist.

Für den Induktionsanfang n=n+1 leider weiß ich da jetzt nicht weiter wie genau ich das beweisen soll.

Answer 1

Induktionsschritt n -> n + 1

2^{2[n + 1]} - 1

2^{2n + 2} - 1

4 * 2^{2n} - 1

4 * 2^{2n} - 4 + 3

4 * (2^{2n} - 1) + 3
2^{2n} - 1 ist durch 3 Teilbar.

Ein Produkt ist durch 3 Teilbar, wenn einer der Faktoren durch 3 teilbar ist.

Eine Summe ist durch 3 Teilbar, wenn beide Summanden durch 3 teilbar sind.

Damit ist auch 4 * (2^{2n} - 1) + 3 durch 3 teilbar.

Answer 2

Voraussetzung:

Gelte für ein festes m ≥ n : 3 teilt 2 ^2 m - 1

Dann gilt für m + 1: 3 teilt 2 ^{2 ( m + 1 )} - 1

Beweis:

2 ^{2 ( m + 1 )} - 1

= 2 ^{2 m + 2} - 1

= 2 ^{2 m} * 2 ² - 1

= ( 2 ^{2 m} - 1 + 1 ) * 4 - 1

= ( 2 ^{2 m} - 1 ) * 4 + 1 * 4  - 1

= 4 * ( 2 ^{2 m} - 1 ) + 3

3 teilt gemäß Voraussetzung ( 2 ^{2 m} - 1 ),

dann teilt 3 aber auch  4 * ( 2 ^{2 m} - 1 )

und auch  

4 * ( 2 ^{2 m} - 1 ) + 3 = 2 ^{2 ( m + 1 )} - 1

q.e.d.