Start
Zufällige Seite
Anmelden
Einstellungen
Spenden
Über Wikiversity
Haftungsausschluss
Suchen
Zahlentheorie/Mersenne Zahl ist 2 quasiprim/Aufgabe/Lösung
Sprache
Beobachten
Bearbeiten
<
Zahlentheorie/Mersenne Zahl ist 2 quasiprim/Aufgabe
Wir haben zu zeigen, dass für
m
=
2
p
−
1
{\displaystyle {}m=2^{p}-1}
gilt:
2
m
−
1
=
1
{\displaystyle {}2^{m-1}=1}
modulo
m
{\displaystyle {}m}
. Es ist
2
p
=
2
{\displaystyle {}2^{p}=2}
modulo
p
{\displaystyle {}p}
nach dem kleinen Fermat. Damit ist
m
−
1
=
2
p
−
2
=
0
{\displaystyle {}m-1=2^{p}-2=0}
modulo
p
{\displaystyle {}p}
. Also ist
m
−
1
{\displaystyle {}m-1}
ein Vielfaches von
p
{\displaystyle {}p}
, sagen wir
m
−
1
=
a
p
{\displaystyle {}m-1=ap}
. Wegen
2
p
=
1
{\displaystyle {}2^{p}=1}
modulo
m
{\displaystyle {}m}
gilt dann
2
m
−
1
=
(
2
p
)
a
=
1
{\displaystyle {}2^{m-1}=(2^{p})^{a}=1}
modulo
m
{\displaystyle {}m}
.
Zur gelösten Aufgabe