Analogous results to Euler's theorem

Question

Fermat's little theorem and its generalization, Euler's theorem holds for pair of relatively prime integers. Are there any analogous results for not relatively prime integers ? Thanks in advance.

Answer 1

A small variant holds even without the coprime condition. It's true that $$ a^p \equiv a \pmod p$$ even if $p \mid a$, for instance. Working a bit harder, you can show that $$ a^{n - \varphi(n)} \equiv a^n \pmod n$$ as well, even if $\gcd(a,n) \neq 1$.

Answer 2

The following generalization of Euler-Fermat often proves handy.

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

Proof $\ $ Notice that if $\ p_i\mid a\ $ then $\:p_i^{e_{\:i}}\ |\ a^e\ $ by $\ e_i \le e.\: $ Else $\:a\:$ is coprime to $\: p_i\:$ so by Euler's phi theorem, $\!\bmod q = p_i^{e_{\:i}}\!:\, \ a^{\phi(q)}\equiv 1 \Rightarrow\ a^f\equiv 1\, $ by $\: \phi(q)\mid f.\ $ Since all $\ p_i^{e_{\:i}}\ |\ a^e\ (a^f - 1)\ $ so too does their lcm = product = $m$.

Examples $\ $ You can find many illuminating examples in prior questions, e.g. below

$24\mid a^3(a^2-1)$

$40\mid a^3(a^4-1)$

$88\mid a^5(a^{20}-1)$

$6p\mid a\,b^p - b\,a^p$