Eulersche Phi-Funktion

12.09.2004, 20:11	Tobias	Auf diesen Beitrag antworten »
Eulersche Phi-Funktion Hallo zusammen, ich beschäftige mich gerade mit der Euler'schen Phi-Funktion $\begin{eqnarray} \varphi \end{eqnarray}$ . $\begin{eqnarray} m, n \in \mathbb{N} \end{eqnarray}$ ( m teilt n ) Zu zeigen ist: $\begin{eqnarray} m \| n \end{eqnarray}$ dann auch $\begin{eqnarray} \varphi(m) \| \varphi(n) \end{eqnarray}$ . Ansatz: $\begin{eqnarray} m \| n \Rightarrow n = t\cdot m, \; t \in \mathbb{N} \qquad \varphi(n) = \varphi(m\cdot t) \end{eqnarray}$ Die Multiplikativität wäre hier aber nur anwendbar, wenn m und t relativ prim wären. Sind sie aber leider nicht unbedingt. Ich benötige also einen anderen Ansatz und bin gerade ein bisschen verloren. Bin über jeden Tipp dankbar, MfG - Tobias
13.09.2004, 00:05	Soap	Auf diesen Beitrag antworten »
RE: Eulersche Phi-Funktion Hier die Idee für eine gemeinsame Primpotenz: Sei $\begin{eqnarray} m=p^x , n=p^y \end{eqnarray}$ mit $\begin{eqnarray} x\le y \end{eqnarray}$ . $\begin{eqnarray} \Rightarrow \phi(m)=(p-1)p^{x-1} , \phi(n)=(p-1)p^{y-1} \Rightarrow \phi(m)\|\phi(n) \end{eqnarray}$ Hoffe, dass es nun einfach geht...
13.09.2004, 01:02	Tobias	Auf diesen Beitrag antworten »
Dank Soaps Hinweis hab ich mir jetzt folgenden Beweis(?) ausgedacht: $\begin{eqnarray} m \| n \Rightarrow n = t\cdot m \end{eqnarray}$ Sind t und m relativ prim, so ist der Fall unter Ausnutzung der Multiplikativität trivial: $\begin{eqnarray} \varphi(n) = \varphi(t\cdot m) = \varphi(t) \cdot \varphi(m) \Rightarrow \varphi(m) \| \varphi(n) \end{eqnarray}$ Sind t und m nicht relativ prim, hab ich ein universelleres Vorgehen. Ich betrachte die Primfaktorzerlegung von m: $\begin{eqnarray} m = \prod_{k=1}^{r}p_k^{\lambda_k} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \quad \varphi(m) = \prod_{k=1}^{r} \left( p_k^{\lambda_k - 1}(p_k - 1) \right) \end{eqnarray}$ Durch m\|n ist zugesichert, dass jede Primzahl in n mindeststens in derselben Potenz vorkommt wie in m: $\begin{eqnarray} \varphi(n) = \varphi(\frac{n}{\prod_{k=1}^{r}p_k^{\lambda_k + \delta_k}}\cdot \prod_{k=1}^{r}p_k^{\lambda_k + \delta_k}) = \varphi(..) \cdot \prod_{k=1}^{r} \left( p_k^{\lambda_k + \delta_k - 1}(p_k - 1) \right) \end{eqnarray}$ Daraus folgt $\begin{eqnarray} \varphi(m) \| \varphi(n) \end{eqnarray}$
13.09.2004, 04:38	Soap	Auf diesen Beitrag antworten »
sieht gut aus... :]
14.09.2004, 09:29	Pürierstab	Auf diesen Beitrag antworten »
Den Weg kannst du natürlich auch gehen, Tobias. Wenn du aber die Formel für die Phi-Funktion $\begin{eqnarray} \varphi(n) = n \prod_{p\| n} (1-\frac{1}{p}) \end{eqnarray}$ kennst (das Produkt erstreckt sich über alle Primteiler p von n), ist dein "Sätzchen" sehr leicht zu zeigen. Und letztere Formel rechnet man sich leicht anhand der Primfaktorzerlegung von n aus. Ich stelle mir vor, dass das der elegantere und durchsichtigere Beweis würde, was aber selbstverständlich Geschmackssache ist. Grüsslis, Pürierstab
14.09.2004, 11:46	Tobias	Auf diesen Beitrag antworten »
Ja, stimmt. Zwar ist der erste Beweis eigentlich auch schön, aber durch die überladene Darstellung ist dieser hier vorzuziehen: $\begin{eqnarray} m\|n \quad \Rightarrow \quad n = \lambda \cdot m \end{eqnarray}$ $\begin{eqnarray} \varphi(m) = m\prod_{p\|m}\left(1 - \frac{1}{p} \right) \end{eqnarray}$ $\begin{eqnarray} \varphi(n) = n\prod_{p\|n}\left(1 - \frac{1}{p}\right) = m \prod_{p\|m}\left(1 - \frac{1}{p}\right) \cdot \lambda\prod_{p\|n \; \wedge \; p \not\| m}\left(1 - \frac{1}{p}\right) \end{eqnarray}$
Anzeige

14.09.2004, 20:02	Peter Silie	Auf diesen Beitrag antworten »
Hallo Thomas, ich weiß zwar nicht, was du mit der "überladenen Darstellung" meinst, aber dein letztgenannter Beweis ist jedenfalls richtig. Ich vermisse nur noch die Aussage, dass $\begin{eqnarray} \lambda\prod_{p\mid n \; \wedge \; p \nmid m}\left(1 - \frac{1}{p}\right) \end{eqnarray}$ eine ganze Zahl ist. (Das ist leicht zu sehen). PS: Beachte auch die Verwendung von \mid und \nmid in der Formel, die hier besser als \| und \not\| aussieht.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »