"Geometrische" Summenformel für modulare Exponentiation

Neue Frage »

Angelhakenname Auf diesen Beitrag antworten »
"Geometrische" Summenformel für modulare Exponentiation
Meine Frage:
Durch Zufall bin auf folgendes Problem gestoßen:

Gibt es eine allgemeine Summenformel für:

(a und p teilerfremd)?

Wie ich überhaupt darauf komme, dass es eine gibt ist ganz einfach: Ich habe mal ein paar Beispiele bei WolphramAlpha eingegeben und dieses spuckt mir Formeln aus, von denen ich keinen Schimmer habe wie man auf sie kommen könnte.

Meine Ideen:
Ich habe schon die Umwandlung des modulo-Terms in eine Gaußklammer versucht, das bringt einen aber auch nicht wirklich weiter. Für ein Beispiel mit niedrigen p, wie zum Beispiel p=3 ist es relativ einfach eine Formel zu finden:

a^k mod 3 drei nimmt immer abwechselnd die Werte 1 und 2 an. Dadurch ist die Summe gleich der folgenden:



Daraufhin erhält man mit konventionellen Methoden:

(1-(-1)^n+6 n)/4

Wolphram stellt seine Formel allerdings mit Gaußklammern dar, was mich vermuten lässt, dass es andere Algorithmen verwendet...
Neue Frage »
Antworten »



Verwandte Themen

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