www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Reste großer Zahlen (Modulo)
Reste großer Zahlen (Modulo) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Reste großer Zahlen (Modulo): Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Reste großer Zahlen (Modulo): anhang
Status: (Antwort) fertig Status 
Datum: 19:23 Di 28.03.2006
Autor: mathmetzsch

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]
Bezug
                
Bezug
Reste großer Zahlen (Modulo): Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Reste großer Zahlen (Modulo): ich glaube...
Status: (Antwort) fertig Status 
Datum: 23:49 Di 28.03.2006
Autor: Bastiane

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]


Bezug
                        
Bezug
Reste großer Zahlen (Modulo): Antwort
Status: (Antwort) fertig Status 
Datum: 21:13 Mi 05.04.2006
Autor: felixf

Hallo max!

> 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?

Es gibt noch weitere Methoden:
- Einmal (passend zu deiner zweiten Methode) kannst du den []kleinen Satz von Fermat zusammen mit []folgender Rechenregel fuer die Eulersche [mm] $\varphi$-Funktion [/mm] benutzen, um das ganze zu vereinfachen, indem du den Exponenten $n$ als $n = q [mm] \varphi(x) [/mm] + r$ schreibst mit $0 [mm] \le [/mm] r < x$, wobei $x$ der Modulus ist: dann ist [mm] $a^n [/mm] = [mm] a^{q \varphi(x) + r} [/mm] = [mm] (a^{\varphi(x)})^q a^r \equiv 1^q a^r \equiv a^r \pmod{x}$. [/mm]
- Weiterhin kannst du per []Exponentiation by Squaring sehr effizient [mm] $a^n \pmod{x}$ [/mm] ausrechnen, indem du den im Link angegebenen Algorithmus benutzt.

LG Felix


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]