Ein Beispiel zu lineare Kongruenzen lösen.

Question

Für welche n ∈ ℕ gilt: $$ { 2 }^{ n }-1\quad \equiv \quad 0\quad \left( mod\quad 7 \right)  $$

Answer 1

dies gilt für alle \( n \in \mathbb{N}_0 \) mit \( n = 3k \) und \( k \in \mathbb{N}_0 \). Mit anderen Worten gilt es für \( 3 \mathbb{N}_0 \).

Mister

Answer 2

wenn du die Aussage für ein paar verschiedene Werte prüfst, sieht man , dass für n=0, n=3, n=6 die Aussage zutrifft.

Daher Annahme: n=3*m mit m∈ℕ₀

Induktionsbeweis: (2^{3m}-1)=7*k, k∈ℕ₀

Induktionsanfang:

n=0: (2^0-1)=0=7*0 passt

Induktionsannahme:

(2^{3m}-1)=7*k, k∈ℕ0

Induktionsschritt: m-->m+1

(2^{3*(m+1)})-1)=(8*2^{3m}-1)=(7*2^{3m}+2^{3m}-1)=7*(2^{3m}+k)=7*k'