$a^{\phi (n) +1} \equiv a \pmod{\! n}; $ Carmichael generalization of Fermat & Euler theorems.

Solution 1:

As the proof below shows, the claim is true $\!\iff\! n$ is squarefree (i.e. a product of distinct primes). A simple counterexample is given by $\,n=4,\,a=2.\,$ Since $\,a^2 \equiv 0 \pmod{\! n}\,$ we can not have $\,a^e \equiv a \pmod{\! n}\,$ for any $\,e>1.\,$ In particular $\,a^{\phi(n) +1}=a^{2+1} \equiv 0\not\equiv a \pmod{\!n}$.

Below is a more general result (sometimes called Korselt's criterion for Carmichael numbers).

Theorem $ $ (Korselt's Carmichael Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ squarefree, \ and \ \ p\!-\!1\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid n\qquad$$

Proof $\ (\Leftarrow)\ $ By unique prime factorization (or Euclid's Lemma), a squarefree natural divides another iff all its prime factors do, so we need only show $\rm\:p\:|\:a^{\large e}\!-\!a\:$ for each prime $\rm\:p\:|\:n.\:$ It's clear if $\rm\,p \mid a.\,$ Else $\rm\!\bmod p\!:\ a \not\equiv 0\,$ $\rm\overset{\rm Fermat}\Longrightarrow\, \color{c00}{a^{\large\color{#0a0}{p-1}} \equiv 1}$ so $\rm\,\color{#c00}{a^{\large\color{#0a0}{e-1}}\equiv 1}\,$ by $\rm \,\color{#0a0}{p\!-\!1\mid e\!-\!1}\,$ and modular order reduction. Thus $\rm\,a^{\large e}-a\equiv a(\color{#c00}{a^{\large\color{#0a0}{e-1}}-1})\equiv a(\color{#c00}0)\equiv 0$.

$(\Rightarrow)\ \ $ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show

$$\rm (1)\ \ n\,\ is\ squarefree,\quad and\quad (2)\ \ p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$

$(1)\ \ $ If $\rm\,n\,$ isn't squarefree then $\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\: a^2\mid a\:\Rightarrow\!\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$

$(2)\ \ $ Let $\rm\ a\ $ be a generator ("primitive root") of the cyclic multiplicative group of $\rm\:\Bbb Z/p,\,$ i.e. $\rm\ a\ $ has order $\rm\:p\!-\!1.\:$ Now $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$ but $\rm\:p\nmid a,\:$ thus $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ the order of $\rm\ a\,\ (mod\ p).\quad$ QED

Corollary $\rm\,\ n\mid a^e b - a b^f\ $ if $\,\rm n\:$ is squarefree, and prime $\rm\:p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e\!-\!1,\,f\!-\!1$

Proof $\ $ By the Theorem $\rm\bmod n\!:\,\ a^e\equiv a,\, b^f\equiv b\,$ so $\rm\,a^e b - ab^f\equiv ab-ab\equiv 0$

Corollary' $\ n\mid f(a^{e_1},b^{e_2}) - f(a^{e_3},b^{e_4})\,$ if $\,n\,$ is squarefree, and prime $\,p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e_i\!-\!1\,$ and $\,f(x,y)\in\Bbb Z[x,y],\,$ i.e. $\,f\,$ is a polynomial in $\,x,y\,$ with integer coefficients.

Proof $\ $ By the Theorem $\bmod n\!:\,\ a^{e_i}\equiv a,\, b^{e_i}\equiv b\,$ so $f(a^{e_i},b^{e_i}) \equiv f(a,b)\,$ by the Polynomial Congruence Rule.

The equivalent definitions of Carmichael numbers are the special case $\,e = n\,$ below.

Theorem $\ $ The following are equivalent for integers $\,n,e>1$.
$(1)_{\phantom{|_{|_.}}}\ n\mid a^e\ -\ a\ \ $ for all $\,a\in\Bbb Z^{\phantom{|^|}}\!\!,\: $ and $\ (e\!-\!1,n)=1$
$(2)_{\phantom{|_{|_.}}}\ n\mid a^{e-1}\!-1\ $ for all $\,a\in\Bbb Z\,$ with $\, \color{#90f}{(a,n)=1}= (e\!-\!1,n)$
$(3)\ \ \ \:\! n\,$ is squarefree, $ $ prime $\,p\mid n\,\Rightarrow\, \color{#0a0}{p\!-\!1\mid e\!-\!1},\ p\nmid e\!-\!1$

Proof $\ \ $ See this answer