Proof of : $x^{n}\equiv x^{\varphi(m)+[n \bmod \varphi(m)]} \mod m$

Question

There is a lesser known generalization of Euler's Theorem. Here 'x' and 'm' are NOT COPRIME and $\,n\ge \log_2 m.\,$ I stumbled upon this on this site : http://cp-algorithms.com/algebra/phi-function.html The "derivation" can be found towards the end of the above link; but i can't seem to wrap my head around it. It would be really great if it could be explained a bit better, probably with an example.

Answer 1

It is a special case of following generalization of the Euler-Fermat theorem. Indeed, let $\phi = \phi(m).\,$ By division we can write $\, n = q\,\phi + r,\,$ for $\,r = n\bmod \phi.\,$ Then the claim is that $$\bmod m\!:\,\ a^{\large q\,\phi+r}\equiv a^{\phi + r}\ \ \ {\rm i.e.}\ \ \ a^{\phi+r}(a^{(q-1)\phi}-1)\equiv 0,\ \ {\rm for\ all}\,\ a\in\Bbb Z\qquad$$

By the Theorem below this is true if $\,e := \phi + r\,$ is as least as large as the largest exponent in the prime factorization of $m$. The point is that we need to choose $\,e\,$ large enough so that the factor $\,a^e\,$ is divisible by all $\, p^{\large e_i}\,$ when $\,p\mid a,\,$ since then its cofactor $\,a^f-1\,$ is not divisible by $p.$

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\ge e_i\ $ 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$.

Remark $\ $ 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$

Answer 2

Let $m=ab$ with $\gcd(a,b)=\gcd(x,b)=1$. Then $$x^{\varphi (b)} \equiv 1\pmod b$$ If $a\mid x^k $, then $$x^k x^{\varphi (b)} \equiv x^k\pmod {m}$$ This means that for $n\geq k$ the sequence $n\to x^n\bmod m$ is periodic with period $\varphi(b)$.

Since $\varphi (m)=\varphi(a)\varphi(b) $, we have, in particular, $$x^k x^{\varphi (m)} \equiv x^k\pmod {m}$$ hence for $n\geq k$ the sequence $n\to x^n\bmod m$ is also periodic with period $\varphi(m)$.

Since $a\mid x^{\varphi (m)} $, we can choose $k=\varphi(m)$, thus obtaining: $$x^{2\varphi (m)} \equiv x^{\varphi (m)}\pmod {m}$$ which says that for $n\geq\varphi(m)$ the sequence $n\to x^n\bmod m$ is periodic with period $\varphi(m)$.

Consequently, for $n=q\varphi(m)+r$ with $r=n\bmod\varphi(m)$ and $q\geq 1$ we have \begin{align} x^n &=x^{q\varphi(m)}x^r\\ &\equiv x^{\varphi(m)}x^r\pmod m\\ &\equiv x^{\varphi(m)+r} \end{align} because $x^{q\varphi(m)}\equiv x^{\varphi(m)}\pmod m$, which proves the assertion.