Solution for 29 October 2026

Answer. \(m\) works if and only if \(m\) is odd, or \(m=2k\) with \(k\) odd and every prime factor of \(k\) congruent to \(\pm1 \pmod 8\). So \(4\nmid m\) is necessary but not sufficient: \(m=6,10,30\) fail, while \(m=2,14,34,98\) work.

Step 1: a multiple of 4 never works. If \(n\) is odd then \(n^n\) is odd; if \(n\) is even then \(n\ge 2\) and \(4\mid n^n\). Either way \(n^n\not\equiv 2 \pmod 4\), so \(4\nmid m\).

Step 2: the even case forces quadratic residues. Let \(m=2k\) with \(k\) odd. From \(2\mid n^n-2\) the number \(n^n\) is even, so \(n\) is even and \(n^n=\bigl(n^{n/2}\bigr)^2\) is a perfect square. For every prime \(p\mid k\) we get \(2\equiv n^n\) modulo \(p\), so \(2\) is a quadratic residue modulo \(p\), and by the second supplement to quadratic reciprocity \(p\equiv\pm1\pmod 8\). This is the trap of the problem: after Step 1 it is tempting to stop at \(4\nmid m\), but \(m=6\) already fails because \(2\) is not a square modulo \(3\).

Step 3: why the obvious constructions fail. For an odd prime \(p\) and \(n\) prime to \(p\), the residue of \(n^n\) modulo \(p^e\) depends on \(n \bmod p^e\) (the base) and on \(n \bmod \varphi(p^e)=p^{e-1}(p-1)\) (the exponent), hence only on \(n\bmod p^e\) and \(n \bmod (p-1)\). The two roles of \(n\) are coupled inside one prime (the residue modulo \(p^{e-1}\) is both base and exponent information) and across primes (the residue modulo \(p-1\) involves the residues of \(n\) modulo the smaller primes dividing \(p-1\)). For instance \(n\equiv 2 \pmod m\) together with \(n\equiv 1\pmod{\operatorname{ord}_m 2}\) is already contradictory for \(m=21\), since \(\operatorname{ord}_{21}2=6\) and the two conditions disagree modulo \(3\). The cure is a lifting lemma inside one prime and an ordering of the primes across primes.

Step 4: lifting lemma. Let \(p\) be an odd prime, \(j\ge1\), and let \(n_0\) satisfy \(p\nmid n_0\) and \(n_0^{n_0}\equiv 2\pmod{p^j}\), say \(n_0^{n_0}\equiv 2+s\,p^j \pmod{p^{j+1}}\). Put \(\delta=t\,p^j(p-1)\) and \(n'=n_0+\delta\). Since \(n'\equiv n_0 \pmod{\varphi(p^{j+1})}\) and \(n'\) is prime to \(p\), we have \(n'^{\,n'}\equiv n'^{\,n_0}\pmod{p^{j+1}}\). By the binomial theorem, as \(p^{2j}\mid\delta^2\), \[n'^{\,n_0}=(n_0+\delta)^{n_0}\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\delta=n_0^{n_0}(1+\delta)\equiv 2+s\,p^j-2t\,p^j \pmod{p^{j+1}},\] using \(n_0^{n_0}\equiv 2\pmod p\) and \(p-1\equiv -1\pmod p\). Choosing \(t\equiv s/2\pmod p\) (possible since \(p\) is odd) gives \(n'^{\,n'}\equiv 2\pmod{p^{j+1}}\), and \(n'\equiv n_0 \pmod{p(p-1)}\). Iterating, a solution modulo \(p\) with \(p\nmid n_0\) lifts to some \(n_p\equiv n_0\pmod{p(p-1)}\) with \(n_p^{n_p}\equiv 2\pmod{p^e}\) for any \(e\).

Step 5: the construction, primes in increasing order. Let \(m\) be as in the answer, let \(k\) be its odd part with prime factorisation \(k=p_1^{e_1}\cdots p_r^{e_r}\), \(p_1<\dots<p_r\), and let \(L=\operatorname{lcm}(p_i-1)\). We build \(n\) by the Chinese remainder theorem, fixing its residues prime by prime.

First fix the residues at primes not dividing \(k\): modulo \(2^{\max(2,v_2(L))}\) take \(n\equiv1\) if \(m\) is odd and \(n\equiv 2\) if \(m\) is even; for each odd prime \(q\mid L\) with \(q\nmid k\) take \(n\equiv 1\pmod{q^{v_q(L)}}\).

Now treat \(p=p_1,p_2,\dots,p_r\) in increasing order. Every prime factor of \(p-1\) is smaller than \(p\), so it is \(2\), or a prime not dividing \(k\), or an earlier \(p_i\), and in each case the residue of \(n\) modulo its full power in \(L\) is already fixed. Hence \(c:=n \bmod (p-1)\) is already determined. All odd residues fixed so far are units, so \(\gcd(c,p-1)=1\) when \(m\) is odd, and \(\gcd(c,p-1)=2\) when \(m\) is even (then \(c\) is even, and \(c\equiv 2\pmod 4\) whenever \(4\mid p-1\)).

Solve \(\alpha^c\equiv 2\pmod p\). If \(\gcd(c,p-1)=1\), take \(\alpha=2^{c'}\) with \(cc'\equiv1\pmod{p-1}\). If \(\gcd(c,p-1)=2\), write \(2\equiv g^w\) for a primitive root \(g\); since \(p\equiv\pm1\pmod 8\), \(2\) is a quadratic residue, so \(w\) is even, the congruence \(cu\equiv w\pmod{p-1}\) is solvable, and \(\alpha=g^u\) works. Let \(n_0\equiv\alpha\pmod p\) and \(n_0\equiv c\pmod{p-1}\). Then \(p\nmid n_0\) and \(n_0^{n_0}\equiv\alpha^c\equiv2\pmod p\). Step 4 gives \(n_p\) with \(n_p\equiv c\pmod{p-1}\) and \(n_p^{n_p}\equiv2\pmod{p^{e}}\). Impose \(n\equiv n_p\pmod{p^{\max(e,v_p(L))}}\) (any lift of \(n_p \bmod p^e\)); this is compatible with everything fixed so far, because \(p\) is a new prime. The new residue modulo \(p\) is the unit \(\alpha\), so the coprimality used above persists.

Step 6: conclusion. For the final \(n\) and each \(p^e\,\|\,k\) we have \(n\equiv n_p\pmod{p^e}\) and \(n\equiv c\equiv n_p\pmod{p-1}\), hence \(n\equiv n_p \pmod{p^{e}(p-1)}\), and therefore \(n^n\equiv n_p^{n_p}\equiv2\pmod{p^e}\). By the Chinese remainder theorem \(k\mid n^n-2\). If \(m\) is odd we are done. If \(m=2k\), then \(n\) is even, so \(n^n-2\) is even and \(2k\mid n^n-2\). Together with Steps 1 and 2 this proves the answer.

Check. An exhaustive search over \(n\) through a full period of \(n^n \bmod m\) confirmed that the set of good \(m\le 1200\) is exactly the set described. The construction of Steps 4 and 5 was also implemented and produced a valid \(n\) for 3300 admissible values of \(m\), including random \(m\) up to \(2\cdot10^5\) and moduli such as \(2\cdot31^4\cdot7\) and \(3^5\cdot5^3\cdot7^2\cdot11\cdot13\).