Modulo 693 mit sehr großen Zahlen

Question

Aufgabe: 777777777778^777777777778  mod 693

Problem/Ansatz:

Ich weiß, dass 574 das Ergebnis ist, da ich es in ein Java-Script eingegeben habe. Meine Frage aber ist wie der Rechenweg genau ist. mit kleineren Zahlen weiß ich wie es geht.

Answer 1

693 ist 77*9

Diese riesige Potenz lässt erkennbar den Rest 1 bei Teilung durch 77,

777777777778 lässt den Rest 4 bei Teilung durch 9, dann lässt 777777777778³ (und alle weiteren Potenzen von 777777777778 mit einem durch 3 teilbaren Exponenten) den Rest 1 bei Teilung durch 9.

Comments

also 77777777778⁹  mod 9 Ergebt bei mir Rest 7.

Und ich versteh nicht ganz in wie weit mich das alles weiter bringt

Answer 2

Ich weiß, dass 574 das Ergebnis ist, da ich es in ein Java-Script eingegeben habe.

Bist du sicher, bei der Eingabe keinen Fehler gemacht zu haben?

Ich bekomme mit einem anderen Algebra-Programm 463 heraus.

übrigens: 777777777778=7/9·(10¹²-1)+1

Comments

Eingegeben habe ich es Richtig da bin ich mir sicher und ich weiß auch, dass das Programm Richtig läuft, aber kann trotzdem am Programm liegen.

Versteh trotzdem nicht wie man zur Lösung kommen sollte, da der Wert so groß ist bei Teilung von der Basis durch 693 der Taschenrechner Rundet

---

Was bedeutei dein Satz: Ich weiß auch, dass das Programm richtig läuft, aber kann trotzdem am Programm liegen..

Ein Taschenrechner ist sicher nicht das richtige Werkzeug.

---

Wolfram Alpha hätte auch 463 heraus

https://www.wolframalpha.com/input/?i=777777777778%5E777777777778+mod+693

Und Wolframalpha würde ich mehr vertrauen als einem unbekannten Java-Skript.

Wenn 574 die richtige Lösung ist, dann schau mal ob du die Aufgabe hier vollständig richtig angegeben hast.

Answer 3

$$777777777778^{777777777778}  \text{ mod } 693 \equiv\dots$$Die Basis kann mod 693 verkleinert werden: $$463^{777777777778}  \text{ mod } 693 \equiv\dots$$Da Modul und Exponent teilerfemd sind, kann nach dem Satz von Euler der Exponent mod \(\varphi(693)=360\) verkleinert werden: $$463^{58}  \text{ mod } 693 \equiv\dots$$Jetzt ist auch die Potenz taschenrechnerfähig.

Comments

Jetzt bin ich ganz verwirrt also lag das Programm falsch mein Lösen der Aufgabe?