Cześć !
Zadanie brzmi następująco:
Udowodnij, że jeśli \(\displaystyle{ d|n}\) , to \(\displaystyle{ \varphi(d)|\varphi(n)}\).
Znalazłem rozwiązanie w skrypcie, ale praktycznie w ogóle go nie rozumiem. Prosiłbym Was o pomoc i wyjaśnienie mi praktycznie całości : )
DOWÓD:
Niech \(\displaystyle{ d= {p_{1}}^{\alpha_{1}} \cdot \ldots \cdot {p_{k}}^{\alpha_{k}}}\) gdzie \(\displaystyle{ p_{1} \ldots p_{k}}\) to liczby pierwsze, parami różne. Wtedy \(\displaystyle{ n= {p_{1}}^{\beta_{1}} \cdot \ldots \cdot {p_{k}}^{\beta_{k}} \cdot m}\) , gdzie \(\displaystyle{ \beta_{i} > \alpha_{i}}\) oraz \(\displaystyle{ p_{i}}\) nie dzieli \(\displaystyle{ m}\) dla \(\displaystyle{ i=1, \ldots , k}\). Zatem \(\displaystyle{ \varphi(n)=\varphi({p_{1}}^{\beta_{1}} \cdot \ldots \cdot {p_{k}}^{\beta_{k}}) \cdot \varphi(m) = \varphi(d) \cdot {p_{1}}^{\beta_{1} - \alpha_{1}} \cdot \ldots \cdot {p_{k}}^{\beta_{k} - \alpha_{k}} \cdot \varphi(m)}\). CO KOŃCZY DOWÓD.
Proszę Was o pomoc : )
dowód odnośnie funkcji Eulera
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
dowód odnośnie funkcji Eulera
Dokładnie wszystkiego : ) . Skąd takie określenie \(\displaystyle{ n}\), skąd takie określenie \(\displaystyle{ d}\). Nie rozumiem czemu naglę tocjent od \(\displaystyle{ n}\) tyle się równa ile jest tam napisane. Proszę wytłumacz mi to w jak najprostszych słowach : ) Będę wdzięczny : ))
- Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
dowód odnośnie funkcji Eulera
Określenie \(\displaystyle{ d}\) to po prostu rozkład na czynniki pierwsze. Liczby \(\displaystyle{ p_{1}, \ p_{2}, \ p_{3}, \ \ldots , p_{k}}\) to różne liczby pierwsze dzielące \(\displaystyle{ d}\), zaś \(\displaystyle{ \alpha_{1}, \ \alpha_{2}, \ \alpha_{3}, \ \ldots, \ \alpha_{k}}\) to wykładniki z jakimi owe liczby pierwsze dzielą \(\displaystyle{ d}\). Skoro \(\displaystyle{ d \mid b}\), to \(\displaystyle{ b}\) pownno dzielić się przez wszystkie liczby pierwsze które dzielą \(\displaystyle{ b}\) i wykładnik z jakim jakakolwiek z tych liczby pierwszych dzieli \(\displaystyle{ b}\) powinien być większy równy od wykładnika z jakim ta liczba pierwsza dzieli \(\displaystyle{ d}\). Powinno być więc raczej \(\displaystyle{ \beta_{i} \ge \alpha_{1}}\). Oczywiście \(\displaystyle{ b}\) może dzielić się przez inne liczby pierwsze, niedzielące \(\displaystyle{ d}\), nadal pozostając przy tym wielokrotnością \(\displaystyle{ d}\). Iloczyn tych liczb pierwszych (z odpowiednimi wykładnikami) oznaczamy przez \(\displaystyle{ m}\). Na razie jasne, czy gubisz się?