Gesucht ist ggt(2^n -1,3)

Question

Aufgabe:

Gesucht ist ggt(2ⁿ -1,3)

Problem/Ansatz:

Wenn ich für n Zahlen einsetzte, erhalte ich:
1,3,7,15,31,63,127,255,511,1023,2047...
Daraus lässt sich feststellen, dass jede 2. Zahl durch 3 teilbar ist, bzw deren ggt()=3 ist.

Wie gebe ich hier das Ergebnis? Gibt es sonst eine andere Lösung für Potenzen bei ggt() mit umformen o.ä?

Answer 1

Wir müssen nur schauen, wann \(3| 2^n-1\) ist, also

\(2^n\equiv 1\) mod \(3\). wegen \(2\equiv -1\) mod \(3\)

bedeutet dies \((-1)^n\equiv 1\) mod \(3\), also \(n\) gerade.

Comments

d.h. dann für n gerade 3
und n ungerade 1 ?

---

ja, so sehe ich das.