好男人喜欢的女人类型-好女人喜欢的男人类型

Question

While Fermat's little theorem states that $$a^p\equiv a\pmod p$$ for any prime number $p$, which may be considered a consequence of Euler's theorem $$a^{\phi(n)}\equiv 1\pmod n\tag{e}\label{e}$$ (for $n\nmid a$) since $\phi(p)=p-1$ for $p$ prime, I was wondering

whether there is any similar statement one can make about $a^n\bmod n$ when $n$ is not a prime number.

As a simplest example, take $n=p^2$ such that $\phi(n)=p(p-1)$, so $$a^{p^2}\equiv a^{\phi(p^2)+p}\stackrel{\eqref{e}}\equiv a^p\pmod{p^2}$$ or for $n=pq$ with $p\neq q$ (i.e. $\phi(n)=(p-1)(q-1)$) $$a^{pq}\equiv a^{\phi(pq)+p+q-1}\stackrel{\eqref{e}}\equiv a^{p+q-1}\pmod{pq}$$ (assuming $n\nmid a$), but these are rather "boring" identities...

I also wonder whether the exponential cycle $$a^{\lambda(n)+k}\equiv a^k\pmod n$$ plays a role here...

Answer 1

Since $\lambda(n)+v_\max(n)\leqslant n$, the $k\geqslant v_\max(n)$ in the exponential cycle $$a^{\lambda(n)+k}\equiv a^k\pmod n$$ can be chosen as $k=n-\lambda(n)\geqslant v_\max(n)$ to obtain $$a^n \equiv a^{n-\lambda(n)} \pmod n$$ As special cases, observe that for prime numbers (and Fermat pseudoprimes), where $\lambda(n)=\phi(n)=n-1$, this yields Fermat's little theorem; while the two examples from the question are also included.

Note how this yields $n\in K_{n-\lambda(n)}$, i.e. each (composite) $n$ is a Kn?del number