Example 3 Find all pairs of positive integers $(m, n), m, n \geqslant 2$, such that for any $a \in\{1$, $2, \cdots, n\}$, we have $a^{n} \equiv 1(\bmod m)$.
When $m$ is an odd prime and $n=m-1$, by Fermat's Little Theorem, the pair $(m, n)$ satisfies the condition. Conversely, must $(m, n)=(p, p-1)$, where $p$ is an odd prime?

Now, let $(m, n)$ be a pair of positive integers that satisfy the condition, and let $p$ be a prime factor of $m$. Then $p>n$ (otherwise, if $p \leqslant n$, take $a=p$, then $m \mid\left(p^{n}-1\right)$, but $p \nmid\left(p^{n}-1\right)$, a contradiction).

Consider the polynomial
$$f(x)=(x-1)(x-2) \cdot \cdots \cdot(x-n)-\left(x^{n}-1\right)$$

Given $p>n$, and for $a \in\{1,2, \cdots, n\}$, we have $m \mid\left(a^{n}-1\right)$ (and thus $p \mid\left(a^{n}-1\right)$), it follows that in modulo $p$, $f(x) \equiv 0(\bmod p)$ has $n$ distinct roots. Since $f(x)$ is an $n-1$ degree polynomial, by Lagrange's Theorem, $f(x)$ is the zero polynomial modulo $p$, meaning every coefficient of $f(x)$ is a multiple of $p$. In particular, the coefficient of $x$ in $f(x)$ is $\equiv 0(\bmod p)$, i.e.,
$$p \mid(1+2+\cdots+n)$$

Thus, $p \mid n(n+1)$. Given $p>n$, it must be that $p=n+1$.
The above discussion shows that $(m, n)=\left(p^{\alpha}, p-1\right)$, where $p$ is an odd prime, and $\alpha \in \mathbf{N}^{*}$.
If $\alpha>1$, by the condition, we have $p^{\alpha} \mid\left((p-1)^{p-1}-1\right)$, hence
$$(p-1)^{p-1} \equiv 1\left(\bmod p^{2}\right)$$

Using the binomial theorem, we get
$$\begin{aligned}
1 & \equiv(p-1)^{p-1} \equiv \mathrm{C}_{p-1}^{1} \cdot p \cdot(-1)^{p-2}+1 \\
& \equiv 1-p(p-1) \equiv 1+p\left(\bmod p^{2}\right)
\end{aligned}$$

This is a contradiction, so $\alpha=1$.
In summary, the pairs $(m, n)=(p, p-1)$, where $p$ is any odd prime, satisfy the condition.