FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Mathematik

Potenzen und Restklassen

Potenzen und Restklassen 2010-01-16 00:05
Benjamin
Moin!

In meiner Übungsgruppe wurde mir heute die Frage gestellt, ob man beim Modulo-Rechnen auch
den Exponenten als Restklasse betrachten kann, also ob

n^m (mod p) = n^(m mod p) gilt.

Dazu ein Gegenbeispiel:

2^5 = 32 = 2 (mod 3)
2^(5 mod 3) = 2^2 = 4 = 1 (mod 3)

Ich hoffe ich hab deine Frage damit beantwortet.
Ansonsten kannst du hier noch Rückfragen stellen.

Schönes Wochenende euch allen!
Benjamin

RE: Potenzen und Restklassen 2010-01-16 02:12
Wulf
Selbstverständlich kann man den Exponenten als Restklasse betrachten, und zwar ist das Z_q, wobei q die Ordnung der Gruppe ist.

n^m (mod p) = n^(m (mod q)) (mod p)

Wenn p prim ist, gilt q = p - 1; allgemein nimmt man die eulersche phi-Formel.

Beispiel:
2^5 = 32 = 2 (mod 3)
2^7 = 2^5 = 2^3 = 2^1 = 2^-1 = 2^9 = 2^(7 (mod (3 - 1))) (mod 3)