Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Große Modulo per GTR berechnen

Große Modulo per GTR berechnen

Universität / Fachhochschule

Algebraische Zahlentheorie

Tags: Algebraische Zahlentheorie, modulo, Modulorechnung, rest, Restklasse

iTobi aktiv_icon

22:02 Uhr, 05.07.2018

Hallo liebe Community,

ich möchte für meinen GTR (Texas Instruments

83

Plus) eine Modulo Funktion schreiben, welche mir für egal welches

x

Modulo

m

den Restwert berechnet.

Ich habe bereits in vielen Foren die einfache Idee gelesen,

\frac{x}{m}

zu rechnen, das Ergebnis davon abzurunden, und das abgerundete Ergebnis von

\frac{x}{m}

abzuziehen. Dieses muss dann nur noch mit

m

multipliziert werden und man hat den Restwert.

Mein Problem bei der ganzen Sache, das abrunden bei größeren Zahlen wie

z . B

28^{43} mod 77

. Diese Zahl ist sehr groß und ist nicht so einfach mit den sichtbaren Nachkommastellen abzurunden

(2.849796 ... E 58)

.

Mein erster Ansatz war eine Schleife, die solange von

x, m

abzieht, bis

x < m

ist. In der Theorie und in einer Programmiersprache, auf einem leistungsfähigeren Computer mit einer stärkeren CPU ist das vermutlich machbar, allerdings braucht so ein GTR dafür schon sehr lange ;-)

Meine zweite Idee war es, mit einer Schleife mit

m

Durchgängen jeweils

x - -

darauf zu überprüfen, ob das Ergebnis eine gerade Zahl ist. Wenn dies der Fall ist, dann ist der aktuelle

x

Wert mein Restwert. Allerdings bin ich in meinem Taschenrechner auch noch auf keine Möglichkeit gestoßen, um eine Zahl darauf zu überprüfen.

Ihr seht also, dass ich mit etwas im Kreis drehe. Hat jemand vielleicht eine gute Idee oder erklärt mir, dass es viel einfacher geht?

Vielen Dank schon einmal im Voraus

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

abakus

22:55 Uhr, 05.07.2018

Berechne 28² und bestimme mit der genannten Methode den Rest mod 77.
Multipliziere den erhaltenen Rest mit 28 und bestimme vom Ergebnis den Rest mod 77.
(Damit hast du den Rest von 28³.)
Multipliziere den erhaltenen Rest mit 28 und bestimme vom Ergebnis den Rest mod 77.
(Damit hast du den Rest von

2 8^{4}

.)
Multipliziere den erhaltenen Rest mit 28 und bestimme vom Ergebnis den Rest mod 77.
(Damit hast du den Rest von

2 8^{5}

.)
... usw.
Du brauchst also lediglich eine Schleife, die fortlaufend die gleichen Operationen wiederholt.

Bummerang

12:00 Uhr, 06.07.2018

Hallo,

das ist eine Aufgabe, da braucht man kaum ein Taschenrechner-Programm, ja man braucht eigentlich überhaupt keinen Taschenrechner. Man sollte als Student eigentlich erkennen, dass sowohl die

28

als auch die

77

durch 7 teilbar sind. Wegen der Teilerfreiheit von 7 und

11,

die

11

stammt von der Zerlegung

77 = 7 \cdot 11,

wird nie der Rest 0 bei der Division von

28^{n}

durch

77

auftauchen. Was potentiell auftauchen kann sind alle durch 7 teilbaren Reste von 7 bis

70

und das sind genau

10

Stück. Da diese

10

kleiner als der Exponent

43

sind, muss es zwangsläufig einen Zyklus geben, in dem sich diese

10

Reste wiederholen. Da 7 und

11

Primzahlen sind, würde ich eine Wiederholung alle

10

Potenzen vermuten. Deshalb berechne ich nach der Methode von abakus mal einige Potenzen, allerdings etwas effektiver:

28^{2} = 784 = 770 + 14 \equiv 14 mod 77

28^{4} = {(28^{2})}^{2} \equiv 14^{2} = 196 = 154 + 42 \equiv 42 mod 77

