Cześć,
Jak udowodnić poniższą równość?
\(\displaystyle{ \forall_{n \in N} \sum_{d|n}^{} \varphi (d) = n}\)
Suma funkcji Eulera
-
Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: Suma funkcji Eulera
Wydaje mi się że można to też zrobić przy użyciu a dowód można znaleźć
Rozumiem to tak że problem pokazania \(\displaystyle{ \forall_{n \in N} \sum_{d|n}^{} \varphi (d) = n}\) jest sprowadzony do policzenia splotu \(\displaystyle{ \varphi}\) z \(\displaystyle{ \mathbf{1}}\) czyli \(\displaystyle{ \varphi*\mathbf{1}}\) a ponieważ \(\displaystyle{ \varphi =\mu * \text{id}}\) (co było pokazane wcześniej) to
\(\displaystyle{ \varphi *\mathbf{1}=\mu* \text{id}*\mathbf{1}}\)
korzystając z własności splotu można zapisać
\(\displaystyle{ \varphi *\mathbf{1}=\mu* \text{id}*\mathbf{1}=\mu *\mathbf{1}*\text{id}=\delta * \text{id}=\text{id}}\)
Co kończy dowód bo \(\displaystyle{ \text{id}=n}\).
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Dirichlet_convolutionKod: Zaznacz cały
http://cykenleung.blogspot.com/2012/08/arithmetic-functions-i-dirichlet.htmlRozumiem to tak że problem pokazania \(\displaystyle{ \forall_{n \in N} \sum_{d|n}^{} \varphi (d) = n}\) jest sprowadzony do policzenia splotu \(\displaystyle{ \varphi}\) z \(\displaystyle{ \mathbf{1}}\) czyli \(\displaystyle{ \varphi*\mathbf{1}}\) a ponieważ \(\displaystyle{ \varphi =\mu * \text{id}}\) (co było pokazane wcześniej) to
\(\displaystyle{ \varphi *\mathbf{1}=\mu* \text{id}*\mathbf{1}}\)
korzystając z własności splotu można zapisać
\(\displaystyle{ \varphi *\mathbf{1}=\mu* \text{id}*\mathbf{1}=\mu *\mathbf{1}*\text{id}=\delta * \text{id}=\text{id}}\)
Co kończy dowód bo \(\displaystyle{ \text{id}=n}\).
-
niunix98
- Użytkownik
- Posty: 96
- Rejestracja: 19 lis 2017, o 20:25
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 17 razy
Re: Suma funkcji Eulera
Znalazłem dowód bardziej elementarny we "Wstępie do teorii liczb" Wacława Sierpińskiego i przedstawię go tutaj dla ciekawych.
Oznaczamy przez \(\displaystyle{ \varphi (n, d)}\) liczbę liczb z ciągu \(\displaystyle{ (1,2,....n)}\), które mają z liczbą n największy wspólny dzielnik równy d. Jako przykład podam \(\displaystyle{ \varphi (18,3) = 2}\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Teraz zauważamy, że jeżeli dla pewnego \(\displaystyle{ a \in \left\{ 1,2,...,n \right\}}\), \(\displaystyle{ NWD(a, n) = d}\) to jest to równoważne z \(\displaystyle{ a = kd}\) dla pewnego \(\displaystyle{ k \le \frac{n}{d}}\) i \(\displaystyle{ NWD(k, \frac{n}{d} ) = 1}\).
Tak więc \(\displaystyle{ \varphi (n, d) = \varphi ( \frac{n}{d} )}\).
Teraz wypisujemy rosnąco dzielniki liczby \(\displaystyle{ n}\): \(\displaystyle{ d_{1} < ... < d_{m}}\). Następnie dzielimy liczby \(\displaystyle{ (1,2,...,n)}\) na m grup w zależności od ich największej wspólnej wielokrotności. To znaczy, w \(\displaystyle{ i}\)-tej klasie będą wszystkie te liczby, których największym wspólnym dzielnikiem z n jest \(\displaystyle{ d_{i}}\).
Wszystkich liczb w ciągu \(\displaystyle{ (1,...,n)}\) jest \(\displaystyle{ n}\), skąd \(\displaystyle{ \sum_{i=1}^{n} \varphi (n, d_{i} ) = n}\), skąd \(\displaystyle{ \sum_{i=1}^{n} \varphi ( \frac{n}{ d_{i} } ) = n}\) i wreszcie \(\displaystyle{ \sum_{i=1}^{n} \varphi ( d_{i} ) = n}\), gdyż gdy \(\displaystyle{ d_{i}}\) przebiega dzielniki \(\displaystyle{ n}\) w porządku rosnącym, to \(\displaystyle{ \frac{n}{ d_{i} }}\) przebiega je w porządku malejącym. CNU
Oznaczamy przez \(\displaystyle{ \varphi (n, d)}\) liczbę liczb z ciągu \(\displaystyle{ (1,2,....n)}\), które mają z liczbą n największy wspólny dzielnik równy d. Jako przykład podam \(\displaystyle{ \varphi (18,3) = 2}\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Teraz zauważamy, że jeżeli dla pewnego \(\displaystyle{ a \in \left\{ 1,2,...,n \right\}}\), \(\displaystyle{ NWD(a, n) = d}\) to jest to równoważne z \(\displaystyle{ a = kd}\) dla pewnego \(\displaystyle{ k \le \frac{n}{d}}\) i \(\displaystyle{ NWD(k, \frac{n}{d} ) = 1}\).
Tak więc \(\displaystyle{ \varphi (n, d) = \varphi ( \frac{n}{d} )}\).
Teraz wypisujemy rosnąco dzielniki liczby \(\displaystyle{ n}\): \(\displaystyle{ d_{1} < ... < d_{m}}\). Następnie dzielimy liczby \(\displaystyle{ (1,2,...,n)}\) na m grup w zależności od ich największej wspólnej wielokrotności. To znaczy, w \(\displaystyle{ i}\)-tej klasie będą wszystkie te liczby, których największym wspólnym dzielnikiem z n jest \(\displaystyle{ d_{i}}\).
Wszystkich liczb w ciągu \(\displaystyle{ (1,...,n)}\) jest \(\displaystyle{ n}\), skąd \(\displaystyle{ \sum_{i=1}^{n} \varphi (n, d_{i} ) = n}\), skąd \(\displaystyle{ \sum_{i=1}^{n} \varphi ( \frac{n}{ d_{i} } ) = n}\) i wreszcie \(\displaystyle{ \sum_{i=1}^{n} \varphi ( d_{i} ) = n}\), gdyż gdy \(\displaystyle{ d_{i}}\) przebiega dzielniki \(\displaystyle{ n}\) w porządku rosnącym, to \(\displaystyle{ \frac{n}{ d_{i} }}\) przebiega je w porządku malejącym. CNU