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⁰-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'