Für p ungerade Primzahl Zeige dass p | n 2^{n} +1

Question

Aufgabe:

Sei p = 2k +1eine ungerade Primzahl. Zeige dass p | n \( 2^{n} \) +1

fur unendlich viele natürliche Zahlen n gilt.

Problem/Ansatz:

n \( 2^{n} \) +1 ≡ 0 (mod p)

n \( 2^{n} \)   ≡ -1 (mod p)

n \( 2^{n} \)   ≡ p-1 (mod p)

n \( 2^{n} \)  ≡ 2 k (mod p)

Hier komme ich leider nicht weiter. hat jemand eine Idee?

Answer 1

Nach dem kleinen Satz von Fermat gilt 2^p-1≡1 mod p.

Multiplikation mit p-1 führt zu

(p-1)2^p-1≡p-1 mod p. Wir addieren 1:

(p-1)2^p-1+1≡ p mod p.

Die Aussage ist also schon mal für n=p-1 wahr.

Vielleicht findest du im Zusammenhang damit weitere n...

Comments

Weitere n zu finden ist nicht ganz so leicht, wegen der 2^(p-1) und der +1

---

p-1 ist kongruent nach dem Modul p zu 2p-1, zu 3p-1, zu 4p-1 usw.

Es existiert also eine Periodenlänge p.

2^p-1 ist hingegen kongruent zu 2^2(p-1) und zu 2^3(p-1) usw,, die Periodenlänge ich HIER (p-1).

Beide Peroden kommen zur Deckung mit der Periodenlänge p(p-1).

Aus einer Lösung für n=p-1 folgt also eine weitere Lösung für n=p-1+p(p-1).