Question

Welcher Rest entsteht bei Division mit Rest von 3^16377493 durch 7 ?

Ich weiß, dass die Lösung dazu Rest = 3 ist, aber ich verstehe nicht, wie ich darauf komme.

Vielen Dank im Voraus !

Answer 1

3^2 mod 7 = 9 mod 7 = 2
3^3 mod 7 = 27 mod 7 = -1

3^(16377493) mod 7
= 3^(5459164·3 + 1) mod 7
= (3^3)^(5459164)·3 mod 7
= (-1)^(5459164)·3 mod 7
= 1·3 mod 7 = 3

Answer 2

Betrachte \(3^1\), \(3^2\), \(3^3\), \(3^4\), \(3^5\), \(3^6\), \(3^7\), \(3^9\) mod 7 und stelle erstaunt fest, dass \(3^1\) den gleichen Rest wie \(3^7\) lässt und dass \(3^2\) den gleichen Rest wie \(3^8\) lässt ...

PS: Fehlerhafte Exponenten korrigiert.

Comments

Und in wie fern hilft mir das, um auf Rest = 3 zu kommen ?

---

Wenn du schon mal weißt, dass das Ergebnis 3 ist:

Auch 3^1 lässt den Rest 3, so wie 3^7  und auch 3^13 und 3^19.

Addiere nun zum Exponenten 19 noch einige Male den Summanden 6. Wenn du nach kurzer Zeit dabei auch den Exponenten 16377493 erhältst, so ist das ein starkes Indiz dafür, dass auch 3^16377493 bei Teilung durch 7 den Rest 3 lassen könnte.

---

Wenn ich das alles hier richtig verstanden habe, geht es jetzt doch nur noch darum, ob

 6 I 16377492, das stimmt, denn

QS (16377492) = 39

3 I 39 damit ist 3 I 16377492

und die Entziffer ist 2

d. h. auch 2 I 16377492 ≅und damit

6 I 16377492

Wenn ich mich nicht irre, hängt das damit zusammen, dass

3 Primitivwurzel mod 7

ist. Es gilt 3 ¹⁺⁶ⁿ  Ξ 3 (mod 7)

---

Es ist so: $$ (1)\quad 3^6 \equiv 1 \mod 7 $$ $$ (2)\quad 16377492 \equiv 1 \mod 6 $$ Beides lässt sich leicht(!) im Kopf ausrechnen.

Damit gilt dann für die eigentliche Rechnung: $$(3)\quad 3^{16377492} = 3^{6\cdot n +1} = \left(3^6\right)^n \cdot 3^1 \equiv 3 \mod 7$$ Das Aufschreiben dauerte länger als das Ausrechnen.

Answer 3

Es ist 3^2=2 mod 7.

Weiter ist 2^3=1 mod 7.

Insgesamt also (3^2)^3=3^6=1 mod 7.

Damit lässt sich der Exponent verkleinern ohne irgendwelche Sätze zu benutzen.