http://www.ftj.agh.edu.pl/~lenda/number_theory/A36.pdf
Witam,
Chodzi o 3ci slajd - dowód twierdzenia Eulera. Jak to możliwe, że on działa ? Całe rozumowanie rozumiem. Jest ok. Tylko ta końcówka.
Wszak po prawej stronie chcemy dostać jedynkę (żeby dostać tezę tw. Eulera). A nie dosatniemy jej, bo te iloczyny reszt nie są równe.
Jak ten dowód działa ?
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 1070
- Rejestracja: 07 maja 2010, 12:48
- Podziękowania: 2 razy
- Otrzymane podziękowania: 357 razy
Są. Każda reszta \(r_i\) daje pewną resztę \(r_i'\). Przy czym żadna reszta \(r_i'\) nie zostanie wygenerowana więcej niż raz. Wiemy, że wszystkich reszt względnie pierwszych z \(m\) jest \(\varphi(m)\), więc skoro otrzymaliśmy \(\varphi(m)\) różnych reszt \(r_i'\) względnie pierwszych z \(m\), to istotnie \(r_1r_2\ldots r_{\varphi(m)}=r_1'r_2'\ldots r_{\varphi(m)}'\). Iloczyn ten jest względnie pierwszy z \(m\), więc możemy obustronnie skrócić przez niego kongruencję, otrzymując tezę twierdzenia Eulera.
Nieco inny dowód, odwołujący się do elementów odwracalnych, można znaleźć tutaj.
Nieco inny dowód, odwołujący się do elementów odwracalnych, można znaleźć tutaj.
Korki z matmy, rozwiązywanie zadań
info na priv
info na priv