Bulgarian Mathematical Olympiad

Solution:
Since $p-1$ is a divisor of $p!$ the greatest common divisor of $p-1$ and $p!+2^{n}$ is a power of two. We shall show that both numbers $p-1$ and $p!+2^{n}$ have at least one odd divisor.

Suppose that $p-1=2^{k}$, i.e. $p=2^{k}+1$. If $s \geq 3$ is an odd divisor of $k$ then
$p=2^{s t}+1=\left(2^{t}+1\right) A$, i.e. $p$ is not a prime number. Therefore $k=2^{t}$ giving
$$\begin{aligned} 2^{p-1}-1 & =2^{2^{k}}-1=\left(2^{2^{k-1}}-1\right)\left(2^{2^{k-1}}+1\right)=\cdots \\ & =\left(2^{2^{t}}-1\right)\left(2^{2^{t}}+1\right)\left(2^{2^{t+1}}+1\right) \ldots\left(2^{2^{k-1}}+1\right) \end{aligned}$$
It is clear that $p^{2}$ does not divide the above product since $\left(2^{2^{t}}+1,2^{2^{l}}+1\right)=1$ when $l>t$, and $2^{2^{t}}-1<p=2^{2^{t}}+1$. Therefore $p-1$ is not a power of 2.

Suppose that $p!+2^{n}=2^{k}$, giving $k>n$ and $p!=2^{n}\left(2^{k-n}-1\right)$. Then $p$ is a divisor of $2^{m}-1$, where $m=k-n$. Let $t$ be the least positive integer such that $p$ divides $2^{t}-1$. Then $t$ is a divisor of $m$ and $t$ is a divisor of $p-1$. If $p-1=l t$ then
$$2^{p-1}-1=\left(2^{t}-1\right)\left(2^{t(l-1)}+2^{t(l-2)}+\cdots+2^{t}+1\right)$$
Since $2^{t} \equiv 1(\bmod p)$ we have $2^{t(l-1)}+2^{t(l-2)}+\cdots+2^{t}+1 \equiv l \not \equiv 0(\bmod p)$. Therefore $p^{2}$ is a divisor of $2^{t}-1$ which implies that $p^{2}$ is a divisor of $2^{m}-1$, i.e. $p^{2}$ is a divisor of $p!$, a contradiction.

Thus, both $p-1$ and $p!+2^{n}$ have at least one odd divisor and these divisors are distinct. Therefore the product $(p-1)\left(p!+2^{n}\right)$ has at least three distinct prime divisors.