¿Cómo pasar del pequeño teorema de Fermat al teorema de Euler pensando en la demostración de Ivory?

Question

La demostración de Ivory del teorema de Fermat explota el hecho de que dado un primo $p$ todos los números de $1$ a $p-1$ son relativamente primos de $p$ (obvio ya que $p$ es primo). Ivory los multiplica por x y obtiene:

$(x)(2x)\cdots((p-1)x)\equiv(1)(2)\cdots(p-1)\pmod{p}$

lo que da el teorema ya que puedo cancelar todos los enteros y salir:

$x^{p-1}\equiv1\pmod{p}$ .

Para derivar el teorema de Euler debería cambiar a módulo $m$ no primos y tomar los enteros positivos relativamente primos a $m$ y repite el proceso. En este punto tengo $\phi(m)$ tales números. ¿Cómo demuestro que todos ellos son no congruentes entre sí (para formar un conjunto completo de residuos al módulo $\phi(m)$ ) para poder multiplicarlos por un $x$ relativamente primo a $m$ y repetir los mismos pasos para demostrar

$x^{\phi(m)}\equiv1\pmod{m}$ ?

Answer 1

Usted tiene $a \ne b$ $\mod m$ , $\gcd(a,m)=\gcd(b,m)=gcd(x,m)=1$ .

Supongamos que $ax = bx \mod m$ . Entonces puedes usar el Teorema Chino del Resto y el hecho de que $x$ es coprimo de $m$ para encontrar un inverso multiplicativo de $x \mod m$ y derivar una contradicción.

Para ir más allá de la pregunta real: esto demuestra que la multiplicación por $x$ permuta el $\phi(m)$ números coprimos a $m$ Así que $$\prod_{a\in\{c | 0<c<m \wedge \gcd(c,m)=1\}} ax = \prod_{a\in\{c | 0<c<m \wedge \gcd(c,m)=1\}} a \mod m$$