Modulo mit sehr großen Zahlen

Question

Ich muss die Aufgaben

(2434345781*4566199813) mod 3 und

127³⁷ mod 7 berechnen.

Ich brauche Hilfe, da ich nicht weiß wie ich auf den Rest kommen soll bei diesen hohen Zahlen.

Answer 1

Hi,

die zweite Zahl kannst du mit Hilfe von \(127 \mod 7 =1 \) und \(37 \mod 7=2\) auch einfach umschreiben :)

An die erste Zahl würde ich wie folgt rangehen:

\(2434345781=2400000000+30000000+4200000+120000+24000+1500+270+9+2\)

Alle Summanden bis auf den letzten sind Modulo 3 einfach 0 :)

Comments

Danke für die Antwort.

Ich merke gerade das ich mich vertippt habe und das ich eigentlich 125³⁷ mod 7 rechnen soll. Habe das dann mal mit deiner Formel gerechnet und kriege für 125 den Rest 6 raus. Ich verstehe den Zusammenhang zwischen 125 mod 7 und 37 mod 7 nicht, was muss ich mit den beiden Resten jetzt tun ?

---

Bitte. Du musst jetzt einfach \(6^2\) berechnen :)

---

Jetzt ist alles klar. Nochmal Danke für die Hilfe.

---

Es ist doch nicht alles klar :D

Ich habe die Aufgabe bei WolframAplha für ein Kontrollergebnis eingegeben, da ist die Lösung Rest=2. Offensichtlich muss ich ja jetzt noch weiterrechnen um auf meinen Rest zu kommen. Also was muss ich jetzt mit der 36 anstellen ? 

---

Sorry, mein Fehler. Im Exponenten darf man nicht Modulo rechnen. Wir haben also \(6^{37}  =36^{18}  \cdot 6 =1^{18}  \cdot 6 =6\).

---

Tut mir leid aber ich verstehe immer noch nicht wie ich jetzt auf mein Ergebnis komme, da 6 ja nicht mein Rest ist. Auch verstehe ich nicht wie du auf die 1¹⁸ *6 kommst, hast du 36 mod 7 berechnet und bist dadurch auf die 1 gekommen ? 

---

Doch, 6 ist dein Rest:

$$ 125^{37} \equiv 6 \mod (7) $$

Der Rechenweg ist folgender:

$$ 125^{37} \equiv 6^{37} \mod (7) $$

da \( 125 \equiv 6 \mod (7) \) nun schreiben wir diese Potenz etwas um:

$$ 6^{37} = 6^{36} * 6 = \left( 6^2 \right) ^ {18} * 6 = 36^{18} * 6 $$

dann erhältst du

$$ 125^{37} \equiv 6^{37} \equiv 36^{18} * 6 \equiv 1^{18} * 6 \equiv 6 \mod (7) $$

da \( 36 \equiv 1 \mod (7) \).

---

Oh man, hat echt lange gedauert aber ich hab es endlich kapiert. Danke EmNero für die Erklärung.

---

+t                                  .

Answer 2

127 mod 7 ergibt 1, da 126 durch 7 teilbar ist.

Also ist auch 127³⁷ mod 7 gleich 1.

Bei der ersten betrachte beide Zahlen einzeln und bedenke:

Zahl geht durch 3, wenn die Quersumme durch 3 geht.

Comments

Vielen Dank für die Antwort, ich hab aber noch 2 Fragen um mich zu vergewissern das ich die Aufgaben richtig bearbeite.

Muss ich bei der 1. Aufgabe den Rest der beiden Quersummen nur noch multiplizieren? 

Zur 2. Aufgabe, ist es immer möglich die Potenz zu ignorieren um den Rest zu berechnen?

---

Muss ich bei der 1. Aufgabe den Rest der beiden Quersummen nur noch multiplizieren? 

Ja und dann ggf. noch davon den Rest mod 2.

Zur 2. Aufgabe, ist es immer möglich die Potenz zu ignorieren um den Rest zu berechnen?

Nein, aber du kannst von der Basis den Rest nehmen und den dann potenzieren

und das war heir besonders nett, weil das eine 1 war.

Answer 3

(2434345781*4566199813) mod 3 =

(24445781*45181) mod 3 =

(47*1) mod 3 =

11 mod 3 =

2 mod 3.

In dieser "Rechnung" habe ich zunächst alle Ziffern gestrichen (rot markiert), die Vielfache von 3 waren. Im zweiten Schritt habe ich paarweise Ziffern gestrichen (ebenfalls rot markiert), die in ihrer Summe Vielfache von 3 waren. Im dritten Schritt habe ich den Faktor 1 weggelessen und die linke Seite durch ihre Quersumme ersetzt. Im letzten Schritt habe ich noch einmal die Quersumme gebildet. Bei keinem Schritt musste ich mit Zahlen jenseits des Zahlenraums bis 10 rechnen. Ich hoffe, ich habe wenigstens andeutungsweise dargelegt, wie vielfältig und wirkungsvoll die Methoden zum Rechnen modulo 3 im 10er-System sein können!

Comments

Die (korrigierte) zweite Aufgabe geht auch recht einfach:

125³⁷ mod 7 =

(-1)³⁷ mod 7 =

(-1) mod 7 =

6 mod 7.

Answer 4

(2434345781 * 4566199813) MOD 3

= 2434345781 MOD 3 * 4566199813 MOD 3

= (2 * 1) MOD 3 = 2

----------

125^37 MOD 7

= (125 MOD 7)^37 MOD 7

= 6^37 MOD 7

= (6 * 6^36) MOD 7

= (6 * 36^18) MOD 7

= (6 * (36 MOD 7)^18) MOD 7

= (6 * 1^18) MOD 7

= (6 * 1) MOD 7

= 6 MOD 7

= 6