Teorema de Euler con un producto de números primos

Question

¿Alguien podría decirme por qué es que si tienes un producto de números primos, digamos 15, entonces si usas el teorema de Euler ligeramente modificado, entonces la ecuación funciona para todos los números, no solo para los primos relativos a n=3*5?

$$x^{\phi(3*5)+1} \equiv x \mod (3*5)$$

¿Cómo podría demostrar esto? (La pregunta está relacionada con RSA si lo conoces)

Answer 1

Sea $m$ un producto de primes distinctos, y sea $p$ un divisor primo de $m$.

Si $p$ no divide a $x$, entonces tenemos $x^{p-1}\equiv 1\pmod{p}$, y por lo tanto $x^{\varphi(m)}\equiv 1\pmod{p}$, y por lo tanto $x^{\varphi(m)+1}\equiv x\pmod{p}$.

Si $p$ divide a $x$, entonces nuevamente $x^{\varphi(m)+1}\equiv x\pmod{p}$, ya que ambos lados son congruentes a $0$.

Así que $x^{\varphi(m)+1}\equiv x\pmod{p}$ para cada divisor primo de $m$. Dado que $m$ es el producto de primos distintos, se sigue que $x^{\varphi(m)+1}\equiv x\pmod{m}$.

Nota: La condición de que $m$ sea un producto de primos distintos es necesaria. Por ejemplo, $3^{\varphi(9)+1}\not\equiv 3\pmod{9}$.

Answer 2

Según el pequeño teorema de Fermat, $3|x(x^2-1);5|x(x^4-1)$ para todo entero $x$

$\displaystyle\implies x(x^{\text{lcm}(2,4)}-1)$ será divisible por lcm$(3,5)$

Ahora $\displaystyle4|\phi(15)\implies x(x^{\phi(15)}-1)$ será divisible por $ x(x^4-1)$ que ya es divisible por lcm$(3,5)$