Letzte Ziffer einer Potenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:53 So 27.06.2010 | | Autor: | ftm2037 |
| Aufgabe | | Bestimme die letzten drei Ziffern der Deziemaldarstellung der Zahl [mm] 7^{512}. [/mm] |
Hallo,
So weit ich weiß, kann man die Aufgabe mit Hilfe des Chinesischen Restsatzes auflösen. Aber wie? Könnte mir jemand vielleicht einen Ansatz geben?
Danke Im Voraus!
Liebe Grüße
"Ich habe diese Frage in keinen anderen Foren gestellt.!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:23 Mo 28.06.2010 | | Autor: | felixf |
Moin!
> Bestimme die letzten drei Ziffern der Deziemaldarstellung
> der Zahl [mm]7^{512}.[/mm]
> Hallo,
> So weit ich weiß, kann man die Aufgabe mit Hilfe des
> Chinesischen Restsatzes auflösen. Aber wie? Könnte mir
> jemand vielleicht einen Ansatz geben?
Wie unterscheiden sich zwei Zahlen, deren letzten drei Dezimalziffern uebereinstimmen?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:45 Mo 28.06.2010 | | Autor: | ftm2037 |
Ich weiß nicht vorauf du mit dieser Frage hinaus willst!
Vielleicht soll man [mm] 7^{512} [/mm] modulo 1000 ausrechnen. 1000 kann man in 8.125 zerlegen. und die sind zueinander teilerfremd. Soweit hat man die Bedingung im Chinesischen Restsatz. und dann rechnet man [mm] 7^{512} [/mm] modulo 8 und einmal auch modulo 125. Aber das Problem ist, ich kann mit dieser großen Zahl [mm] 7^{512} [/mm] nicht weiter machen. 512 kann man auch [mm] 2^{9} [/mm] schreiben. Aber was bringt das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:39 Mo 28.06.2010 | | Autor: | felixf |
Moin.
> Ich weiß nicht vorauf du mit dieser Frage hinaus willst!
>
> Vielleicht soll man [mm]7^{512}[/mm] modulo 1000 ausrechnen.
Genau darauf will ich hinaus.
> 1000 kann man in 8.125 zerlegen.
Du meist $8 [mm] \cdot [/mm] 125$.
> und die sind zueinander
> teilerfremd. Soweit hat man die Bedingung im Chinesischen
> Restsatz. und dann rechnet man [mm]7^{512}[/mm] modulo 8 und einmal
> auch modulo 125. Aber das Problem ist, ich kann mit dieser
> großen Zahl [mm]7^{512}[/mm] nicht weiter machen. 512 kann man auch
> [mm]2^{9}[/mm] schreiben. Aber was bringt das?
Klar: es ist [mm] $7^{2^9} [/mm] = [mm] (\cdots (((7^2)^2)^2 \cdots)^2$. [/mm] Du quadrierst also, rechnest modulo 8 bzw. 125, quadrierst nochmal, machst nochmal modulo, etc.
Alternativ kannst du auch den Satz von Euler benutzen, falls ihr den hattet.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:27 Mo 28.06.2010 | | Autor: | ftm2037 |
Hallo Felix,
danke für die Hilfe! Nur muss man unbedingt mod 8 und mod 125 rechnen? Ich habe jetzt [mm] 7^{512} [/mm] mod 1000 gerechnet und auf dieses Ergebnis gekommen:
Schritt:
1) [mm] 7^{2} \equiv [/mm] 49 mod 1000
2) [mm] (7^{2})^{2} \equiv 49^{2} \equiv [/mm] 401 mod 1000
3) [mm] ((7^{2})^{2})^{2} \equiv 401^{2} \equiv [/mm] 801 mod 1000
4) [mm] (((7^{2})^{2})^{2} )^{2} \equiv 801^{2} \equiv [/mm] 601 mod 1000
5) [mm] ((((7^{2})^{2})^{2} )^{2})^{2} \equiv 601^{2} \equiv [/mm] 201 mod 1000
6) [mm] (((((7^{2})^{2})^{2} )^{2})^{2})^{2} \equiv 201^{2} \equiv [/mm] 401 mod 1000
7) [mm] ((((((7^{2})^{2})^{2} )^{2})^{2})^{2})^{2} \equiv 401^{2} \equiv [/mm] 801 mod 1000
8) [mm] (((((((7^{2})^{2})^{2} )^{2})^{2})^{2})^{2})^{2} \equiv 801^{2} \equiv [/mm] 601 mod 1000
9) [mm] ((((((((7^{2})^{2})^{2} )^{2})^{2})^{2})^{2})^{2})^{2} \equiv 601^{2} \equiv [/mm] 201 mod 1000
Also sind letzte drei Ziffern: 201.
Ist das so richtig?
Eine ähnliche Aufgabe habe ich auch aber mit [mm] 3^{9999}. [/mm] Ich habe mir überlegt, 9999 in [mm] 3^{2}.11.101 [/mm] zu zerlegen. Aber 101 ist viel zu groß. Oder man schreibt 9999= [mm] 10^{4}-1 [/mm] und somit:
[mm] 3^{9999} [/mm] = [mm] 3^{10^{4} - 1} [/mm] = [mm] (3^{10})^{4} [/mm] . [mm] 3^{-1} [/mm] = [mm] \bruch{3^{10^{4}} }{3}
[/mm]
Dann rechne ich [mm] \bruch{(((3^{10})^{10})^{10})^{10}}{3} \aquiv [/mm] mod 1000. Aber das Problem ist "durch 3 teilen". Gibt es andere Lösung?
Vielleicht muss man das mit dem Satz von Euler machen? Wir haben erst heute Satz von Euler-Fermat gelernt. Ich weiß aber nicht wie man den hier anwendet?
Viele Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:50 Mo 28.06.2010 | | Autor: | felixf |
Moin!
> danke für die Hilfe! Nur muss man unbedingt mod 8 und mod
> 125 rechnen?
Nein. Das macht nur die Zahlen kleiner; wenn 1000 nicht so ein schoener Modulus waer koennte es etwas bringen.
> Ich habe jetzt [mm]7^{512}[/mm] mod 1000 gerechnet und
> auf dieses Ergebnis gekommen:
>
> Schritt:
> 1) [mm]7^{2} \equiv[/mm] 49 mod 1000
> 2) [mm](7^{2})^{2} \equiv 49^{2} \equiv[/mm] 401 mod 1000
> 3) [mm]((7^{2})^{2})^{2} \equiv 401^{2} \equiv[/mm] 801 mod 1000
> 4) [mm](((7^{2})^{2})^{2} )^{2} \equiv 801^{2} \equiv[/mm] 601 mod
> 1000
> 5) [mm]((((7^{2})^{2})^{2} )^{2})^{2} \equiv 601^{2} \equiv[/mm]
> 201 mod 1000
> 6) [mm](((((7^{2})^{2})^{2} )^{2})^{2})^{2} \equiv 201^{2} \equiv[/mm]
> 401 mod 1000
> 7) [mm]((((((7^{2})^{2})^{2} )^{2})^{2})^{2})^{2} \equiv 401^{2} \equiv[/mm]
> 801 mod 1000
> 8) [mm](((((((7^{2})^{2})^{2} )^{2})^{2})^{2})^{2})^{2} \equiv 801^{2} \equiv[/mm]
> 601 mod 1000
> 9) [mm]((((((((7^{2})^{2})^{2} )^{2})^{2})^{2})^{2})^{2})^{2} \equiv 601^{2} \equiv[/mm]
> 201 mod 1000
>
> Also sind letzte drei Ziffern: 201.
>
> Ist das so richtig?
Laut Maple stimmen die letzten drei Ziffern.
> Eine ähnliche Aufgabe habe ich auch aber mit [mm]3^{9999}.[/mm]
> Ich habe mir überlegt, 9999 in [mm]3^{2}.11.101[/mm] zu zerlegen.
> Aber 101 ist viel zu groß. Oder man schreibt 9999=
> [mm]10^{4}-1[/mm] und somit:
Du meinst [mm] $10^5 [/mm] - 1$!
> [mm]3^{9999}[/mm] = [mm]3^{10^{4} - 1}[/mm] = [mm](3^{10})^{4}[/mm] .
Selbst wenn die 4 stimmen wuerde: [mm] $3^{10^4}$ [/mm] ist nicht gleich [mm] $(3^{10})^4$.
[/mm]
> [mm]3^{-1}[/mm] =
> [mm]\bruch{3^{10^{4}} }{3}[/mm]
>
> Dann rechne ich [mm]\bruch{(((3^{10})^{10})^{10})^{10}}{3} \aquiv[/mm]
> mod 1000. Aber das Problem ist "durch 3 teilen". Gibt es
> andere Lösung?
Nun, durch 3 teilen ist auch nicht so schwer, du musst nur das modulare Inverse von 3 modulo 1000 bestimmen. Das geht z.B. mit dem erweiterten euklidischen Algorithmus, der sollte (richtig angewendet) nach zwei Schritten fertig sein.
> Vielleicht muss man das mit dem Satz von Euler machen? Wir
> haben erst heute Satz von Euler-Fermat gelernt. Ich weiß
> aber nicht wie man den hier anwendet?
Nun, was ist denn [mm] $\phi(1000)$? [/mm] Du kannst den Exponenten um [mm] $\phi(1000)$ [/mm] erhoehen oder verringern, ohne den Wert des Ergebnisses zu aendern. Damit kannst du z.B. schonmal die 999 viel kleiner bekommen.
Andernfalls kannst du wie ![[]](/images/popup.gif) hier vorgehen, dann musst du modulo 1000 nur multiplizieren und quadrieren.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:35 Mo 28.06.2010 | | Autor: | ftm2037 |
Ich habe mich vertippt! [mm] 10^{5} [/mm] ist richtig. Die inverse zu 3 mod 1000 ist (-3333). Aber wie soll ich das in meine Rechnung? Ich habe folgendes:
[mm] 3^{2} [/mm] = 9 [mm] \equiv [/mm] 9 mod 1000
[mm] (3^{2})^{5} \equiv 9^5 [/mm] \ 49 mod 1000
[mm] ((3^{2})^{5})^{5} \equiv 49^5 \equiv [/mm] 249 mod 1000
[mm] (((3^{2})^{5})^{5})^2 \equiv 249^2 \equiv [/mm] 1 mod 1000
[mm] ((((3^{2})^{5})^{5})^2)^{1000} \equiv [/mm] 1 mod 1000
Soweit ist ok. Soll ich jetzt die rechte seite mit 3.(-333) multiplizieren? D.h. 1 mit diesem Produkt ersetzen? Denn das ist gleich 1 mod 1000.
Das ergibt dann:
[mm] ((((3^{2})^{5})^{5})^2)^{1000} \equiv [/mm] (3.(-333)) mod 1000 [mm] \Rightarrow [/mm]
[mm] 3^{100000} [/mm] . [mm] 3^{-1} \equiv [/mm] (-333) mod 1000 [mm] \Rightarrow
[/mm]
[mm] 3^{9999}\equiv [/mm] (-333) mod 1000 [mm] \Rightarrow
[/mm]
[mm] 3^{9999}\equiv [/mm] (667) mod 1000
Also sind die letzten drei Ziffern 667.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:00 Mi 30.06.2010 | | Autor: | felixf |
Moin!
> Ich habe mich vertippt! [mm]10^{5}[/mm] ist richtig. Die inverse zu
> 3 mod 1000 ist (-3333). Aber wie soll ich das in meine
> Rechnung?
Na, durch 3 teilen ist das gleiche wie mit dem Inversen von 3 mutiplizieren.
> Ich habe folgendes:
>
> [mm]3^{2}[/mm] = 9 [mm]\equiv[/mm] 9 mod 1000
> [mm](3^{2})^{5} \equiv 9^5[/mm] \ 49 mod 1000
> [mm]((3^{2})^{5})^{5} \equiv 49^5 \equiv[/mm] 249 mod 1000
> [mm](((3^{2})^{5})^{5})^2 \equiv 249^2 \equiv[/mm] 1 mod 1000
> [mm]((((3^{2})^{5})^{5})^2)^{1000} \equiv[/mm] 1 mod 1000
>
> Soweit ist ok. Soll ich jetzt die rechte seite mit 3.(-333)
> multiplizieren? D.h. 1 mit diesem Produkt ersetzen? Denn
> das ist gleich 1 mod 1000.
>
> Das ergibt dann:
>
> [mm]((((3^{2})^{5})^{5})^2)^{1000} \equiv[/mm] (3.(-333)) mod 1000
> [mm]\Rightarrow[/mm]
> [mm]3^{100000}[/mm] . [mm]3^{-1} \equiv[/mm] (-333) mod 1000 [mm]\Rightarrow[/mm]
> [mm]3^{9999}\equiv[/mm] (-333) mod 1000 [mm]\Rightarrow[/mm]
> [mm]3^{9999}\equiv[/mm] (667) mod 1000
>
> Also sind die letzten drei Ziffern 667.
Ein bisschen umstaendlich, aber geht so.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:18 Mi 30.06.2010 | | Autor: | ftm2037 |
Hallo Felix,
danke für deine Hilfe!
Liebe Grüße
|
|
|
|
