3 endziffer in der dezimaldarstellung 2^1000 wie geht das?

26.12.2012, 16:01	amira91	Auf diesen Beitrag antworten »
3 endziffer in der dezimaldarstellung 2^1000 wie geht das? Meine Frage: hallo wir müssen die letzten 3 Ziffern in dezimaldarstellung aufschreiben von 2^1000 und habe keine ahnung wie das gehen soll.... könnt ihr mir vllt helfen ?? Meine Ideen: habe erst gedacht man muss es einfach mal nehmen aber um ehrlich zu sein hört sich das total falsch an
26.12.2012, 17:59	Elvis	Auf diesen Beitrag antworten »
Ein bißchen Kongruenzrechnung: $\begin{eqnarray} 2^{10}=1024 \equiv 24 (1000)\Rightarrow 2^{90}\equiv 24^9\equiv 224 (1000) \end{eqnarray}$ ... und jetzt darfst du ein wenig weiterrechnen.
26.12.2012, 19:59	amira91	Auf diesen Beitrag antworten »
also ich kann es nicht in einem Schritt machen sondern muss das so stückchenweise machen ?? ich verstehe immernoch nicht wieso jetzt 2^90 ?
27.12.2012, 09:34	tmo	Auf diesen Beitrag antworten »
Mit dem chinesischen Restsatz geht es deutlich einfacher. $\begin{eqnarray} 2^{1000} \equiv 0 \pmod 8 \end{eqnarray}$ ist klar. Mit Euler-Fermat kriegt man auch schnell $\begin{eqnarray} 2^{1000} \equiv r \pmod {125} \end{eqnarray}$ raus, wobei $\begin{eqnarray} r \end{eqnarray}$ noch von dir zu finden ist. Danach musst du nur noch die sieben Zahlen $\begin{eqnarray} 125k + r, 0 \leq k \leq 7 \end{eqnarray}$ dahingehend überprüfen, ob sie durch 8 teilbar sind. Genau eine tut es. Und das ist dein gesuchter Rest.
27.12.2012, 10:31	Elvis	Auf diesen Beitrag antworten »
@amira91 $\begin{eqnarray} 2^{10} \end{eqnarray}$ und $\begin{eqnarray} 2^{90} \end{eqnarray}$ sind nur Beispiele, die zeigen, dass du nicht $\begin{eqnarray} 2^{1000} \end{eqnarray}$ berechnen musst. Immerhin ist $\begin{eqnarray} (2^{90})^{10}= 2^{900} \end{eqnarray}$ schon "ziemlich nahe" an $\begin{eqnarray} 2^{1000} \end{eqnarray}$ . z.B. bietet sich auch $\begin{eqnarray} 2^{29} \equiv 912 \equiv -88 (1000) \end{eqnarray}$ an.
29.12.2012, 13:39	Elvis	Auf diesen Beitrag antworten »
Wenn du immer noch keine Lösung hast, dann kommt hier ein möglicher Weg: $\begin{eqnarray} 2^{10}=1024 \equiv 24 (1000)\Rightarrow 2^{60}=(2^{10})^6\equiv 24^6=191102976 \equiv -24(1000) , 2^{90}=(2^{10})^9\equiv 24^9 = 2641807540224 \equiv 224 (1000) \end{eqnarray}$ $\begin{eqnarray} 2^{60}\equiv -24(1000) \Rightarrow 2^{360}=(2^{60})^6\equiv (-24)^{6}=191 102 976\equiv -24(1000) \Rightarrow 2^{720}=(2^{360})^2\equiv (-24)^2 (1000) \end{eqnarray}$ $\begin{eqnarray} 1000=720+3\cdot 90+10 \Rightarrow 2^{1000}\equiv (-24)^2\cdot 224^3 \cdot 24 = 155373797376 \equiv 376 (1000) \end{eqnarray}$
Anzeige

29.12.2012, 14:32	Mystic	Auf diesen Beitrag antworten »
Der Profi würde allerdings zunächst $\begin{eqnarray} 2^{1000} \mod 125 \end{eqnarray}$ wie folgt berechnen $\begin{eqnarray} 2^{1000} \equiv (2^{100})^{10} \equiv {\underbrace{(2^{\varphi(125)})}_{\equiv 1 \mod 125}}^{10} \equiv 1 \mod 125 \end{eqnarray}$ aber nur, weil er weiß, dass dies noch leicht im Kopf möglich ist... Tatsächlich wird ja $\begin{eqnarray} 2^{997} \mod 125 \end{eqnarray}$ benötigt, da wir die ganze Kongruenz noch mit 2³ multiplizieren müssen, um auf den Modul 1000 zu kommen... Nun ist aber das Inverse von 2 mod n für ein ungerades n ganz allgemein durch (n+1)/2 gegeben, hier also durch (125+1)/2, also 63... Letzendlich gilt somit $\begin{eqnarray} 2^{1000} \equiv 8 \cdot (63^3 \mod 125) \equiv 376 \mod 1000 \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »