Teorema totient generalizado de Euler

Question

Todos sabemos que si$a$ y$n$ son coprime, entonces

$a^{\phi(n)} \equiv 1\quad(\text{mod}\ n)$

¿Cómo puedo generalizar esto para el caso donde$a$ y$n$ no son coprime? ¿Es cierto lo siguiente?

$a^{k+\phi(n)} \equiv a^k\quad(\text{mod}\ n)$ para suficientemente grande$k$?

Answer 1

Poner $\rm\: b= 1\:$ en los siguientes

TEOREMA $\ $ Supongamos que $\rm\ n\in \mathbb N\ $ tiene la factorización en primos $\rm\:n = p_1^{e_{\:1}}\cdots\:p_k^{e_k}\ $ y supongo que para todos los $\rm\:i:$ $\rm\ e_i\le e\ $ y $\rm\ \phi(p_i^{e_{\:i}})\ |\ f\:.\ $ $\rm\ n\ |\ (ab)^e\ (a^f-b^f\:)\ $ todos los $\rm\: a,b\in \mathbb Z\:.$

Prueba de $\ $ Aviso que si $\rm\ p_i\ |\ ab\ $ $\rm\:p_i^{e_{\:i}}\ |\ (ab)^e\ $ $\rm\ e_i \le e\:.\: $ lo Contrario $\rm\:a\:$ $\rm\:b\:$ son coprime a$\rm\: p_i\:$, con lo que por el phi de Euler teorema, $\rm\ mod\ q = p_i^{e_{\:i}}:\: \ a^{\phi(q)}\equiv 1\equiv b^{\phi(q)}\: \Rightarrow\ a^f\equiv 1\equiv b^f\: $ desde $\rm\: \phi(q)\ |\ f\:.\ $, con Lo que desde todos los $\rm\ p_i^{e_{\:i}}\ |\ (ab)^e\ (a^f - b^f\:)\ $ también lo hace su lcm = producto = $\rm\: n\:.\:$ $\quad$

COMENTARIO $\ $ se puede obtener menores valores de $\rm\:f\:$ reemplazando $\rm\:\phi(p^k)\:$ $\rm\:\lambda(p^k)\:,\:$ el (universal) exponente del grupo de $\rm\:\mathbb Z/{p^k}^*,\:$.k.una. el Carmichael función. $\:$ Ver mi post aquí para obtener más.