Welche Zahlen der Form 2^n-1 (n ∈ ℕ_{0}) sind durch 3 teilbar?

Question

Aufgabe:

Welche Zahlen der Form $$ 2^n-1 (n \in \mathbb{N}_{0}) $$ sind durch 3 teilbar? (Beweise)

Problem/Ansatz:

Jemand eine Idee wie ich das beweisen könnte? Leider bin in der Suche nicht fündig geworden.

Answer 1

Probier das doch mal für kleine Zahlen n aus.

Comments

Für n=0,2,4,6,8,... ist das teilbar

---

Für n=0,2,4,6,8,... ist das teilbar

Richtig. Nun gibt es verschiedene einfache Argumente, warum das so ist.

---

Könnte man das auch mit vollständiger Induktion beweisen?

---

Ja, du kannst auch mit vollständiger Induktion beweisen, dass \(2^{2k}-1\) für alle k∈N durch 3 teilbar ist.

---

Du musst dann aber noch zeigen, dass \(2^{2k+1}-1\) nicht durch 3

teilbar ist.

Answer 2

Wenn du weißt, wie man modulo 3 rechnet, ist die Aufgabe

ganz leicht.

Comments

Vollständige Induktion

Answer 3

Zur Lösung der Aufgabe mit mod 3:

\( 3 \; | \; 2^n-1 \; \iff \; 2^n-1\equiv 0\) mod \(3\; \iff \)

\((-1)^n\equiv 1\) mod \(3 \; \iff \; 2\; | \; n\).

Comments

$$ (-1)^n\equiv 1 \text{  } mod \text{  } 3 $$

Kann den Zwischenschritt nicht nachvollziehen. Woher kommt denn die (-1)ⁿ her?

---

Wegen \(2\equiv -1\) mod \(3\).