Induktionsbeweis für Phi-Funktion und ggT

21.06.2018, 15:53	Mexicano13	Auf diesen Beitrag antworten »
Induktionsbeweis für Phi-Funktion und ggT Meine Frage: Man soll zeigen, dass wenn x,y Element von ? ist, und ggT(x,y) =g dann gilt phi(xy) = (phi(x)phi(y)g) / phi(g) Es wird vorgeschlagen, dafür die Induktion zu benutzen und dabei die Anzahl der gemeinsamen Primteiler von x und y zu beachten. Ich verstehe zwar, wie Induktion funktioniert, aber habe jedoch keinerlei Ansatz, wie ich dabei die Anzahl der gemeinsamen Primteiler einbinden soll. Habt ihr einen Ansatz für mich? Meine Ideen: Leider fehlt mir genau dieser Ansatz.
21.06.2018, 16:40	HAL 9000	Auf diesen Beitrag antworten »
Ich würde hier so vorgehen: Statt $\begin{eqnarray} \varphi \end{eqnarray}$ betrachte man die Funktionen $\begin{eqnarray} f(n):= \frac{\varphi(n)}{n} \end{eqnarray}$ sowie $\begin{eqnarray} h(p):=\frac{p-1}{p} \end{eqnarray}$ für Primzahlen $\begin{eqnarray} p \end{eqnarray}$ . Dann erhält man unmittelbar $\begin{eqnarray} f(n) = \prod_{p\mid n} h(p) \end{eqnarray}$ , und die Behauptung lautet mit $\begin{eqnarray} f \end{eqnarray}$ geschrieben $\begin{eqnarray} f(xy)f(g) = f(x)f(y)\qquad () \end{eqnarray}$ . Jetzt kann man für jede Primzahl $\begin{eqnarray} p \end{eqnarray}$ die vier möglichen Fälle hinsichtlich der Teilbarkeit von $\begin{eqnarray} x,y \end{eqnarray}$ durch diese Primzahl diskutieren... oder die angesprochene Vollständige Induktion durchführen, für () ist die sogar technisch leichter durchführbar.
21.06.2018, 16:57	mexicano13	Auf diesen Beitrag antworten »
Vielen Dank, ich werde mal sehen wie weit ich komme!
21.06.2018, 17:02	HAL 9000	Auf diesen Beitrag antworten »
Übrigens eine ziemliche Unverfrorenheit, diese Woche mit diesem Gastnamen hier aufzukreuzen.
21.06.2018, 17:12	mexicano13	Auf diesen Beitrag antworten »
Man muss sich so lange freuen, wie man kann Wünsche natürlich Deutschland alles Gute

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »