Wie Beweise ich 7|2^n -1 <=> 3|n?

Question

Aufgabe:

Beweise 7|2^n -1 <=> 3|n

Problem/Ansatz:

Wie komme ich von der 7 teilt... zur 3 teilt ?

Answer 1

2^1≡ 2 mod 7

2^2≡ 4 mod 7

2^3≡ 1 mod 7 (und somit ist 2^3-1 durch 7 teilbar).

Wegen 2^3≡ 1 mod 7 gilt für jeden Exponenten k

\(2^k\cdot 2^3 \equiv 2^k \cdot 1 \equiv 2^k mod 7\),

also \(2^{k+3} \equiv 2^k mod 7\).

Damit wiederholen sich die Reste 2, 4 und 1 zyklisch und haben nur für k=0, k=3, k=6, k=9 ... den Wert 1.