Primzerlegung+Dirichlet-Faltg. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:26 Mo 02.01.2012 | | Autor: | swetti |
| Aufgabe | | Beschreibe [mm] \mu \* [/mm] w(n) in Termini der Primzerlegung |
[mm] \mu [/mm] ist die Möbiusfunktion mit
[mm] \mu [/mm] (n) = 1 wenn n =1
= 0 wenn [mm] \exists [/mm] p Primzahl: [mm] v_{p}(n)>1
[/mm]
[mm] =(-1)^r [/mm] wenn n = [mm] p_{1}*...*p_{r} [/mm] , [mm] p_{i} \not= p_{j} [/mm] , r [mm] \in \IN
[/mm]
[mm] \* [/mm] ist die Dirichlet-Faltung:
f,g : [mm] \IN \to \IC
[/mm]
(f [mm] \* [/mm] g) (n) = [mm] \summe_{d | n } [/mm] f(d) * g [mm] (\bruch{n}{d}) [/mm] = [mm] \summe_{a*b = n } [/mm] f(a) * g(b)
w(n) ist die Anzahl der verschiedenen Primteiler von n, n > 1.
w(1) = 0
Ich soll diese Aufgabe bearbeiten. Da wir die Möbius-Funktion erst ganz neu eingeführt habe und damit noch nicht gearbeitet haben, bin ich ratlos, wie ich vorgehen soll. Soll ich das durch das Faltungsprodukt neu erzeugte Element in [mm] \IC [/mm] in Primfaktoren zerlegen? Ich verstehe das Problem dabei nicht...Ist das Faltungsprodukt so außergewöhnlich?
Es würde mir wirklich sehr helfen, wenn ich eine Hilfe zum Verständnis und zum Vorgehen dieser Aufgabe bekommen würde. Dafür bedanke ich mich jetzt schon.
Grüße, swetti
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:35 Mo 02.01.2012 | | Autor: | felixf |
Moin swetti!
> Beschreibe [mm]\mu \*[/mm] w(n) in Termini der Primzerlegung
> [mm]\mu[/mm] ist die Möbiusfunktion mit
> [mm]\mu[/mm] (n) = 1 wenn n =1
> = 0 wenn [mm]\exists[/mm] p Primzahl: [mm]v_{p}(n)>1[/mm]
> [mm]=(-1)^r[/mm] wenn n = [mm]p_{1}*...*p_{r}[/mm] , [mm]p_{i} \not= p_{j}[/mm]
> , r [mm]\in \IN[/mm]
>
> [mm]\*[/mm] ist die Dirichlet-Faltung:
> f,g : [mm]\IN \to \IC[/mm]
> (f [mm]\*[/mm] g) (n) = [mm]\summe_{d | n }[/mm] f(d) * g
> [mm](\bruch{n}{d})[/mm] = [mm]\summe_{a*b = n }[/mm] f(a) * g(b)
>
> w(n) ist die Anzahl der verschiedenen Primteiler von n, n >
> 1.
> w(1) = 0
>
> Ich soll diese Aufgabe bearbeiten. Da wir die
> Möbius-Funktion erst ganz neu eingeführt habe und damit
> noch nicht gearbeitet haben, bin ich ratlos, wie ich
> vorgehen soll. Soll ich das durch das Faltungsprodukt neu
> erzeugte Element in [mm]\IC[/mm] in Primfaktoren zerlegen? Ich
> verstehe das Problem dabei nicht...Ist das Faltungsprodukt
> so außergewöhnlich?
Du sollst $n = [mm] \prod_{i=1}^k p_i^{e_i}$ [/mm] mit paarweise verschiedenen Primzahlen [mm] $p_1, \dots, p_k$ [/mm] schreiben und dann [mm] $(\mu \ast [/mm] w)(n)$ als Ausdruck in [mm] $p_1, \dots, p_k, e_1, \dots, e_k, [/mm] k$ angeben.
Etwa ist [mm] $\phi(n) [/mm] = [mm] \prod_{i=1}^k p_i^{e_i - 1} (p_i [/mm] - 1)$ (mit [mm] $\phi$ [/mm] der Eulerschen [mm] $\phi$-Funktion), [/mm] und $w(n) = [mm] \sum_{i=1}^k [/mm] 1 = k$.
> Es würde mir wirklich sehr helfen, wenn ich eine Hilfe zum
> Verständnis und zum Vorgehen dieser Aufgabe bekommen
> würde. Dafür bedanke ich mich jetzt schon.
Zum Vorgehen: wenn $n = [mm] \prod_{i=1}^k p_i^{e_i}$ [/mm] ist, so kannst du [mm] $\sum_{d \mid n} [/mm] g(d)$ schreiben als [mm] $\sum_{f_1=0}^{e_1} \cdots \sum_{f_k=0}^{e_k} g(\prod_{i=1}^k p_i^{f_i})$.
[/mm]
Damit solltest du weiterkommen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:17 Do 05.01.2012 | | Autor: | swetti |
Hallo Felix,
danke für deine hilfreichen Tipps.
Ich habe mir die vorliegende Faltung an einigen Beispielen angeguckt und festgestellt, dass folgendes gilt:
1) [mm] (\mu \* [/mm] w) (n) = 1 [mm] \gdw [/mm] n Primzahl
2) [mm] (\mu \* [/mm] w) (n) = 0 [mm] \gdw [/mm] n nicht Primzahl
Dass 1) gilt, kann man leicht auch mit dem Faltungsprodukt begründen, welches ja so aussieht:
[mm] (\mu\*w)(n) [/mm] = [mm] \summe_{d|n} \mu(d) [/mm] * w(n/d) = [mm] \mu(1) [/mm] * w(n) + [mm] \mu(n) [/mm] * w(1) = 1*1+ (-1)*0 = 1
Bei 2) ist es natürlich um einiges komplizierter, da es sich hier um eine allgemeine Zahl n = [mm] \produkt_{i=1}^{n} p_{1} e^{i} [/mm] handelt.
Unser Übungsgruppenleiter sagte uns, dass wir die sich ergebende Funktion in diesen Fall mithilfe der Möbius-Inversion zeigen könnten/ sollten. Diese haben wir so definiert:
Ist F = 1 [mm] \* [/mm] f , so gilt f = F [mm] \* \mu.
[/mm]
Also F = [mm] \summe_{d|n} [/mm] f(n/d) und f = [mm] \summe_{d|n} [/mm] F(d) * [mm] \mu(n/d) [/mm] = [mm] \summe_{d|n} \mu(d) [/mm] * F(n/d) (wg Kommutativität)
Da [mm] (\mu\*w)(n) [/mm] = [mm] \summe_{d|n} \mu(d) [/mm] * w(n/d), würde dann ja gelten:
F(n/d) = w(n/d). Doch was würde mir das dann weiter bringen??
Kann man mithilfe dieser Herangehensweise die gesuchte Funktion finden?
Ich habe es auch mit felix' letzten Tipp versucht, indem ich das gegebene Faltungsprodukt zu vereinfachen versucht habe. Nach einigen Umrechnungsschritte kam ich jedoch nicht weiter, denn meine Möbiusfunktion ist ja multiplikativ, die w-Funktion (Anzahl der Primteiler) ist dagegen additiv. Dadurch wusste ich nicht, wie ich beide zusammenfassen könnte:
Sei n = [mm] \produkt_{i=1}^{n} p_{i} e^{i} [/mm] und d | n, wobei d = [mm] \produkt_{i=1}^{n} d_{i} [/mm] mit [mm] d_{i} [/mm] | [mm] p_{i} e^{i},p_{i} e^{i} [/mm] und [mm] d_{i} [/mm] sind je teilerfremd :
[mm] \summe_{\produkt_{i=1}^{n} d_{i}|\produkt_{i=1}^{n} p_{i} e^{i} } (\mu(d_{1})*...*\mu(d_{n})) +(w(p_{1} e^{1}/d_{1})+...+w(p_{n} e^{n}/d_{1}))= [/mm] ??
Hinweise, wie ich diese Aufgabe doch noch lösen könnte, sind mir sehr willkommen. Ich weiß echt nicht mehr, von welcher Seite ich mich dieser nähern sollte. Trotzdem würde ich sehr gerne verstehen, was hinter dieser Aufgabe steckt.
Ich bedanke mich herzlich für eure Mühen!!!
Grüße swetti
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:10 Sa 07.01.2012 | | Autor: | felixf |
Moin!
> danke für deine hilfreichen Tipps.
>
> Ich habe mir die vorliegende Faltung an einigen Beispielen
> angeguckt und festgestellt, dass folgendes gilt:
>
> 1) [mm](\mu \*[/mm] w) (n) = 1 [mm]\gdw[/mm] n Primzahl
> 2) [mm](\mu \*[/mm] w) (n) = 0 [mm]\gdw[/mm] n nicht Primzahl
>
> Dass 1) gilt, kann man leicht auch mit dem Faltungsprodukt
> begründen, welches ja so aussieht:
> [mm](\mu\*w)(n)[/mm] = [mm]\summe_{d|n} \mu(d)[/mm] * w(n/d) = [mm]\mu(1)[/mm] * w(n)
> + [mm]\mu(n)[/mm] * w(1) = 1*1+ (-1)*0 = 1
Damit hast du nur [mm] $\Leftarrow$ [/mm] gezeigt. Das reicht aber, wenn du bei 2) ebenfalls [mm] $\Leftarrow$ [/mm] zeigst.
> Bei 2) ist es natürlich um einiges komplizierter, da es
> sich hier um eine allgemeine Zahl n = [mm]\produkt_{i=1}^{n} p_{1} e^{i}[/mm]
> handelt.
> Unser Übungsgruppenleiter sagte uns, dass wir die sich
> ergebende Funktion in diesen Fall mithilfe der
> Möbius-Inversion zeigen könnten/ sollten. Diese haben wir
> so definiert:
>
> Ist F = 1 [mm]\*[/mm] f , so gilt f = F [mm]\* \mu.[/mm]
Du meinst aufgeschrieben.
Die Moebiusinversion kann man auch wie folgt aufschreiben: $1 [mm] \ast \mu [/mm] = [mm] \mu \ast [/mm] 1 = $ neutrales Element bzgl. der Faltung.
Damit gilt $1 [mm] \ast (\mu \ast [/mm] w) = (1 [mm] \ast \mu) \ast [/mm] w = w$.
> Also F =
> [mm]\summe_{d|n}[/mm] f(n/d) und f = [mm]\summe_{d|n}[/mm] F(d) * [mm]\mu(n/d)[/mm] =
> [mm]\summe_{d|n} \mu(d)[/mm] * F(n/d) (wg Kommutativität)
>
> Da [mm](\mu\*w)(n)[/mm] = [mm]\summe_{d|n} \mu(d)[/mm] * w(n/d),
es soll also $f = [mm] \mu \ast [/mm] w$ und $F = w$ sein?
> würde dann
> ja gelten:
> F(n/d) = w(n/d). Doch was würde mir das dann weiter
> bringen??
> Kann man mithilfe dieser Herangehensweise die gesuchte
> Funktion finden?
Das fragst du am besten deinen Uebungsleiter...
> Ich habe es auch mit felix' letzten Tipp versucht, indem
> ich das gegebene Faltungsprodukt zu vereinfachen versucht
> habe. Nach einigen Umrechnungsschritte kam ich jedoch nicht
> weiter, denn meine Möbiusfunktion ist ja multiplikativ,
> die w-Funktion (Anzahl der Primteiler) ist dagegen additiv.
> Dadurch wusste ich nicht, wie ich beide zusammenfassen
> könnte:
> Sei n = [mm]\produkt_{i=1}^{n} p_{i} e^{i}[/mm]
Du meinst [mm] $\prod_{i=1}^k p_i^{e_i}$? [/mm] Mit $k$ anstelle $n$ (das wird sonst doppelt gebraucht) und [mm] $e_i$ [/mm] im Exponenten und nicht hinten ein [mm] $e^i$?
[/mm]
> und d | n, wobei d
> = [mm]\produkt_{i=1}^{n} d_{i}[/mm] mit [mm]d_{i}[/mm] | [mm]p_{i} e^{i},p_{i} e^{i}[/mm]
> und [mm]d_{i}[/mm] sind je teilerfremd :
Sorry, aber das macht nicht viel Sinn. Warum sollen [mm] $p_i^{e_i}$ [/mm] und [mm] $d_i$ [/mm] teilerfremd sein (fuer jedes $i$)?
> [mm]\summe_{\produkt_{i=1}^{n} d_{i}|\produkt_{i=1}^{n} p_{i} e^{i} } (\mu(d_{1})*...*\mu(d_{n})) +(w(p_{1} e^{1}/d_{1})+...+w(p_{n} e^{n}/d_{1}))=[/mm]
> ??
Was tust du da???
> Hinweise, wie ich diese Aufgabe doch noch lösen könnte,
> sind mir sehr willkommen. Ich weiß echt nicht mehr, von
> welcher Seite ich mich dieser nähern sollte. Trotzdem
> würde ich sehr gerne verstehen, was hinter dieser Aufgabe
> steckt.
Gehe vor wie ich dir das aufgeschrieben hatte: [mm] $\sum_{d \mid n} [/mm] g(d) = [mm] \sum_{f_1=0}^{e_1} \cdots \sum_{f_k=0}^{e_k} g(\prod_{i=1}^k p_i^{f_i}) [/mm] $ mit $g(x) = [mm] \mu(x) [/mm] w(n/x)$.
LG Felix
|
|
|
|
