Dirichlet-Faltung

18.05.2014, 09:50

Vezzrin

Dirichlet-Faltung

Seien $\begin{eqnarray*} f,g \end{eqnarray*}$ zwei zahlentheoretische Funktionen und sei durch *(f,g) die Dirichlet-Faltung definiert duch $\begin{eqnarray*} f*g(n) = \sum_{d|n} f(d)\cdot g(n/d) \end{eqnarray*}$ .

Zeige: Wenn f,g multiplikativ -> f*g multiplikativ.

Beweis:

Sei also für alle m,n mit ggT(m,n)=1 erfüllt: $\begin{eqnarray*} f(m\cdot n) = f(m) \cdot f(n) \end{eqnarray*}$ . und $\begin{eqnarray*} g(m \cdot n) = g(m) \cdot g(n) \end{eqnarray*}$ .

Zu zeigen ist nun: $\begin{eqnarray*} f*g(n \cdot m) = (f*g)(n) \cdot (f*g)(m) \end{eqnarray*}$ , richtig?

Nun ist
$\begin{eqnarray*} f*g(n \cdot m) = \sum_{d| nm} f(d) \cdot g(n/d) \end{eqnarray*}$ .

Wie geht das denn nun?

18.05.2014, 11:07

HAL 9000

Auf diesen Beitrag antworten »

RE: Dirichlet-Faltung

Zitat:

Original von Vezzrin
Nun ist
$\begin{eqnarray*} f*g(n \cdot m) = \sum_{d| nm} f(d) \cdot g(n/d) \end{eqnarray*}$ .

Nein, wenn schon, dann

$\begin{eqnarray*} f*g(n \cdot m) = \sum_{d | nm} f(d) \cdot g\left( \frac{nm}{d}\right) \end{eqnarray*}$ .

Aufgrund der Teilerfremdheit von $\begin{eqnarray*} n,m \end{eqnarray*}$ lässt sich jeder Teiler $\begin{eqnarray*} d \end{eqnarray*}$ von $\begin{eqnarray*} nm \end{eqnarray*}$ in eineindeutiger Weise zerlegen in $\begin{eqnarray*} d= d_1\cdot d_2 \end{eqnarray*}$ mit $\begin{eqnarray*} d_1|n \end{eqnarray*}$ sowie $\begin{eqnarray*} d_2|m \end{eqnarray*}$ (sollte klar sein, etwa wenn man die Primfaktoren betrachtet). Es ist dann

$\begin{eqnarray*} f*g(n \cdot m) = \sum_{d_1 | n} \sum_{d_2 | m} f(d_1d_2) \cdot g\left( \frac{nm}{d_1d_2}\right) \end{eqnarray*}$ ,

von hier aus sollte es vorangehen.

Neue Frage »

Antworten »

Dirichlet-Faltung

Verwandte Themen