Show that if $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ such that $\gcd(n,a) = 1$, then $a^{n} \equiv a \pmod{n}$ for all $a$.

In Burton's Elementary Number Theory, when introducing absolute pseudoprimes (also called Carmichael numbers), the author states that they are composite numbers $n$ such that $a^{n-1} \equiv 1 \pmod n$ for all integers $a$ with $\gcd(a,n) = 1$.

When showing that 561 is an absolute pseudoprime, he then concludes that $a^{561} \equiv a \pmod{561}$ for all $a$.

I searched a bit on the internet, and it seems that these two are actually equivalent definitions of a Carmichael number. However I have not been able to find a proof; the fact that the implication in the title of the post is stated so plainly in my textbook makes me think it is quite simple to see, but I can't seem to understand the argument.

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 $\ \ (1\Rightarrow 2)\ \ \ (1)\,\Rightarrow\, \color{#90f}{n\mid a}(a^{e-1}-1)\,\Rightarrow\, n\mid a^{e-1}-1\,$ by $\,\color{#90f}{n,a}\,$ coprime & Euclid's Lemma.

$(2\Rightarrow 3)\ \ $ Suppose prime $\,p\mid n,\,$ so $\,n = j\, p^k$ with $\,k\ge 1,\ p\nmid j.\,$ Let $\,g\,$ be a primitive root $\!\bmod p^k,\,$ i.e. $\,g\,$ has order $\,(p\!-\!1)p^{k-1}.\,$ By CRT there's $\,a\in\Bbb Z\,$ with $\,\ a\equiv 1\pmod{\!j},\,a\equiv g\pmod{\!p^k},\,$ thus $\,a\,$ is coprime to $\,j,p\,$ so also to $\,n = j\,p^k.\,$ So $\,(2)\Rightarrow\,a^{e-1}\equiv 1\,$ holds $\!\bmod n\,$ so also $\!\bmod p^k,\,$ thus Order Theorem $\Rightarrow\,(\color{#0a0}{p\!-\!1})p^{k-1}\!\mid \color{#0a0}{e\!-\!1}\,\Rightarrow\,k=1\,$ (else $\,p\mid e\!-\!1,n\,$ contra $\,(e\!-\!1,n)=1)$.

$(3\Rightarrow 1)\ \ $ Let prime $\,p\mid n.\,$ If $\,p\mid a\,$ then $\,p\mid a^e-a\,$ by $\,e>1.\,$ Else $\,p\nmid a\,$ so by little $\rm\color{#c00}{Fermat}$ $\!\bmod p\!:\ a^{\large\color{#0a0}{e-1}}\equiv \smash[t]{\color{#c00}{(a^{\color{#0a0}{\large p-1}})}}^{\large\color{#0a0} k}\equiv \color{#c00}1^{\large k}\!\equiv 1\,$ so $\,p\mid a^{e-1}-1\mid a^e-a.\,$ So $\, a^e-a\,$ is divisible by all primes $\,p\mid n\,$ so also by their lcm = product = $\,n,\,$ by $\,n\,$ squarefree. $\,(e\!-\!1,n)=1\,$ by $\,p\mid n\,\Rightarrow\,p\nmid e\!-\!1$.

Remark $\,\ (3)\, $ for $\,e=n\,$ is known as Korselt's criterion for Carmichael numbers.