Seltsames bei Modulo-Rechnung

Neue Frage »

otto123 Auf diesen Beitrag antworten »
Seltsames bei Modulo-Rechnung
Edit (mY+): "Seltsamer" Titel wurde modifiziert.

Hallo ich habe mal eine Frage:


Zunächst ein Beispiel, damit man ganz einfach versteht, in welche Richtung meine Frage zielt.

Wir haben N = P*Q = 7*13 = 91 (Multiplikation zweier verschiedener Primzahlen)

Dann bilden wir die Werte


a_0 = 4^0 mod 91 = 1
a_1 = 4^1 mod 91 = 4
a_2 = 4^2 mod 91 = 16
a_3 = 4^3 mod 91 = 64
a_4 = 4^4 mod 91 = 74
a_5 = 4^5 mod 91 = 23


a_6 = 4^6 mod 91 = 1
a_7 = 4^7 mod 91 = 4
a_8 = 4^8 mod 91 = 16
a_9 = 4^9 mod 91 = 64
a_10 = 4^10 mod 91 = 74
a_11 = 4^11 mod 91 = 23

...
...

Die Werte wiederholen sich periodisch.


Das interessante ist nun, dass wenn man die Werte einer Periode addiert, sich ein Vielfaches von N = 91 ergibt. In unserem Fall haben wir

S = 1+4+16+64+74+23 = 182 = 2*91



Dies verallgemeinern und präzisieren wir: Gegeben sein eine Zahl N = P*Q, wobei

* P und Q ungerade Primzahlen sind
* P =/= Q

Weiters wählt man eine Zahl B für die gilt: 2 < B < N und gcd(B,N) = 1 (B ist also nicht ein Vielfaches von P oder Q)

Dann bildet man die Werte der Reihe

a_0 = B^0 mod N
a_1 = B^1 mod N
a_2 = B^2 mod N
...
...


bis sich die Werte zu wiederholen beginnen. Dann bildet man die Summe der Werte einer Periode, und stellt fest, dass sich als Summe immer das Vielfache von N ergibt, mit folgender Ausnahme, nämlich wenn B die Form

B = r*P + 1 oder
B = s*Q + 1

(mit r,s = 1,2,3,4,...)


annimmt.




In obigem Beispiel sind die Ausnahmen bei

B = 1*7 + 1 = 8
B = 2*7 + 1 = 15
B = 3*7 + 1 = 22
B = 4*7 + 1 = 29
...
...

und

B = 1*13 + 1 = 14
B = 2*13 + 1 = 27
B = 3*13 + 1 = 40
...
...


usw.


Z.B. wenn B = 8 gewählt wird, dann ergibt sich als Summe S = 130, und das ist kein Vielfaches von N=91.



Für obiges Beispiel mit N = P*Q = 7*13 = 91 gebe ich hier eine Tabelle mit verschiedenen B und den Summen an:

B = 2 S = 364 = 91 · 4
B = 3 S = 182 = 91 · 2
B = 4 S = 182 = 91 · 2
B = 5 S = 546 = 91 · 6
B = 6 S = 455 = 91 · 5
B = 8 S = 130 = 91 · 10/7 Ausnahme
B = 15 S = 481 = 91 · 37/7 Ausnahme
B = 16 S = 91 = 91 · 1
B = 17 S = 273 = 91 · 3
B = 18 S = 546 = 91 · 6
B = 19 S = 546 = 91 · 6
B = 20 S = 455 = 91 · 5
B = 22 S = 52 = 91 · 4/7 Ausnahme
B = 23 S = 182 = 91 · 2
B = 24 S = 546 = 91 · 6
B = 25 S = 273 = 91 · 3
B = 27 S = 28 = 91 · 4/13 Ausnahme
B = 29 S = 52 = 91 · 4/7 Ausnahme
B = 30 S = 273 = 91 · 3
B = 31 S = 546 = 91 · 6
B = 32 S = 364 = 91 · 4
B = 33 S = 546 = 91 · 6
B = 34 S = 182 = 91 · 2
B = 36 S = 195 = 91 · 15/7 Ausnahme
B = 37 S = 364 = 91 · 4
B = 38 S = 273 = 91 · 3
B = 40 S = 266 = 91 · 38/13 Ausnahme
...
...
...



Ich verstehe leider zwei Dinge nicht:
1) Wieso ergibt sich als Summe meist ein Vielfaches von N
2) Wie kann man die Ausnahmen erklären?
tmo Auf diesen Beitrag antworten »

Sei die Periodenlänge in Abhängigkeit von B.

Dann ist:



Nun ist aber .

Und am Nenner sieht man auch direkt wo die Ausnahmen herkommen Augenzwinkern
otto123 Auf diesen Beitrag antworten »
Seltsames bei Modulo-Rechnung
Danke für die Antwort, die Summenformel erhellt die Situation. Leider verstehe ich die Zusammenhänge noch nicht ganz.

Wie kann man den Formeln entnehmen, dass die Summe der a_k immer ein Vielfaches von N ist, außer wenn B von einer ganz bestimmten Form ist (wie im Eingangsbeitrag angegeben)?
Reksilat Auf diesen Beitrag antworten »
RE: Seltsames bei Modulo-Rechnung
Hi otto,

tmo hat meiner Meinung nach alles gesagt, was für Deine Frage nötig ist. Bitte nenne konkret Deine Probleme bei seiner Antwort, denn ausführlicher kann man es eigentlich kaum schreiben, wenn man nicht noch die Grundlagen der Modulorechnung erklären will.

Gruß,
Reksilat.
otto123 Auf diesen Beitrag antworten »

Danke nochmal an alle, jetzt habe ich es auch kapiert. Hammer
Neue Frage »
Antworten »



Verwandte Themen

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