Funkcja Eulera

[Iza8723]

Udowodnij, że jeśli \(\displaystyle{ NWD(n,m)=1}\), to \(\displaystyle{ \phi (n \cdot m)= \phi(n) \cdot \phi(m)}\).

[mol_ksiazkowy]

gdyz \(\displaystyle{ \phi(n)= n \prod_{p |n} (1- \frac{1}{p})}\)

[Dasio11]

molu, podejrzewam że zadanie jest dopiero przyczynkiem do udowodnienia podanego przez Ciebie wzoru, więc skorzystanie z niego byłoby jak zjadanie własnego ogona.

Dlatego proponuję tak: dla liczby naturalnej \(\displaystyle{ k}\) niech \(\displaystyle{ \ZZ_k = \{ 0, 1, \ldots, k-1 \}}\) i \(\displaystyle{ \ZZ^*_k = \{ x \in \ZZ_k : \operatorname{NWD}(x, k) = 1 \}}\) - tak że wtedy \(\displaystyle{ \phi(k) = |\ZZ^*_k|}\). Na mocy chińskiego twierdzenia o resztach funkcja \(\displaystyle{ r : \ZZ_{n \cdot m} \to \ZZ_n \times \ZZ_m}\) dana wzorem \(\displaystyle{ r(x) = (x \bmod{n}, x \bmod{m})}\) jest bijekcją. Ponadto dla \(\displaystyle{ r(x) = (y, z)}\) prawdziwe są równoważności

\(\displaystyle{ \operatorname{NWD}(x, n \cdot m) = 1 \iff \operatorname{NWD}(x, n) = 1 \wedge \operatorname{NWD}(x, m) = 1 \iff \operatorname{NWD}(y, n) = 1 \wedge \operatorname{NWD}(z, m) = 1}\)

zatem \(\displaystyle{ r}\) daje nam bijekcję \(\displaystyle{ : \ZZ^*_{n \cdot m} \to \ZZ^*_n \times \ZZ^*_m}\). Istnienie takiej bijekcji oznacza że \(\displaystyle{ |\ZZ^*_{n \cdot m}| = |\ZZ^*_n| \cdot |\ZZ^*_m|}\), czyli dokładnie \(\displaystyle{ \phi(n \cdot m) = \phi(n) \cdot \phi(m)}\).

[Janusz Tracz]

Ustalmy \(\displaystyle{ n,m\in \NN}\) względnie pierwsze i rozważmy zbir \(\displaystyle{ \left\{ 1,2,3,...,nm\right\} }\) w którym jest oczywiście \(\displaystyle{ \phi(mn)}\) liczb względnie pierwszych z \(\displaystyle{ mn}\). Zapisany nasz zbiór inaczej w postaci tabelki:

\(\displaystyle{ {\begin{bmatrix}1&2&\dots&k &\dots &m\\m+1&m+2&\dots&m+k&\dots &2m\\2m+1&2m+2&\dots&2m+k&\dots &3m\\\vdots&\vdots &\ddots&\vdots &\vdots \\(n-1)m+1&(n-1)m+2&\dots&(n-1)m+k&\dots &nm\end{bmatrix}}}\)

Zauważmy, że \(\displaystyle{ \phi(m)}\) to liczba liczy względnie pierzystych z \(\displaystyle{ m}\). Powiedzmy, że \(\displaystyle{ k}\) jest taką liczbą względnie pierwszą z \(\displaystyle{ m}\). Można udowodnić, że w kolumnie \(\displaystyle{ k}\)-tej znajdzie się \(\displaystyle{ \phi(n)}\) liczb względnie pierwszych z \(\displaystyle{ n}\).

Ale wcześniej zauważmy za zachodzi pewna równość: \(\displaystyle{ \NWD\left( a,b\right)=\NWD\left( a\text{ mod }b,b\right) }\).

