endziffer 2^1000 kongruenz

Neue Frage »

13.11.2009, 18:46	Linus.H	Auf diesen Beitrag antworten »
endziffer 2^1000 kongruenz Heyy! ich sitz jetzt schon seit ner halben stunde an dieser aufgabe und dreh mich immer im kreis... Vielleicht habt ihr ja ne idee dazu.. Geben sie die letzten 2 ziffern von 2^1000 an. Hinweis: Verwenden sie die Beziehung 2^10 = 1024 kongruent zu -1 mod 25 und die Aussage: a ist kongruent zu x mod m und b ist kongruent zu y mod m => ab ist kongruent zu xy mod m habs schon mit den potenzgesetzen versucht die 2^1000 auseinanderzunehmen, aber dann bekomm ich ja ne neue potenz raus, also 2^1000 = (2^100)^10 zum beispiel. habt ihr ne idee dazu? die kongruenzrechnung habe ich soweit ganz gut verstanden. Vielleicht hat ja einer am samstag abend lust mir zu helfen, es lässt mich nämlich nicht in ruhe, weil es relativ einfach aussieht vielen dank!
13.11.2009, 19:52	kiste	Auf diesen Beitrag antworten »
Hallo, der Tipp ist doch schon ziemlich gut. Es ist doch 2^1000 = 2^10*100 = (2^10)^100 und betrachte es jetzt modulo 25. Dann betrachte den Term noch modulo 4(sehr einfach!). Dannach musst du die beiden nur noch mit dem chinesischen Restsatz zusammenfügen und hast modulo 100(sprich die letzten beiden Stellen)
14.11.2009, 00:14	Linus.H	Auf diesen Beitrag antworten »
würde die nächste zeile dann lauten (2^10)^100 kongruent zu -1^100 mod 25? wenn ja, was bringt mir das denn?
14.11.2009, 10:02	kiste	Auf diesen Beitrag antworten »
(-1)^100 kann man leicht berechnen, das bringt es? Zur weiteren Vorgehensweise hab ich ja schon was gesagt
15.11.2009, 16:20	Linus.H	Auf diesen Beitrag antworten »
ich versteh immernoch nicht was mir dieser Ausdruck $\begin{eqnarray} (1024)^{100} \equiv 1 mod 25 \end{eqnarray}$ jetzt bringt... $\begin{eqnarray} 1024^{100} \end{eqnarray}$ ist ja immernoch $\begin{eqnarray} 2^{1000} \end{eqnarray}$
15.11.2009, 16:23	kiste	Auf diesen Beitrag antworten »
Ja das ist ja gerade das tolle Wir wollen doch $\begin{eqnarray} 2^{1000}\mod 100 \end{eqnarray}$ bestimmen. Nach dem chinesischen Restsatz ist es aber äquivalent $\begin{eqnarray} 2^{1000}\mod 25 \end{eqnarray}$ und $\begin{eqnarray} 2^{1000}\mod 4 \end{eqnarray}$ zu bestimmen. Den ersten Teil dieser Aufgabe hast du damit also schon erledigt
Anzeige

15.11.2009, 16:58	Linus.H	Auf diesen Beitrag antworten »
das waren doch bis jetzt nur umformungen der ausgangsgleichung.. die aufgabe besteht ja darin die letzten beiden ziffern zu berechnen. ich weiß jetzt das die 4 und die 25 die zahl 2^1000 teilen. ich sehe aber keine verbindung zwischen dieser erkenntnis und der frage nach den letzten beiden ziffern von 2^1000. verstehst du was ich meine?
15.11.2009, 17:05	kiste	Auf diesen Beitrag antworten »
Also ersteinmal: 25 teilt 2^1000 natürlich nicht, sonst würde sich doch nicht der Rest 1 ergeben. Das 4 die Zahl 2^1000 teilt ist eine wichtige Erkenntnis! Nochmal langsam: Du willst die letzten beiden Stellen ermitteln. Die letzten beiden Stellen sind genau der Rest bei der Division durch 100. Also betrachten wir das ganze modulo 100. Jetzt gibt es einen tollen Satz, den chinesischen Restsatz. Dieser besagt dass wir auch modulo 25 und modulo 4 rechnen können und das Ergebnis dann so zusammensetzen können dass wir das Ergebnis modulo 100 bekommen. Wir wissen also jetzt: $\begin{eqnarray} 2^{1000} \equiv 1 \mod 25 \end{eqnarray}$ und jetzt bestimme noch $\begin{eqnarray} 2^{1000} \mod 4 \end{eqnarray}$ (hast du im Prinzip schon gemacht, aber ich will es nochmal explizit hören). Wenn du das hast suchst du eine Lösung im Zahlenraum 0 bis 99 die beiden Lösungen genügt. Da wir bereits wissen dass es modulo 25 eben 1 gibt reicht es 1,26,51 und 76 zu testen(auf den Wert der sich modolu 4 ergibt)
15.11.2009, 17:36	Linus.H	Auf diesen Beitrag antworten »
ahh okay.. so langsam kommt licht ins dunkel. 2^100 modulo 4 ergibt 0 richtig?
15.11.2009, 17:36	kiste	Auf diesen Beitrag antworten »
Genau. Jetzt musst du nur noch untersuchen welche der Zahlen 1,26,51,76 auch Rest 0 bei der Division durch 4 lässt und du bist fertig.
15.11.2009, 17:41	Linus.H	Auf diesen Beitrag antworten »
ja gut, das wird dann wohl die 76 sein. eigentlich ein ziemlich schönes system das so zu rechnen. ich danke dir vielmals kiste für deine geduld

Neue Frage »

Antworten »

endziffer 2^1000 kongruenz

Verwandte Themen