forum.zadania.info

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.

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.