Hola
Esta es la prueba que yo conozco.
1. Se prueba que si (a,b) = 1 y x recorre el sistema reducido de restos módulo b, ax también recorre el sistema reducido de restos al hacer la reducción módulo b.
O sea , que si S=\( \{r_1, 1_2, \ldots r_{\phi(b)}\} \) es el sistema reducido de restos, \( \{ar_1, ar_2, \ldots, ar_{\phi(b)}\} \), al tomar módulo con b, es una reordenación de S.
2. tendremos \( ar_j\equiv r_{i_{j}} (\mathrm{mod}\, b) \) cuando j varía desde 1 hasta \( \phi(b) \). Multiplicamos todas las congruencias miembro a miembro y se divide por \( r_1r_2\cdots r_{\phi(b)} \).
Saludos.