Reste großer Zahlen (Modulo) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:30 Di 28.03.2006 | | Autor: | max43 |
| Aufgabe | | Welcher Rest ergibt sich, wenn man [mm] irgendeinegrossezahl^{anderezahl} [/mm] durch x teilt? Beispielsweise [mm] 15^{83} [/mm] oder [mm] 20576^{42} [/mm] |
Hallo zusammen,
habe mir die vorangegangenen Postings zum Thema Modulo-Rechnung angeschaut, konnte aber leider keine allgemeine Vorgehensweise zur genannten Aufgabe finden. Problem: wie macht man sowas OHNE Taschenrechner in halbwegs kurzer Zeit? Gibts da ne Art Kochrezept für solche Aufgaben? Habe versucht, den kleinen Satz von Fermat darauf anzuwenden, bisher leider ohne Erfolg... Freue mich über Vorschläge, Links, etc., vielleicht hilfts ja nicht nur mir.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
sieh dir mal den Anhang an. Da findest du andere Beispiele, die dir helfen sollten.
Viele Grüße
Daniel
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:34 Di 28.03.2006 | | Autor: | max43 |
Vielen vielen Dank für die schnelle Antwort!
Sehr schön mal verschiedene Wege zu sehen sowas zu rechnen. Sehe ich das richtig so:
-entweder man hat Glück und findet periodische Wiederholungen der Reste (z.B. bei geraden/ungeraden Potenzen),
-oder man sucht sich eine möglichst kleine Potenz, die gerade den Rest 1 lässt und versucht diese dann "rauszuziehen"?
Letztere Möglichkeit kann einen ganz schön ins Schwitzen bringen wenn man alles im Kopf ausrechnen muss :) Geht das evtl. auch anders?
|
|
|
| |
|
Hallo!
> Vielen vielen Dank für die schnelle Antwort!
> Sehr schön mal verschiedene Wege zu sehen sowas zu
Sind das so unterschiedliche Möglichkeiten? Ich sehe da eigentlich höchstens zwei Methoden... Aber den Link finde ich echt klasse! Hab's mir direkt gespeichert. 
> rechnen. Sehe ich das richtig so:
> -entweder man hat Glück und findet periodische
> Wiederholungen der Reste (z.B. bei geraden/ungeraden
> Potenzen),
Mmh, also ich glaube, meistens (oder sogar immer?) gibt es so eine Periode. Man muss nur evtl. etwas länger suchen.
> -oder man sucht sich eine möglichst kleine Potenz, die
> gerade den Rest 1 lässt und versucht diese dann
> "rauszuziehen"?
Meinst du z. B. bei dem 4. Beispiel? Das liegt aber nicht daran, dass man sich etwas sucht, das Rest 1 lässt, sondern man stellt den Exponenten nur als Produkt von Exponenten dar. Und dadurch ergibt sich glaube ich quasi wieder eine Wiederholung. Also 36=9*4, also [mm] 17^{36} [/mm] = [mm] \left(17^9\right)^4. [/mm] Und [mm] 17^9 [/mm] haben wir schon herausgefunden, dann müssen wir dieses Ergebnis nur noch "hoch 4" nehmen. Wobei das hier mit der 1 als "Zwischenergebnis" natürlich sehr einfach geht.
Ich hoffe mal, das stimmt so. Hab' mich damit nur mal kurz glaube ich in unserer LA-Vorlesung beschäftigt, und ab und zu mal hier im Forum.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
![[]](/images/popup.gif){kind=small}
kleinen Satz von Fermat