Eulersche Funktion mit ggT = 2 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Seien m, n [mm] \in \IN, [/mm] und sei ggT(m, n) = 2. Beweisen Sie, dass [mm] \phi(mn) [/mm] = 2 [mm] \phi(m) \phi(n). [/mm] |
Hallo,
grübel leider schon wieder mehrere Stunden hierüber.
Verfolge bisher 2 Ansätze:
1) Aus ggT(m, n) = 2 folgt einerseits, dass sowohl die Primfaktorzerlegung von m als auch die von n eine Zweierpotenz [mm] \ge [/mm] 1 enthält, wobei entweder die von m oder die von n genau 1 ist. Sei die Zerlegung von n diejenige, die genau [mm] 2^1 [/mm] enthält. Dann gilt [mm] \phi(\frac{mn}{2}) [/mm] = [mm] \phi(m) \phi(\frac{n}{2}). [/mm] Hier komme ich nicht weiter, weil ich zu keiner allgemeinen Aussage zum Verhältnis [mm] \frac{\phi(\frac{n}{2})}{\phi(n)} [/mm] bzw. [mm] \frac{\phi(\frac{mn}{2})}{\phi(mn)} [/mm] gelange ...
2) Andererseits habe ich einen Beweis für die Multiplikativität [mm] \phi(mn) [/mm] = [mm] \phi(m) \phi(n) [/mm] für ggT(m, n) = 1. Hier werden im Grunde drei Mengen [mm] U_{m}, U_{n} [/mm] und [mm] U_{mn} [/mm] mit [mm] U_{x} [/mm] = [mm] \{ a \in \IZ_{x} \vert ggT(a, x) = 1 \} [/mm] verwendet und dann zwei Funktionen [mm] U_{mn} \to U_m \times U_n [/mm] und [mm] U_m \times U_n \to U_{mn} [/mm] definiert und gezeigt, dass beide surjektiv sind, wobei verrwendet wird, dass es mit dem chinesischen Restsatz ein eindeutig bestimmtes [mm] x_0 \in \IZ_{mn} [/mm] so gibt, dass [mm] x_0 [/mm] mod m = a [mm] \in \IZ_{m} [/mm] und [mm] x_0 [/mm] mod n = b [mm] \in \IZ_{n}. [/mm] Auch hier stocke ich leider und würde mich über einen Tipp freuen...
Gruß und Danke,
Martin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:33 So 08.11.2020 | | Autor: | statler |
Guten Morgen!
> Seien m, n [mm]\in \IN,[/mm] und sei ggT(m, n) = 2. Beweisen Sie,
> dass [mm]\phi(mn)[/mm] = 2 [mm]\phi(m) \phi(n).[/mm]
> Hallo,
> grübel leider schon wieder mehrere Stunden hierüber.
>
> Verfolge bisher 2 Ansätze:
>
> 1) Aus ggT(m, n) = 2 folgt einerseits, dass sowohl die
> Primfaktorzerlegung von m als auch die von n eine
> Zweierpotenz [mm]\ge[/mm] 1 enthält, wobei entweder die von m oder
> die von n genau 1 ist. Sei die Zerlegung von n diejenige,
> die genau [mm]2^1[/mm] enthält. Dann gilt [mm]\phi(\frac{mn}{2})[/mm] =
> [mm]\phi(m) \phi(\frac{n}{2}).[/mm] Hier komme ich nicht weiter,
>
Unter diesen Voraussetzungen ist [mm] $\varphi(\frac{n}{2}) [/mm] = [mm] \varphi(n)$. [/mm] Am einfachsten ist es wohl, du schreibst dir die Primfaktorzerlegungen von m und n hin und benutzt dann die Produktdarstellung von [mm] $\varphi$:
[/mm]
$m = [mm] 2^{e_0}\cdot p_1^{e_1} \cdots p_r^{e_r}$ [/mm] und $n = [mm] 2^{1}\cdot q_1^{f_1} \cdots q_s^{f_s}$
[/mm]
Jetzt ist [mm] $\varphi(m) [/mm] = [mm] 2^{e_0 - 1}\cdot p_1^{e_1}(1-\frac{1}{p_1}) \cdots p_r^{e_r}(1-\frac{1}{p_r})$ [/mm] und [mm] $\varphi(n) [/mm] = [mm] 2^{0}\cdot q_1^{f_1}(1-\frac{1}{q_1}) \cdots q_s^{f_s}(1-\frac{1}{q_s})$
[/mm]
Was ist jetzt [mm] \varphi(mn)? \rightarrow [/mm] Das ist deine Aufgabe :)
So weit so gut und schönen Sonntag
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:10 So 08.11.2020 | | Autor: | sancho1980 |
Super danke. Dabei fällt mir auf: Auf diese Weise hätte man [mm] \phi(mn) [/mm] = [mm] \phi(m) \phi(n) [/mm] im Fall dass ggT(m, n) = 1 auch viel einfacher zeigen können als über diese Mengen [mm] U_m, U_n [/mm] und [mm] U_{mn} [/mm] ...
|
|
|
|
