Eulerfunktion

15.11.2004, 19:25	Schmidtl	Auf diesen Beitrag antworten »
Eulerfunktion Hallo! Ich brauche für die RSA - Verschlüsselung die Eulerfunktion. Dazu habe ich mich unter http://www.matheboard.de/lexikon/Satz_vo...,definition.htm informiert aber bin nicht so richtig schlau geworden. Ich habe folgende Aussage: vieh(55) = 40. Wie komme ich dort drauf?? Kann mir das bitte jmd. einfach und verständlich erklären!? Danke! MfG
15.11.2004, 19:44	Leopold	Auf diesen Beitrag antworten »
Schrecklich! Vieh(55)! Schreibe doch bitte phi(55)! Die Eulersche $\begin{eqnarray} \varphi \end{eqnarray}$ -Funktion kannst du so definieren: $\begin{eqnarray} \varphi(n) = \mbox{Anzahl der zu} \ n \ \mbox{teilerfremden Zahlen} \ \geq 1 \ \mbox{und} \ \leq n \end{eqnarray}$ Oder auch so: $\begin{eqnarray} \varphi(n) = n \cdot \prod_{p\|n} \left( 1-\frac{1}{p} \right) \end{eqnarray}$ Das Produkt erstreckt sich über alle Primteiler $\begin{eqnarray} p \end{eqnarray}$ von $\begin{eqnarray} n \end{eqnarray}$ . Beispiel: $\begin{eqnarray} \varphi(15) \end{eqnarray}$ erste Methode: 1,2,3,4,5,6,7,8,9,10,11,12,13,,15 Die roten sind die zu 15 teilerfremden Zahlen. Das sind 8 Stück. Daher gilt: $\begin{eqnarray} \varphi(15)=8 \end{eqnarray}$ zweite Methode: Die Primteiler von 15 sind 3 und 5. Über diese erstreckt sich das Produkt: $\begin{eqnarray} \varphi(15) = 15 \cdot \left( 1-\frac{1}{3} \right)\left( 1-\frac{1}{5} \right) = 15 \cdot \frac{2}{3} \cdot \frac{4}{5} = 8 \end{eqnarray}$
15.11.2004, 20:04	Schmidtl	Auf diesen Beitrag antworten »
Hallo! Gut danke! Ich hatte inzwischen die Variante phi(p * q) = (p - 1) * (q - 1) gefunden, welche sich uach mit deiner Variante deckt. MfG

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »