We induct on $k$. So by induction, we can find $l$ such that $m \equiv n \pmod {\varphi(k)}$. By letting $\varphi(k)$ and $k$ divide $l$, we can assume $m,n$ coprime to both $\varphi(k)$ and $k$. Hence letting $m \equiv n \equiv i \pmod {\varphi(k)}$, since $\gcd(i,\varphi(k)) = 1$ we know that $x^i$ is bijective mod $k$ on coprime residues. Thus $$m^m \equiv n^n \pmod k \implies m^i \equiv n^i \pmod k \implies m \equiv n \pmod k$$as desired and our induction is done where we can take $k = 1$ as our base case.

Same idea as above. We go backwards, if $m\equiv n \pmod k$, and if we force $\gcd(mn, k)=1$, then $\varphi(k) \mid m-n$. Hence, in our case $m^m\equiv n^n \pmod{\ell}$ also implies $m\equiv n \pmod{\varphi(k)}$, which by similar argument implies $m\equiv n \pmod{\varphi(\varphi(k))}$, and so on. Therefore we set $\ell = k \cdot \varphi(k) \cdot \varphi^{(2)}(k) \cdots \varphi^{(s)}(k)$, where $\varphi^{(s)}(k)=1$ and $s$ is the smallest such number. Then we can go backwards $\varphi^{(s-1)}(k)=2$, so $m^m\equiv n^n \pmod{\ell}$ and $\gcd(mn, 2)=1$ imply $m \equiv n \equiv 1 \pmod 2$. Similarly, if $m \equiv n \equiv r \pmod {\varphi^{(j)}(k)}$ and $m^m\equiv n^n \pmod{ \ell}$, then $m^r\equiv n^r \pmod{ \varphi^{(j-1)}(k)}$. We have $\gcd(r, \varphi^{(j)}(k))=1$ and $0< r < \varphi^{(j)}(k)$, and because $r$ must be divisible by the order of $(m/n)$ modulo $\varphi^{(j-1)}(k)$, the only possibility is $r=1$. Thus $m \equiv n \pmod {\varphi^{(j-1)}(k)}$, and we can conclude the result by induction argument.

Let $$k = l!$$