Vollständige Induktion. Für alle...

Question

Kann mir jemand diese Aufgabe erklären:

$$Für\quad alle\quad n∈ℕ*\quad gilt:\quad 3\quad teilt\quad { 2 }^{ 2n }-1.$$

Answer 1

Direkt

2^{2n} - 1 mod 3 = 0

4^n - 1 mod 3 = 0

(4 mod 3)^n - 1 mod 3 = 0

1^n - 1 mod 3 = 0

1 - 1 mod 3 = 0

0 = 0

Comments

Vollständige Induktion

3 teilt 2^{2*n} - 1

Induktionsanfang n = 1

3 teilt 2^{2*1} - 1

3 teilt 3 --> stimmt

Induktionsschritt n --> n + 1

3 teilt 2^{2*(n+1)} - 1

3 teilt 2^{2*n + 2} - 1

3 teilt 4 * 2^{2*n} - 1

3 teilt 4 * 2^{2*n} - 1 - 3

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

3 teilt 4 * (2^{2*n} - 1)

Dank Induktionsvoraussetzung ist das erfüllt.