CASE I if $\gcd(n,\phi(n))\ne 1$
First suppose there is a prime $p$ such that $p^2$ divides $n$ and suppose that we could solve $m^m\equiv p\pmod n$. Then $m$ would be a multiple of $p$ and so $p^2$ would be a factor of $m^m$ and therefore of $p$, a contradiction.
Otherwise there must be two primes $p$ and $q$ such that $pq$ divides $n$ and $p$ divides $q-1$.
Consider $\{ x^p|(x,q)=1\}$. This set contains $\frac{q-1}{p}$ residues modulo $q$ and so we can choose a positive integer $t$ such that $tp$ is not congruent modulo $q$ to any member of this set. Now suppose that we could solve $m^m\equiv tp\pmod n$. Then $m$ would be a multiple of $p$ and so $tp$ would be congruent modulo $q$ to a $p$th power after all, a contradiction.
CASE II if $\gcd(n,\phi(n))= 1$
First suppose that $a$ is coprime to $n$. Since $\phi(n)$ is also coprime to $n$ we can choose a positive integer $t$ such that $1+t\phi(n)\equiv a\pmod n$. Let $m=1+t\phi(n)$. Then $$m^m \equiv (1+t\phi(n))(1+t\phi(n))^{t\phi(n)}\equiv 1+t\phi(n)\equiv a\pmod n.$$
Now suppose $a$ is not coprime to $n$. Let $n=PQ$ where $P$ divides $a$ and $Q$ is coprime to $a$ and $P$.
Then we can find a positive integer $t$ such that $(tP)^P\equiv a\pmod Q$ and then find an integer $s$ such that $t\equiv 1+s\phi(Q)\pmod Q$. Let $m=(1+s\phi(Q))P$. Then $$m^m \equiv (tP)^{(1+s\phi(Q))P}\equiv (tP)^P\equiv a\pmod Q.$$
$P$ divides both $m$ and $a$ and so $m^m \equiv a\pmod {PQ}.$
There are an infinite number of solution pairs. That's a general result for quadratic Diophantine equations: they either have no solution (except perhaps for trivial solutions involving zero), or they have an infinite number of solutions, although those solutions will fall into a finite number of families. IIRC, Lagrange gave the first proof of that result (along with various other important proofs on Pell's equation and quadratic forms).
As mentioned by Daniyar, for both equations to have integer solutions, both $p^2-4q$ and $p^2-3q$ must be perfect squares.
Let
$$p^2-4q=r^2$$
$$p^2-3q=s^2$$
Subtracting,
$$q=s^2-r^2$$
and substituting
$$p^2=4s^2-3r^2$$
Using Brahmagupta's identity, products of integers of the form $4s^2-3r^2$ are also of that form if the second terms are even:
$$(4s^2-3r^2)(4x^2-3y^2)$$
$$=(16s^2x^2+9r^2y^2) - 3(4s^2y^2+4r^2x^2)$$
$$=(16s^2x^2+9r^2y^2 \pm 24sxry) - 3(4s^2y^2+4r^2x^2 \pm 8syrx)$$
$$=(4sx \pm 3ry)^2 - 3(2sy \pm 2rx)^2$$
If either of $r$ or $y$ are even, $4sx \pm 3ry$ will also be even.
Now we could search for numbers of the form $4s^2-3r^2$, looking for perfect squares. But we can use a minor modification of the above identity to construct such squares.
Let
$$s=(u^2+3v^2)/4$$
where $u$ & $v$ are coprime and both odd, hence
$$u^2\equiv v^2\equiv 1\pmod 4$$
and
$$u^2+3v^2\equiv 0\pmod 4$$
(so $s$ is an integer), and let
$$r=uv$$
So
$$4s^2-3r^2$$
$$=(u^2+3v^2)^2/4-3u^2v^2$$
$$=(u^4+9v^4+6u^2v^2 - 12u^2v^2)/4$$
$$=(u^4+9v^4-6u^2v^2)/4$$
$$=(u^2-3v^2)^2/4$$
Note that $(u^2-3v^2)\equiv 2 \pmod 4$, i.e., it's twice an odd number, so $(u^2-3v^2)^2$ is an even square, and
$$p=(u^2-3v^2)/2$$
is an odd integer. We do need to choose appropriate $(u, v)$ pairs to ensure that $p$ and $q$ are positive.
Now sometimes $\gcd(p,q)=3$, but if that's not the case they are coprime, so we can easily multiply them both by 3 to achieve the desired GCD constraint.
I'll leave the proof of that as an exercise for the reader. ;)
Here are some solutions constructed using the above procedure.
$$\begin{array}{|r|r|}
\hline
p & q \\
\hline
33 & 72 \\
39 & 360 \\
69 & 360 \\
111 & 3024 \\
141 & 840 \\
177 & 2520 \\
183 & 5616 \\
213 & 2640 \\
219 & 11880 \\
249 & 5040 \\
291 & 12240 \\
321 & 3168 \\
327 & 22176 \\
363 & 32760 \\
393 & 10920 \\
429 & 8568 \\
429 & 15120 \\
501 & 18480 \\
537 & 23760 \\
573 & 7920 \\
681 & 28728 \\
717 & 19872 \\
753 & 43680 \\
789 & 51480 \\
897 & 15960 \\
897 & 62832 \\
933 & 72072 \\
1041 & 59400 \\
1149 & 94248 \\
1221 & 118560 \\
1257 & 131040 \\
\hline
\end{array}$$
You can see more solution pairs using this small interactive Python script. The script itself is encoded into the URL, and it runs on a SageMath, Inc, server. I use a Farey sequence generator to produce coprime $(u, v)$ pairs. The script parameter $m$ selects the Farey sequence.
Best Answer
First: If $p$ is a prime and $$n=\frac{a^{2p}-1}{a^2-1} =1+a^2+a^4+...+a^{2p-2}$$
Then $$ 1+a^2+a^4+...+a^{2p-2}=0 \pmod{n} \\ a^2( 1+a^2+a^4+...+a^{2p-2})=0 \pmod{n} \\ a^2+a^4+...+a^{2p-2}+a^{2p}=0 \pmod{n} \\ $$
Subtracting the first and last relation you get $$1=a^{2p} \pmod{n}$$
Now, if you now chose $p,n$ so that $2p |n-1$ you get $$a^{n-1} \equiv 1 \pmod{n}$$
Note that $2p |n-1$ means $$2p|a^2(1+a^2+...+a^{2p-4})$$
It is easy to make the RHS even and if you want $$p|1+a^2+...+a^{2p-4}$$ the easiest way is to pick $p >a^2-1$ (to make sure that $a^2-1$ cannot be divisible by $p$) and use $$a^{2p-2} \equiv (a^{p-2})^2\equiv 1 \pmod{p}$$