28^{8} = {(28^{4})}^{2} \equiv 42^{2} = 1764 = 1540 + 224 = 1540 + 154 + 70 \equiv 70 mod 77

28^{12} = 28^{4} \cdot 28^{8} \equiv 42 \cdot 70 = 2940 = 1540 + 1540 - 140 = 1540 + 1540 - 154 + 14 \equiv 14 mod 77

\Rightarrow 28^{12} \equiv 28^{2} mod 77

Damit haben wir einen Zyklus von

10

(könnte auch von 2 oder 5 als Teiler von

10

sein, ist aber egal, auch die

10

bildet einen Zyklus) und wir wissen schon

28^{42} \equiv 28^{2} mod 77 \equiv 14 mod 77

Bleibt als Restaufgabe:

28^{42} = 28^{42} \cdot 28 \equiv 14 \cdot 28 = 392 = 154 + 154 + 84 = 154 + 154 + 77 + 7 \equiv 7 mod 77

Jetzt werden die hier bekannten Krümelkacker sicher feststellen, dass ich zu Beginn behauptet habe, dass man gar keinen Taschenrechner braucht, denen bin ich natürlich noch meine Berechnungen im Kopf schuldig:

28^{2} = (28 - 2) \cdot (28 + 2) + 4 = 26 \cdot 30 + 4 = 26 \cdot 3 \cdot 10 + 4 = 780 + 4 = 784

77 \cdot 10 = 770

14^{2} = 196;

das ist Schulstoff!

77 \cdot 2 = 154

42^{2} = (42 - 2) \cdot (42 + 2) + 4 = 40 \cdot 44 + 4 = 4 \cdot 44 \cdot 10 + 4 = 1760 + 4 = 1764

77 \cdot 20 = 77 \cdot (2 \cdot 10) = (77 \cdot 2) \cdot 10 = 1540

42 \cdot 70 = 42 \cdot 7 \cdot 10 = (280 + 14) \cdot 10 = 1940

1540 + 1540 = 3080

3080 - 2940 = 140

140 = 154 - 14

14 \cdot 28 = 14 \cdot (14 \cdot 2) = (14 \cdot 14) \cdot 2 = 196 \cdot 2 = 392

154 + 154 = 308

84 = 77 + 7

Bummerang

12:00 Uhr, 06.07.2018

Korrektur eines Cut/Paste-Fehlers:

Bleibt als Restaufgabe:

28^{43} = 28^{42} \cdot 28 \equiv 14 \cdot 28 = 392 = 154 + 154 + 84 = 154 + 154 + 77 + 7 \equiv 7 mod 77

Da stand oben statt

28^{43}

ganz links nur

28^{42}

.

Und Korrektur eines Tippfehlers:

42 \cdot 70 = 42 \cdot 7 \cdot 10 = (280 + 14) \cdot 10 = 2940

Da stand oben statt

2940

ganz rechts nur

1940

. Aber war ja ohne Folgen, da nicht im Rechenteil sondern nur im Teil für die Krümelkacker

iTobi aktiv_icon

13:17 Uhr, 06.07.2018

Mir ist vollkommen bewusst, dass sich das ganze relativ einfach ausrechnen lässt, wie du ja bereits gezeigt hast. Ich habe nur nach einer schnelleren Methode gesucht, um schnell und ohne große Zwischenrechnungen Restwerte zu Modulen am Taschenrechner zu berechnen. Das die Problemstellung von Hand einfacher zu lösen ist, als mit einer Funktion war mir bereits bekannt. ;-)

ledum aktiv_icon

00:17 Uhr, 07.07.2018

Hallo die Methode immer wieder

m

abzuziehen sollte man sicher erst für die letzten Schritte verwendn, also im genannten Fall erst mal

2 \cdot 10^{58} \cdot m

abziehen.
dein Programm müsste erstmal große und kleine Zahlen unterschiedlich behandeln,
gruß ledum

ledum aktiv_icon

00:17 Uhr, 07.07.2018

sorry, Doppelpost

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1433006

1432879

	Status: nicht eingeloggt	Noch nicht registriert?