# Generalized Euler's totient theorem

We all know that if $a$ and $n$ are coprime, then

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

How can I generalize this to the case where $a$ and $n$ are not coprime? Is the following true?

$a^{k+\phi(n)} \equiv a^k\quad(\text{mod}\ n)$ for sufficiently large $k$?

-

Put $\rm\: b= 1\:$ in the following

THEOREM $\$ Suppose that $\rm\ n\in \mathbb N\$ has the prime factorization $\rm\:n = p_1^{e_{\:1}}\cdots\:p_k^{e_k}\$ and suppose that for all $\rm\:i:$ $\rm\ e_i\le e\$ and $\rm\ \phi(p_i^{e_{\:i}})\ |\ f\:.\$ Then $\rm\ n\ |\ (ab)^e\ (a^f-b^f\:)\$ for all $\rm\: a,b\in \mathbb Z\:.$

Proof $\$ Notice that if $\rm\ p_i\ |\ ab\$ then $\rm\:p_i^{e_{\:i}}\ |\ (ab)^e\$ by $\rm\ e_i \le e\:.\:$ Otherwise $\rm\:a\:$ and $\rm\:b\:$ are coprime to $\rm\: p_i\:$ thus by Euler's phi theorem, $\rm\ mod\ q = p_i^{e_{\:i}}:\: \ a^{\phi(q)}\equiv 1\equiv b^{\phi(q)}\: \Rightarrow\ a^f\equiv 1\equiv b^f\:$ since $\rm\: \phi(q)\ |\ f\:.\$ Thus since all $\rm\ p_i^{e_{\:i}}\ |\ (ab)^e\ (a^f - b^f\:)\$ so too does their lcm = product = $\rm\: n\:.\:$ $\quad$

REMARK $\$ One can obtain smaller values of $\rm\:f\:$ by replacing $\rm\:\phi(p^k)\:$ by $\rm\:\lambda(p^k)\:,\:$ the (universal) exponent of the group $\rm\:\mathbb Z/{p^k}^*,\:$ a.k.a. the Carmichael function. $\:$ See my post here for more.

-