Task 5. Find all pairs of prime numbers $(p, q)$ for which

$$
2^{p}=2^{q-2}+q! .
$$
Solution. Answer: the only pairs $(p, q)$ that satisfy are $(3,3)$ and $(7,5)$.

First, we will go through a few small cases. If $q=2$, then $2^{p}=1+2$ has no solution. If $q=3$, then $2^{p}=2+6$ gives $p=3$ as the only solution. If $q=5$, then $2^{p}=8+120$ gives $p=7$ as the only solution. Henceforth, we may assume that $q$ is at least 7.

Now, we observe that we can rewrite the condition as

$$
q !=2^{p}-2^{q-2}=2^{q-2}\left(2^{p-q+2}-1\right).
$$

Since $q!$ is positive, the right-hand side must also be positive. In particular, $2^{p-q+2}>1$, so $p-q+2>0$ and $2^{p-q+2}$ is an integer (and greater than 1). We conclude that $2^{p-q+2}-1$ is an integer and odd. Therefore, the right-hand side has exactly $q-2$ factors of 2. To count the number of factors on the left-hand side, let $\nu_{2}(a)$ be the function that counts how many factors an integer $a$ has. Since $q$ is a prime number greater than 2, it is odd. Then $\left\lfloor\frac{q}{2}\right\rfloor=\frac{q-1}{2}$ and in general $\left\lfloor\frac{q}{2^{i}}\right\rfloor=\left\lfloor\frac{q-1}{2^{i}}\right\rfloor$. Let $n$ now be the integer such that $2^{n}<q<2^{n+1}$. Then we calculate that

$$
\begin{aligned}
\nu_{2}(q !) & =\left\lfloor\frac{q}{2}\right\rfloor+\left\lfloor\frac{q}{4}\right\rfloor+\ldots+\left\lfloor\frac{q}{2^{n}}\right\rfloor \\
& =\left\lfloor\frac{q-1}{2}\right\rfloor+\left\lfloor\frac{q-1}{4}\right\rfloor+\ldots+\left\lfloor\frac{q-1}{2^{n}}\right\rfloor \\
& \leq(q-1)\left(\frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^{n}}\right) \\
& =(q-1)\left(1-\frac{1}{2^{n}}\right) \\
& =(q-1)-\frac{q-1}{2^{n}} \\
& \leq q-2 .
\end{aligned}
$$

In both inequalities above, equality holds if and only if $q=2^{n}+1$ (and we used in the second line that $q$ is odd). Due to the condition, equality must also hold, so $q=2^{n}+1$ for some natural number $n$.

Now that we have come a long way by looking at factors of 2, we would like to derive a contradiction from equation (2) using modular arithmetic since $q!$ has many prime factors. From our small examples, we know that this will not work modulo 3 or 5, so we try the next prime number: 7.

Since we have assumed that $q$ is at least 7, $q!$ is indeed divisible by 7. This means that $2^{p-q+2} \equiv 1 \bmod 7$. Since also $2^{3} \equiv 8 \equiv 1 \bmod 7$, this means that $2^{\operatorname{ggd}(p-q+2,3)} \equiv 1 \bmod 7$. But $2^{1} \not \equiv 1 \bmod 7$, so $\operatorname{ggd}(p-q+2,3)=3$ or $p-q+2 \equiv 0 \bmod 3$. We know, however, that $q=2^{n}+1$ is congruent to -1 or 0 modulo 3. Since we also know that $q$ is prime (and greater than 3), the second case is ruled out, and we conclude that $q \equiv-1 \bmod 3$. But then the previous gives $p \equiv q-2 \equiv-1-2 \equiv 0 \bmod 3$. Since $p$ is also prime, we conclude that $p=3$. But $2^{q-2}+q !=2^{3}=8$ has no solutions for $q \geq 7$.

We conclude that the only pairs $(p, q)$ that satisfy are $(3,3)$ and $(7,5)$.

Remark. In general, if an arbitrary natural number $q$ in binary notation has $r$ digits 1, then

$$
\nu_{2}(q !)=\sum_{i=1}^{\infty}\left\lfloor\frac{q}{2^{i}}\right\rfloor=q-r
$$

So for $2^{n}<q<2^{n+1}$, it holds due to $r \geq 2$ that $\nu_{2}(q !) \leq q-2$ with equality if and only if $r=2$. If $q$ is also odd, then $q=2^{n}+1$ (because $q=2^{n}+2^{k}$ with $k \geq 1$ is even).