Note that if you already know the uniqueness criterion for CRT then the sought result is *immediate*, i.e. both $\,\color{#0a0}{x_0 = 1}\,$ and the CRT formula $\,x_1 = p(p^{-1}\!\bmod q) + q(q^{-1}\!\bmod p)$ are clearly solutions of the system $\,x\equiv 1\pmod{\!p},\ x\equiv 1\pmod{\!q},\,$ so by $\rm\color{#c00}{
U =}$ uniqueness $\,x_1\overset{\rm\color{#c00}U}\equiv \color{#0a0}{x_0\equiv 1}\pmod{\!pq}$.

Your question essentially asks for a (direct) proof of the uniqueness criterion. It is easy to show that the uniqueness criteria for [C]CRT, linear diophantine equations, and modular inverses are all *equivalent* (to Euclid's lemma and many other closely related basic results). Below is a direct proof via **inverse uniqueness** (with a trivial one-line proof) & $\rm\color{#0a0}{Bezout\ identity}$ for $\gcd(p,q)=1$.

There are $\,p',q'\in\Bbb Z\,$ with $\,\color{#0a0}{pp'\!+\!qq' = 1},\,$ so $\, \color{0a0}{pp'\equiv 1}\pmod{\!\color{darkorange1}q},\,$ so by **inverse uniqueness** $\,p^{-1}\equiv p'\!\pmod{\!q},\,$ so $\, p^{-1^{\phantom{|^|}}}\!\!\! = p'\!+\!iq,\,$ some $\,i\in\Bbb Z.\,$ Similarly $\,q^{-1^{\phantom{|^|}}}\!\!\! = q'\!+\!jp,\,$ some $\,j\in \Bbb Z,\,$ therefore
$\, \color{#90f}{pp^{-1}\!+qq^{-1^{\phantom{|^|}}}}\!\!\! = p(p'\!+\!iq)+q(q'\!+\!jp)$ $ = pp'\!+\!qq'^{\phantom{|^|}}\!\!\!+\color{#c00}{pq}(i\!+\!j)\:\!\equiv_{\color{#c00}{pq}}\:\!\color{#0a0}{pp'\!+\!qq'\, [= 1]}$

**Remark** $ $ No answer actually "deals with the $\color{#0af}{1\!+\!1}$" -- which arise from your change from working with inverses $p^{-1},q^{-1}$ to working with their $\color{#c00}{{\rm negatives}\ \,k,k'}\,$ (which has the following effect on the Bezout identity summands: $\,i+j = 1\iff \color{#c00}{-i}+(\color{#c00}{-j})+\color{#0af}{2}=1).\,$ Rather, we *eliminate* the more unwieldly negative inverses by changing back to $\,p^{-1},q^{-1},\,$ i.e. read your last displayed equations in reverse
to get $\,\color{#c00}kp+\color{#c00}{k'}q+\color{#0af}2 = \color{#90f}{p^{-1}p+q^{-1}p},\,$ which is $\color{#0a0}{\equiv 1\pmod{pq}}\,$ as proved above.

As usual, these matters are clarified arithmetically when viewed via the (product) *ring* form of CRT (see here for a simple intro requiring no knowledge of ring theory). Namely, your change to use of $\rm\color{#c00}{negated}$ inverses $\,\color{#c00}{k\equiv_q -p^{-1}}\,$ and $\,\color{#c00}{k'\equiv_p -q^{-1}}\,$ corresponds to a basis change to the negated standard basis $\,(0,\color{#c00}{-1}),(\color{#c00}{-1},0)\,$ vs. the normal standard basis $\,(0,1),(1,0).\,$ Then your final equation arises by negating the Bezout equation $\rm E$ then adding $\,\color{#0af}2,\,$ i.e. $\,\rm E\to -E\to \color{#0af}2+E,\,$ i.e.

$$\begin{align}
\ \overbrace{(0,1)\ +\ (1,0)\ \equiv \ (1,1)}^{\textstyle\!\! \color{#90f}{p^{-1}p\ +\,\ q^{-1}q}\ \equiv\ 1\ \ \ \ \ }
\!\overset{\rm -E}\iff \ \overbrace{(0,\color{#c00}{-1})+ (\color{#c00}{-1},0)\ \equiv \ (\color{#c00}{-1,-1})}^{\textstyle\!\!\!\!\!\!\!\!\!\!\!\!\!\!\color{#c00}{-p^{-1}}p\, \ \color{#c00}{-\ \ q^{-1}}q\, \ \ \equiv \ \ {-}1} \\[.7em]
\underset{\rm \color{#0af}2\,+\,E^{\phantom |}\!}\iff\ \ \underbrace{\color{#0af}{(2,2)}+ (0,\color{#c00}{-1})+(\color{#c00}{-1},0)\ \equiv\ (1,1)}_{\textstyle\!\!\! \color{#0af}{2}\ \ \ +\ \ \ \color{#c00}kp\ \ \ \ +\ \ \ \ \color{#c00}{k'}q\ \ \equiv\ \ 1}\quad\ \
\end{align}\qquad\qquad$$

Thus the three above congruences $\!\bmod{pq}\,$ are all trivially *equivalent*, so it suffices to prove any one of them. It is easiest to prove the first (as we did above) since it connects more immediately to the intuitive arithmetical notion of *inverses* and their *uniqueness*. As is often true in algebraic proofs, a slight algebraic transformation of equations may transform them into a form which better reveals innate arithmetical structure facilitating intuition and proof. As such we should strive to transform *towards* such intuitive forms - not *away* from them (as do the above transforms to *negated* inverses and basis).

## Best Answer

The result is that $M$ is good if and only if every prime divisor of $\phi(M)$ is also a divisor of $M$. This is the sequence A151999 on OEIS.

"If" part:

Suppose that every prime divisor of $\phi(M)$ is also a divisor of $M$. Let $n$ be a positive integer such that $n^n \equiv 1\pmod M$ and let $d$ be the order of $n$ mod $M$. It follows that $d \mid n$ and also $d \mid \phi(M)$. But clearly $n$ is prime to $M$, and hence is prime to $\phi(M)$ because of the assumption on $M$. This implies $d = 1$ and therefore $n \equiv 1\pmod M$.

"Only if" part:

Suppose that there exists a prime divisor $p$ of $M$ and a prime number $q$ such that $q \mid p - 1$ but $q$ is prime to $M$. We want to show that $M$ is bad.

Write $M = p^r N$ with $N$ prime to $p$. We know that the multiplicative group $\Bbb Z/p^r\Bbb Z$ is cyclic and has order disivible by $q$, therefore there exists $x$ such that $x^q \equiv 1 \pmod{p^r}$ and $x \not\equiv 1 \pmod {p^r}$.

By Chinese remainder theorem, we can find $n$ such that $n \equiv 0 \pmod q$, $n \equiv x \pmod {p^r}$ and $n \equiv 1 \pmod N$.

Clearly $n \not\equiv 1 \pmod M$. On the other hand, we have $n^n \equiv (x^q)^{n/q} \equiv 1\pmod{p^r}$ and also $n^n \equiv 1 \pmod N$, thus $n^n \equiv 1 \pmod M$.