Restbestimmung bei grossen Zahlen

Neue Frage »

telli Auf diesen Beitrag antworten »
Restbestimmung bei grossen Zahlen
Meine Frage:
Hallo MatheBoard Freunde,

Ich habe mir einige Gedanken zur Restberechnung bei grossen Zahlen gemacht.
Das ist wahrscheinlich Stoff der Zahlentheorie kenne mich aber in diesem Bereich nur knapp aus.

Meine Frage ist: Wie kann ich bei einer Division den Rest bestimmen, ohne die Division durchführen zu müssen?

Also:
wobei

Als Beispiel:

(c = 3)

Ich kann mir vorstellen, dass die konventionelle Methodik für Zahlen mit 100'000 Ziffern nicht mehr so effizient funktionieren wird.

Gibt es hierfür Möglichkeiten, wie mann das subtiler lösen kann? Kann mir das jemand anhand des Beispiels erklären? Danke!

Meine Ideen:
habe keine..
lgrizu Auf diesen Beitrag antworten »
RE: Restbestimmung bei grossen Zahlen
Additive Zerlegung:




So kann man dann weiter fortfahren....
telli Auf diesen Beitrag antworten »

Danke für deine Antwort!

Hmm verstehe ich das richtig, es gilt also: (u+v)mod x = (u)mod x + (v)mod x ?
Ich suche eine zerlegung für die gilt: (u)mod x = 0 so dass (u+v)mod x = (v)mod x ?

Wie finde ich aber eine solche Zerlegung? in dem Beispiel ist (u)mod x = 15'000'000 mod x
Der erste Schritt ist mir klar und das 15*10^6 ein Vielfaches von 15 ist auch einleuchtend, was aber wenn der Teiler ebenfalls eine grosse Zahl ist?

Sagen wir dann wird es doch schwierig eine solche Zerlegung zu finden?
Helferlein Auf diesen Beitrag antworten »

Die Größe der Zahlen ändert aber nichts am Prinzip der schrittweisen Verkleinerung, bis wir eine offensichtliche Größe haben.

Zum Beispiel so:

28.925.583 - 36.542*500 = 28.925.583 - 18.271.000 = 10.654.583
10.654.583 - 36.542*200 = 10.654.583 - 7.308.400 = 3.346.183
3.346.183 - 36.542*50 = 3.346.183 - 1.827.100 = 1.519.083
1.519.083 - 36.542*20 = 1.519.083 - 730.840 = 788.243
788.243 - 36.542*20 = 788.243 - 730.840 = 57.403

Dabei habe ich bewusst einfache Rechnungen genutzt. Wenn man genauer teilt, braucht das Verfahren natürlich weniger Schritte. Alternativ kannst Du auch mit negativen Ergebnissen arbeiten, um größere Schritte zu verwenden.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »