Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Letzten Ziffern von 2^1000

Letzten Ziffern von 2^1000

Universität / Fachhochschule

Gruppen

Tags: Gruppen, Modulo Arithmetik, Restgruppen

Jannik-F aktiv_icon

23:33 Uhr, 25.11.2019

Hallo zusammen,

wir haben folgende Aufgabe bekommen :

Finden Sie die letzten drei Ziffern in der Dezimaldarstellung der Zahlen:

2^{1000}

Übersetzt heißt das für mich wir sollen

2^{1000} mod 1000

lösen. Meine erste Idee war es das ganze über den Satz von Fermat und Euler zu lösen, den kann man aber mir ist später aufgefallen, dass man diesen nicht anwenden kann, da 2 und

1000

ja nicht teilerfremd sind (ggT=2).

Meine zweite Idee war es die Potenz möglichst gut auseinander zu ziehen, also hab ich als ersten Impuls aus

2^{1000} mod 1000 \to {({(2^{10})}^{10})}^{10} mod 1000

gemacht und versucht es darüber zu lösen, was im Endeffekt mir die Lösung

376

als letzten Stellen lieferte, was aber im Großen und Ganzen sehr umständlich und kleinlich war, da man irgendwann nicht drum herum kam unschöne Sachen wie

376^{3} \cdot 376^{3} \cdot 376 mod 1000

auszurechnen. Daher wollte ich fragen, ob es auch eine elegante und kürzere alternative gibt für das Ganze (ich bin mir sicher das es sie gibt und ich komme gerade nicht drauf)

Ich habe in einem ähnlichen Forumbeitrag gelesen, dass man hier wohl den chinesischen Restsatz verwenden kann aber leider ohne Erklärung wie, denn auf den ersten Blick wüsste ich nicht wie.

MfG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

anonymous

00:33 Uhr, 26.11.2019

Hallo,
hast du untersucht ob es eine Periodizität gibt bzgl. der 2er...Es würde dich weiterführen. Betrachte die Periodizität der Endziffer.

Jannik-F aktiv_icon

00:47 Uhr, 26.11.2019

Hallo,
was genau meinst du mit "Periodizität gibt bzgl. der 2er"
Die Reihe von

2^{n}

wäre ja

0,1,2,4,16,32,64,128

usw... Wirklich periodisch ist da ja eig. Nichts und bei

2^{10} = 1024 mod 1000

kommt man auf

24

was auch nicht in diese Reihe passt oder auf etwas periodisches schließen lässt.

LG

Jannik-F aktiv_icon

01:01 Uhr, 26.11.2019

Ich glaube ich habe "Betrachte die Periodizität der Endziffer" eiskalt überlesen, also abseits der

2^{0} = 1

endet

2^{n}

für beliebiges

n \in ℕ

auf

0,2,4,6

oder 8. Damit weiß ich schonmal dass mein Ergebnis mit

376

auf jeden Fall im Rahmen der Möglichkeiten liegt und das ganze herumgerechne nicht umsonst war aber dennoch, wie kann ich das zu meinem Vorteil nutzen?

HAL9000

07:54 Uhr, 26.11.2019

Teile das Modul in Primfaktoren auf:

1000 = 2^{3} \cdot 5^{3}

. Und ja, dann kombiniert man die Einzellösungen

mod 5^{3}

und

mod 2^{3}

per Chinesischen Restsatz zur Lösung

mod 1 0^{3}

.

Wegen Fermat-Euler weiß man dann

2^{φ (5^{3})} = 2^{(5 - 1) \cdot 5^{2}} = 2^{100} \equiv 1 mod 5^{3}

, und damit auch

2^{1000} = {(2^{100})}^{10} \equiv 1^{10} = 1 mod 5^{3}

.

Da andererseits trivialerweise auch

2^{1000} \equiv 0 mod 2^{3}

gelten muss, haben wir diejenige Lösung

2^{1000} \equiv 1 + 125 k mod 1000

, für welche

1 + 125 k \equiv 1 + 5 k \equiv 0 mod 8

gilt, das ist nach kurzem Probieren

k = 3

und damit insgesamt

2^{1000} \equiv 376 mod 1000

.

P.S.: Mit fast analoger Rechnung und nur geringfügigem Mehraufwand bekommt man auch die letzten vier Ziffern 9376 dieser Zahl heraus.

anonymous

08:47 Uhr, 26.11.2019

Ich würde auch empfehlen, erst mal den ersten Gedankengang zu Ende zu führen und die Periodizität der Endziffer nicht so oberflächlich und falsch, sondern mal wirklich ernsthaft anzugehen.
Ich fange mal für dich an:
Die Endziffer von

2^{1} = 2

ist 2 .
Die Endziffer von

2^{2} = 4

ist 4 .
Die Endziffer von

2^{3} = 8

ist 8 .

Willst du mal weiter...?
(Es lohnt sich!)

Jannik-F aktiv_icon

20:17 Uhr, 26.11.2019

(2^{0} = 1)

2^{1} = 2

2^{2} = 4

2^{3} = 8

2^{4} = 16

2^{5} = 32

2^{6} = 64

2^{7} = 128

2^{8} = 256

2^{9} = 512

2^{10} = 1024

2^{11} = 2048

2^{12} = 4096

1,5,9,13 . .

\to

Endziffer 2

2,6,10,14 . .

\to

Endziffer 4

3,7,11,15 . .

\to

Endziffer 8

4,8,12,16 . .

\to

Endziffer 6

4 + k \cdot 4 = 1000 < \to k = 249

liefert als einziges eine Zahl

k \in ℕ,

also kann man schonmal sicher sagen, dass

2^{1000} mod 1000

eine Zahl ist, die auf 6 endet.

Wie komm ich darüber jetzt aber an die beiden Ziffern davor ?

HAL9000

20:35 Uhr, 26.11.2019

> (Es lohnt sich!)

> Wie komm ich darüber jetzt aber an die beiden Ziffern davor ?

Dein Part, 11engleich. ;-)

anonymous

23:54 Uhr, 26.11.2019

Ich muss bekennen, dass ich die Aufgabenstellung nicht recht gelesen habe.
Meine Empfehlung und Motivation galt dahin, die letzte Stelle zu bestimmen.
Das ist ja schon mal gelungen.
:-)

HAL9000

06:18 Uhr, 27.11.2019

> Ich muss bekennen, dass ich die Aufgabenstellung nicht recht gelesen habe.

Ja, jeder liest etwas bzw. liest etwas nicht. Du liest die Aufgabenstellung nicht richtig, und Jannik-F liest nur den unmittelbar letzten Beitrag, und postet deshalb

> Wie komm ich darüber jetzt aber an die beiden Ziffern davor ?

anonymous

09:19 Uhr, 27.11.2019

Hallo,

a^{x} a^{y} = a^{x + y} (i)

Periodizität der 2er-Potenzen:
Beginnen wir mit einer überschaubaren Größe

2^{25} = 33554432

Wir erhalten mit

(i)

für die letzten 3 Ziffern entsprechend für

2^{50} : 43 2^{2} = 186624

und analog für

2^{100} : 62 4^{2} = 389376

, für

2^{200} : 37 6^{2} = 141376

. Da nun jeder weitere Schritt von

37 6^{2}

(z.B.

2^{200} \cdot 2^{100} = 2^{300}

) die drei Endziffern

376

ergibt, besitzt auch

2^{1000}

diese drei Endziffern.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1488018

1487851

	Status: nicht eingeloggt	Noch nicht registriert?