| Autor |
Beitrag |
    
jakuz (Jakuz)
| | Veröffentlicht am Samstag, den 07. Oktober, 2000 - 15:53: | 
|
hy!
weiss jemand, wie man das Inverse einer Zahl in Zm (also in den Restklassen modulo m) mithilfe der Eulerschen Phi-Funktion (liefert die Anzahl der zum Argument teilerfremenden Zahlen <= der Zahl zurueck) und dem euklidischen Algorithmus zur Bestimmung des ggT (durch Division mit Rest) bestimmen kann?
Und warum funktioniert das dann?
danke!! |
Carmichael
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 14:08: |
|
also das mit dem Inversen und phi-Funktion ist klar.
Es gilt in Z/m*:
a^phi(m) = 1 (mod m); a E Z/m*;
(satz von euler)
Beweis:
Sei a E Z/m*
Die Abbildung f:Z/m* -> Z/m* ist bijektiv mit
f(x):= a*x [denn ax=ay => x=y, und |Z/m*|=|Z/m*| ]
Damit gilt für Z/m* = {x1,x2,...,xn) n=phi(m);
x1*x2*....*xn*a^phi(m) = x1*a*x2*a*....*xn*a =
= x1*x2*....*xn;
=> a^phi(m) = 1;
Deshalb: a*a^-1 = a*a^(phi(m)-1) = 1;
Zum euklidische Algorithmus:
weiß nicht genau was da gemeint ist, aber vielleicht nützt dir folgende Formel was:
Summe[d|n] (phi(d)) = n; |
|
