Dowód multiplikatywności funkcji Eulera
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
Dowód multiplikatywności funkcji Eulera
Witam,czy mógłby pokazać mi jak przeprowadzić dowód multiplikatywności funkcji Eulera?
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Dowód multiplikatywności funkcji Eulera
Funkcja eulera nie jest multiplikatywna - rozumiem, że chodzi Ci o multiplikatywność na elementach względnie pierwszych?
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
Re: Dowód multiplikatywności funkcji Eulera
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Funkcja_multiplikatywna
W przykładach jest wypisana
\(\displaystyle{ \phi(20)=\phi(5)\cdot \phi(4)=4\cdot 2=8}\)
-- 26 lip 2018, o 10:54 --
Tak,dokładnie.Możesz jeszcze pokazać tą różnice ?-- 26 lip 2018, o 10:55 --Ogólnie:
\(\displaystyle{ \phi(a\cdot b)=\phi(a)\cdot \phi(b)}\) jeśli \(\displaystyle{ NWD(a,b)=1}\)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Dowód multiplikatywności funkcji Eulera
Dla względnie pierwszych argumentów już tak, na bank o to chodzi.
Myślę, że odpowiedni jest tutaj dowód indukcyjny, tylko trochę niestandardowy (pomińmy jakieś jedynki, jako czynniki, bo żal coś takiego pisać): jeśli chodzi o bazę indukcji, pokazujemy, że dla liczb pierwszych \(\displaystyle{ p\neq q}\) i dowolnych \(\displaystyle{ a,b\in \NN^+}\) mamy
\(\displaystyle{ \varphi(p^{a}q^b)=\varphi(p^a)\varphi(q^b)}\), zaś w kroku indukcyjnym pokazujemy, że jeśli dla liczby \(\displaystyle{ x}\) o dokładnie \(\displaystyle{ k}\) dzielnikach pierwszych i dowolnych \(\displaystyle{ a,b}\) całkowitych dodatnich względnie pierwszych i takich, że \(\displaystyle{ ab=x}\) jest \(\displaystyle{ \varphi(ab)=\varphi(a)\varphi(b)}\), to analogiczny fakt zachodzi dla liczby \(\displaystyle{ x}\) o \(\displaystyle{ k+1}\) dzielnikach pierwszych i dowolnego rozkładu na względnie pierwsze czynniki.
Ale może da się zgrabniej.
Myślę, że odpowiedni jest tutaj dowód indukcyjny, tylko trochę niestandardowy (pomińmy jakieś jedynki, jako czynniki, bo żal coś takiego pisać): jeśli chodzi o bazę indukcji, pokazujemy, że dla liczb pierwszych \(\displaystyle{ p\neq q}\) i dowolnych \(\displaystyle{ a,b\in \NN^+}\) mamy
\(\displaystyle{ \varphi(p^{a}q^b)=\varphi(p^a)\varphi(q^b)}\), zaś w kroku indukcyjnym pokazujemy, że jeśli dla liczby \(\displaystyle{ x}\) o dokładnie \(\displaystyle{ k}\) dzielnikach pierwszych i dowolnych \(\displaystyle{ a,b}\) całkowitych dodatnich względnie pierwszych i takich, że \(\displaystyle{ ab=x}\) jest \(\displaystyle{ \varphi(ab)=\varphi(a)\varphi(b)}\), to analogiczny fakt zachodzi dla liczby \(\displaystyle{ x}\) o \(\displaystyle{ k+1}\) dzielnikach pierwszych i dowolnego rozkładu na względnie pierwsze czynniki.
Ale może da się zgrabniej.
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Re: Dowód multiplikatywności funkcji Eulera
No to zacznij od najprostszego przypadku ,gdy \(\displaystyle{ \phi(p \cdot q ) = \phi(p) \cdot \phi(q)}\) dla p i q pierwszych. zamiast zliczać te względnie pierwsze zliczas te, które względnie pierwsze nie są.
Jeśli \(\displaystyle{ NWD(a, pq) \neq 1}\) i \(\displaystyle{ a < pq}\) to
\(\displaystyle{ p|a \vee q|a}\) i nie jest prawdą, że \(\displaystyle{ p|a \wedge q|a}\). Umiesz wyliczyć ile jest takich a ?
Jeśli \(\displaystyle{ NWD(a, pq) \neq 1}\) i \(\displaystyle{ a < pq}\) to
\(\displaystyle{ p|a \vee q|a}\) i nie jest prawdą, że \(\displaystyle{ p|a \wedge q|a}\). Umiesz wyliczyć ile jest takich a ?
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Dowód multiplikatywności funkcji Eulera
Chcesz udowodnić, że \(\displaystyle{ \phi(pq) = (p-1)(q-1) = \phi(p) \phi(q)}\).
Zeby to zrobic musisz pokazać, że liczb wzglednie pierwszych z \(\displaystyle{ pq}\) i mniejszych od \(\displaystyle{ pq}\) jest dokladnie \(\displaystyle{ (p-1)(q-1)}\).
Ja proponuje zebys policzyl iloxc liczb mniejszych od \(\displaystyle{ pq}\) ,ktore nie sa wzglednie pierwsze z \(\displaystyle{ pq}\)
Zeby to zrobic musisz pokazać, że liczb wzglednie pierwszych z \(\displaystyle{ pq}\) i mniejszych od \(\displaystyle{ pq}\) jest dokladnie \(\displaystyle{ (p-1)(q-1)}\).
Ja proponuje zebys policzyl iloxc liczb mniejszych od \(\displaystyle{ pq}\) ,ktore nie sa wzglednie pierwsze z \(\displaystyle{ pq}\)