1. N1 (TWN) ${ }^{1 \mathrm{MO} 04}$ Find all pairs of positive integers $(x, p)$ such that $p$ is a prime, $x \leq 2 p$, and $x^{p-1}$ is a divisor of $(p-1)^{x}+1$.
1. Obviously $(1, p)$ (where $p$ is an arbitrary prime) and $(2,2)$ are solutions and the only solutions to the problem for $x<3$ or $p<3$.
Let us now assume $x, p \geq 3$. Since $p$ is odd, $(p-1)^{x}+1$ is odd, and hence $x$ is odd. Let $q$ be the largest prime divisor of $x$, which also must be odd. We have $q|x| x^{p-1} \mid(p-1)^{x}+1 \Rightarrow(p-1)^{x} \equiv-1(\bmod q)$. Also from Fermat's little theorem $(p-1)^{q-1} \equiv 1(\bmod q)$. Since $q-1$ and $x$ are coprime, there exist integers $\alpha, \beta$ such that $x \alpha=(q-1) \beta+1$. We also note that $\alpha$ must be odd. We now have $p-1 \equiv(p-1)^{(q-1) \beta+1} \equiv(p-1)^{1 \alpha} \equiv-1(\bmod q)$ and hence $q \mid p \Rightarrow q=p$. Since $x$ is odd, $p \mid x$, and $x \leq 2 p$, it follows $x=p$ for all $x, p \geq 3$. Thus
$$
p^{p-1} \left\lvert\,(p-1)^{x}+1=p^{2} \cdot\left(p^{p-2}-\binom{p}{1} p^{p-1}+\cdots-\binom{p}{p-2}+1\right) .\right.
$$

Since the expression in parenthesis is not divisible by $p$, it follows that $p^{p-1} \mid p^{2}$ and hence $p \leq 3$. One can easily verify that $(3,3)$ is a valid solution.
We have shown that the only solutions are $(1, p),(2,2)$, and $(3,3)$, where $p$ is an arbitrary prime.