Dowód multiplikatywności funkcji Eulera

[xxDorianxx]

Witam,czy mógłby pokazać mi jak przeprowadzić dowód multiplikatywności funkcji Eulera?

[leg14]

Funkcja eulera nie jest multiplikatywna - rozumiem, że chodzi Ci o multiplikatywność na elementach względnie pierwszych?

[xxDorianxx]

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]

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.

[leg14]

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 ?

[xxDorianxx]

leg14, trochę nie rozumiem co mam wyliczać

[leg14]

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}\)