Teraz ustalmy dwa elementy z \(\displaystyle{ k}\)-tej kolumny są one postaci \(\displaystyle{ \ell m+k}\) oraz \(\displaystyle{ \ell' m+k}\) i zauważmy, że wszystkie poniższe zapisy są równoważne:

\(\displaystyle{ \ell m+k \equiv \ell' m+k \mod n }\)

\(\displaystyle{ \ell m\equiv \ell' m \mod n }\)

\(\displaystyle{ \left( \ell -\ell' \right) m \equiv 0 \mod n }\)

\(\displaystyle{ \ell -\ell' \equiv 0 \mod n }\)

\(\displaystyle{ \ell \equiv \ell' \mod n }\)

przy czym po drodze korzysta się z faktu, że \(\displaystyle{ \NWD(n,m)=1}\). Kluczowe jest spostrzeżenie, że \(\displaystyle{ \ell,\ell'\in \left\{ 0,1,2,...,n-1\right\} }\) zatem są musi zajęć \(\displaystyle{ \ell=\ell'}\) a zatem gdyby rozważyć wszystkie reszty z dzielenia elementów \(\displaystyle{ k}\)-tej kolumny to utworzą one zbiór \(\displaystyle{ \left\{ 0,1,2,...,n-1\right\}}\) i każdy z nich wystąpi dokładnie raz (istnieje bijekcja pomiędzy elementami \(\displaystyle{ k}\)-tej kolumny na zbiór \(\displaystyle{ \left\{ 0,1,2,...,n-1\right\}}\)). A ponieważ branie modulo nie zmieniało \(\displaystyle{ \NWD}\) to w rozważanej kolumnie znajdzie się \(\displaystyle{ \phi(n)}\) liczb względnie pierwszych z \(\displaystyle{ n}\). Zatem mamy \(\displaystyle{ \phi(m)}\) takich kolumn w których liczby są względnie pierwsze z \(\displaystyle{ m}\) a w tych kolumnach jest \(\displaystyle{ \phi(n)}\) liczb względnie pierwszych z \(\displaystyle{ n}\). Czyli wszystkich liczb względnie pierwszych z \(\displaystyle{ mn}\) jest \(\displaystyle{ \phi(m) \cdot \phi(n)}\).

[Iza8723]

A jak udowodnić w takim razie, że jeśli \(\displaystyle{ NWD(a,b)=1}\) to \(\displaystyle{ NWD(a \mod b,b)=1}\) ?

[matmatmm]

Wynika to ze wspomnianego już ogólniejszego wzoru \(\displaystyle{ NWD(a,b)=NWD(a\phantom{0}\mathrm{mod}\phantom{0}b, b)}\).

Oznaczmy \(\displaystyle{ d=NWD(a,b),D=NWD(a \phantom{0}\mathrm{mod}\phantom{0} b, b)}\) oraz \(\displaystyle{ r=a \phantom{0}\mathrm{mod}\phantom{0}b}\).

Dla pewnej liczby całkowitej \(\displaystyle{ k\in\ZZ}\) mamy \(\displaystyle{ a=kb+r}\).

Wtedy \(\displaystyle{ d|a,d|b}\), więc \(\displaystyle{ d|r}\). Zatem \(\displaystyle{ d\le D}\).

Z drugiej strony \(\displaystyle{ D|r,D|b}\), więc \(\displaystyle{ D|a}\). Zatem \(\displaystyle{ D\le d}\).

[Iza8723]

Dostałam wskazówkę, żeby udowodnić to z tego wzoru
\(\displaystyle{ n= \prod_{i=1}^{t}p _{i} ^{e _{i} } }\) gdzie \(\displaystyle{ p _{i} }\) jest liczbą pierwszą, \(\displaystyle{ e _{i} }\) jest liczbą naturalną oraz \(\displaystyle{ p_{i} \neq p _{j} }\) dla \(\displaystyle{ i \neq j}\)
I dostajemy wzór \(\displaystyle{ \phi(n)= \prod_{i=1}^{t}(p _{i} ^{e _{i}}-p _{i} ^{e _{i}-1})}\)

Wie ktoś jak z tego wzoru to rozpisać?

[Premislav]

Moim zdaniem przy takim podejściu kluczowe jest właśnie udowodnienie tego wzoru na \(\displaystyle{ \phi(n)}\), ale jeśli możesz z niego skorzystać, to banał (choć i dowód nie jest trudny, z zasady włączeń i wyłączeń można to zrobić, a może da się i łatwiej).
Niech \(\displaystyle{ m,n>1, \NWD(m,n)=1}\) i niechaj \(\displaystyle{ I=\left\{p_{i}\in \PP: p_{i}|m\right\}, \ J=\left\{p_{j}\in \PP: p_{j}|n\right\}}\) i niech \(\displaystyle{ v_{p_{i}}(mn)=c_{i}}\) (tj. \(\displaystyle{ c_{i}}\) to wykładnik, z którym liczna pierwsza \(\displaystyle{ p_{i}}\) wchodzi do rozkładu liczby \(\displaystyle{ mn}\) na czynniki pierwsze).
Wtedy oczywiście \(\displaystyle{ I\cap J=\varnothing}\), a więc gdy \(\displaystyle{ p_{i}^{c_{i}}|mn}\), to \(\displaystyle{ p_{i}^{c_{i}}|m \vee p_{i}^{c_{i}}|n}\) oraz, w myśl przytoczonego wzoru,
\(\displaystyle{ \phi(mn)=\prod_{p_{i}|mn}^{}\left(p_{i}^{c_{i}}-p_{i}^{c_{i}-1}\right)=\prod_{p_{i}|mn\\p_{i}\in I}\left(p_{i}^{c_{i}}-p_{i}^{c_{i}-1}\right)\prod_{p_{i}|mn\\p_{i}\in J}^{}\left(p_{i}^{c_{i}}-p_{i}^{c_{i}-1}\right)=\phi(m)\phi(n)}\)