Restklassen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1. Man berechne folgende Divisionsreste:
a) [mm] 2^6 rem 7 [/mm]
b) [mm] 3^9rem 13 [/mm]
c) [mm] 5^1^2^5 rem 127 [/mm]
|
Hallo,
ich habe bereits die Aufgaben a)-b) gerechnet. Das Prinzip ist zwar einfach doch wie bekomme ich eine Teilerklasse von einer Potenz, die so hoch ist wie in c)? Ich habe es bereits mit Zerlegen versucht doch ich komme dabei auf kein Ergebnis.
Schoene Gruesse
Mathestudent
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:02 Fr 24.10.2008 | | Autor: | abakus |
> 1. Man berechne folgende Divisionsreste:
>
> a) [mm]2^6 rem 7[/mm]
>
> b) [mm]3^9rem 13[/mm]
>
>
> c) [mm]5^1^2^5 rem 127[/mm]
Sicher, dass es im Exponenten 125 und nicht 126 heißt?
Nach dem kleinen Satz von Fermat ist [mm] a^{p-1}\equiv [/mm] 1 (p).
Da 127 eine Primzahl ist, gilt also
[mm] 5^{126}\equiv [/mm] 1 (127).
Aber warte mal.
Es ist [mm] 5^3=125 [/mm] und 125 [mm] \equiv [/mm] -2 (127)
Wegen [mm] (-2)^7=-128=-127-1 [/mm] gilt [mm] (5^3)^7\equiv [/mm] -1 (127),
also [mm] 5^{21}\equiv [/mm] -1 (127).
Dann gilt auch [mm] 5^{105}\equiv [/mm] -1 (127).
Jetzt brauchst du nur noch den Rest von [mm] 5^{20}.
[/mm]
Gruß Abakus
>
> Hallo,
>
> ich habe bereits die Aufgaben a)-b) gerechnet. Das Prinzip
> ist zwar einfach doch wie bekomme ich eine Teilerklasse von
> einer Potenz, die so hoch ist wie in c)? Ich habe es
> bereits mit Zerlegen versucht doch ich komme dabei auf kein
> Ergebnis.
>
> Schoene Gruesse
>
> Mathestudent
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
Ich habe versucht [mm] 5^20 [/mm] durch 127 zu teilen, aber ich habe da einen Rest von 106. Stimmt das?
|
|
|
| |
|
Hallo mathestuden,
> Ich habe versucht [mm]5^20[/mm] durch 127 zu teilen, aber ich habe
> da einen Rest von 106. Stimmt das?
Das stimmt leider nicht.
Um den Rest zu bestimmen gehe so vor:
Berechne
[mm]5^{1}\equiv 5 \ \left(127\right)[/mm]
[mm]5^{2}\equiv 5 * 5 \equiv \dots \ \left(127\right)[/mm]
[mm]5^{4}\equiv 5^{2} * 5^{2} \equiv \dots \ \left(127\right)[/mm]
[mm]5^{8}\equiv 5^{4} * 5^{4} \equiv \dots \ \left(127\right)[/mm]
[mm]5^{16}\equiv 5^{8} * 5^{8} \equiv \dots \ \left(127\right)[/mm]
Stelle dann die Zahl 20 als Summe von 2er-Potenzen dar.
Gruss
MathePower
|
|
|
| |
|
Was soll ich denn mit einer 20? Ich verstehe den Beitrag nicht. Ich habe dann nach der Aussage 5^128. Was soll das bringen?
|
|
|
| |
|
Hallo mathestuden,
> Was soll ich denn mit einer 20? Ich verstehe den Beitrag
> nicht. Ich habe dann nach der Aussage 5^128. Was soll das
> bringen?
Es bringt das, dass Du nicht mit großen Zahlen herumhantieren musst.
Zerlege nun 20 in 2er-Potenzen:
[mm]20=2^{4}+2^{2}[/mm]
Dann ist
[mm]5^{20} \equiv 5^{2^{4}+2^{2}} \equiv 5^{2^{4}}*5^{2^{2}} \equiv 5^{16}*5^{4} \ \left(127\right)[/mm]
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:55 Fr 24.10.2008 | | Autor: | abakus |
> Hallo mathestuden,
>
> > Was soll ich denn mit einer 20? Ich verstehe den Beitrag
> > nicht. Ich habe dann nach der Aussage 5^128. Was soll das
> > bringen?
Ich hatte dir schon den Rest von [mm] 5^{105} [/mm] serviert. Um auf [mm] 5^{125} [/mm] zu kommen, musst du das noch mit (dem Rest von) [mm] 5^{20} [/mm] multiplizieren.
Gruß Abakus
>
>
> Es bringt das, dass Du nicht mit großen Zahlen
> herumhantieren musst.
>
> Zerlege nun 20 in 2er-Potenzen:
>
> [mm]20=2^{4}+2^{2}[/mm]
>
> Dann ist
>
> [mm]5^{20} \equiv 5^{2^{4}+2^{2}} \equiv 5^{2^{4}}*5^{2^{2}} \equiv 5^{16}*5^{4} \ \left(127\right)[/mm]
>
> Gruß
> MathePower
|
|
|
| |
|
Hallo Abakus und Mathepower,
ich habe mittlerweile ein etwas anderes Verfahren entdeckt. Der Rest ist 51. Vielen Dank für eure Beiträge.
Schöne Grüße
Mathestudent
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:37 Sa 25.10.2008 | | Autor: | abakus |
> Hallo Abakus und Mathepower,
>
> ich habe mittlerweile ein etwas anderes Verfahren entdeckt.
Lässt du uns an deinem Wissen teilhaben?
> Der Rest ist 51. Vielen Dank für eure Beiträge.
>
> Schöne Grüße
>
> Mathestudent
|
|
|
| |
|
Aber klar doch! 
Also ich habe [mm] 5^1^2^5 [/mm] aufgesplittet in [mm]\left(\left(5^5\right)^5\right)^5 [/mm].
=> [mm] 5^5=3125 [/mm] Der Rest durch 127 ist 77
=> [mm] 77^5=2706784157 [/mm] Der Rest ist 10
=> [mm] 10^5=100000 [/mm] Der Rest ist daraus 51.
Ich habe das Verfahren mal mit anderen kleineren Potenzen probiert.
Schöne Grüße
Mathestudent
|
|
|
|
