Eulersche Phi-Funktion und gekürzte Brüche

16.05.2013, 14:21	Hexenjaeger	Auf diesen Beitrag antworten »
Eulersche Phi-Funktion und gekürzte Brüche Hey, folgende Aufgabe macht mich jetzt schon seit Tagen verrückt. Vielleicht könnt ihr mir helfen. Die Eulersche $\begin{eqnarray} \phi \end{eqnarray}$ -Funktion ist definiert durch $\begin{eqnarray} \phi(n) = \| \{k \in \mathbb{N} : k\leq n \mbox{ und k ist teilerfremd zu n}\}\| \end{eqnarray}$ . (a) $\begin{eqnarray} n\in \mathbb{N} \end{eqnarray}$ , $\begin{eqnarray} d \end{eqnarray}$ ein Teiler von $\begin{eqnarray} n \end{eqnarray}$ . Die Brüche $\begin{eqnarray} \frac{k}{n} \end{eqnarray}$ mit $\begin{eqnarray} 1 \leq k \leq n \end{eqnarray}$ werden so weit wie möglich gekürzt. Wie viele der gekürzten Brüche haben den Nenner $\begin{eqnarray} d \end{eqnarray}$ ? (b) Man folgere aus (a) $\begin{eqnarray} \sum_{d\|n} \phi(d)=n \end{eqnarray}$ . Für (b), hätte ich einen anderen Beweis, der aber halt nicht aus (a) folgt... Hat jemand einen Tipp für mich? Wenn $\begin{eqnarray} d\|n \end{eqnarray}$ gilt, dann auch $\begin{eqnarray} \frac{k}{j\cdot d} \end{eqnarray}$ ... hilft mir das weiter?
16.05.2013, 17:05	Tesserakt	Auf diesen Beitrag antworten »
Zur ersten Teilaufgabe: Aus $\begin{eqnarray} d \ \| \ n \end{eqnarray}$ folgt unmittelbar, dass ein natürliches $\begin{eqnarray} j \in \mathbb N \end{eqnarray}$ existiert mit $\begin{eqnarray} n = j \cdot d \end{eqnarray}$ . Ist ein Nenner der Form $\begin{eqnarray} \frac{z}{d} \end{eqnarray}$ vollständig gekürzt, so ist $\begin{eqnarray} z \end{eqnarray}$ teilerfremd zu $\begin{eqnarray} d \end{eqnarray}$ .
16.05.2013, 21:28	Hexenjaeger	Auf diesen Beitrag antworten »
Ok, ich glaub ich habs... Weil alle Brüche von $\begin{eqnarray} \frac{1}{n} \end{eqnarray}$ bis $\begin{eqnarray} \frac{n}{n} \end{eqnarray}$ betrachtet werden, kommen auch sicherlich alle Brüche der Form $\begin{eqnarray} \frac{i\cdot j}{j\cdot d} = \frac{i}{d} \end{eqnarray}$ vor, wobei i von 1 bis d läuft. Von denen sind genau diese nicht mehr kürzbar deren i teilerfremd zu d ist. Also ist die gesuchte Anzahl bei (a) $\begin{eqnarray} \phi(d) \end{eqnarray}$ . Richtig soweit? Über die (b) muss ich jetzt nochmal kurz nachdenken...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »