Gestern
habe ich mich, wie an so vielen Samstagen mit Gerald getroffen und versprochen noch ein paar Bemerkungen zu unserem Gespraech an dieser Stelle zu hinterlassen. Bei dem Paradoxon ueber das wir vielleicht gestolpert sind, handelt es sich um das sogenannte Bertrandsche Paradoxon. Es ist ganz unten auf der Seite, vielleicht hat es ja wirklich was mit dem Dilemma gestern zu tun?
Dann wolte ich dir noch den schoenen Weg vom Chinesischen Restsatz zur Multiplikativitaet der Eulerschen Phi-Funktion kurz anreissen:
Zuerst haben wir also ein Kriterium fuer die Eindeutige Loesbarkeit eines Kongruenzgleichungssystems (Die Moduln sind relativ prim), das wir erst mal elementar (ausrechnen) beweisen. Daraus leiten wir einen sehr wichtigen Isomorphismus der Restklassen von m=n1*n2*…*nl (teilerfremd, wie in der Vorraussetzung zum C.R.)
R(m)< ->R(n1)xR(n2)x…xR(nl) her, das ist genau der den man manchmal auch zuerst beweist und daraus dann den Reststatz folgert..)
Nun wollen wir Phi(m) herausfinden und betrachten zuerst m=m1*m2 (teilerfremd).
Dafuer schaut man sich das Problem
x=a1(modm1)
x=a2(modm2)
an. Wenn wir jetzt a1 in R(m1) und a2 in R(m2) variieren lassen, wieviele solcher verschiedenen und eindeutigen x koennen wir bestimmen? Mit dem Chinesischen Restsatz genau eins fuer jedes Paar (a1,a2). Und es sind (nach Definition von m1,m2 genau die x die teilerfremd zu m sind). Also brauchen wir, um die Anzahl aller zu m teilerfremden Zahlen zu kennen, nur die Menge der Paare (a1,a2) zu bestimmen. Wieviele Elemente sind in den jeweiligen Restklassen? Genau Phi(m1) bzw. Phi(m2)!
Damit folgt: Phi(m)=Phi(m1)*Phi(m2). Das kann jetzt bis zur Zerlegeung in Primzahlpotenzen iteriert werden (na gut den pathologischen Fall Phi(1) zeigt man schnell so).
Also ist er nicht schoen und motiviert zu schoenem, dieser Chinesische Restsatz? Ja das ist rethorisch.