
Problem 3. Find all prime numbers $p$ and $q$, such that the number $2^{p}+2^{q}$ is divisible by p.q.


Solution.

Lemma. If $k>1$, then $k$ doesn't divide $2^{k-1}+1$.

Proof. Assume that $k$ divides $2^{k-1}+1$. Obviously $k$ is odd. Let $k=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{r}^{\alpha_{r}}$, where $p_{1}, p_{2}, \ldots, p_{r}$ are odd prime numbers ( $p_{i} \neq p_{j}$ if $i \neq j$ ), $\alpha_{1}, \alpha_{2}, \ldots, \alpha_{r}$ are positive integers and $r \geq 1$. Let $p_{i}-1=2^{m_{i}} \cdot t_{i}$, where $t_{i}$ are odd integers ( $\left.i=1,2, \ldots, r\right)$. Let $m_{1}$ be the smallest number in the sequence $m_{1}, m_{2}, \ldots, m_{r}$. It follows from $p_{i} \equiv 1\left(\bmod \left(p_{i}-1\right)\right)$ that $p_{i} \equiv 1$

$\left(\bmod 2^{m_{i}}\right)$ and $p_{i}^{\alpha_{i}} \equiv 1\left(\bmod 2^{m_{i}}\right), i=1,2, \ldots, r$. Hence $k-1=2^{m_{1}} \cdot u(u$ is an integer). If $2^{k-1} \equiv-1 \quad(\bmod k)$, then $2^{2^{m_{1}} \cdot u} \equiv-1 \quad(\bmod k)$ and $2^{\left(p_{1}-1\right) \cdot u} \equiv-1 \quad\left(\bmod p_{1}\right)$, because $t_{1}$ is odd. But $2^{p_{1}-1} \equiv 1\left(\bmod p_{1}\right)$ - a contradiction.

Let $2^{p}+2^{q}$ is divisible by p.q. We have three cases:

1. $p$ and $q$ are odd prime numbers. Then $2^{p}+2^{q} \equiv 0(\bmod p)$ and since $2^{p} \equiv 2(\bmod p)$, then $2^{q} \equiv-2(\bmod p)$ and $2^{p q} \equiv(-2)^{p} \equiv-2 \quad(\bmod p)$. Similarly $2^{p q} \equiv-2 \quad(\bmod q)$. Thus $2^{p q-1} \equiv-1 \quad(\bmod p q)$, which is a contradiction with the lemma.
2. $p=2, q>2$. Then $4+2^{q} \equiv 0(\bmod q)$ and it follows from $2^{q} \equiv 2(\bmod q)$ that $6 \equiv 0(\bmod q)$ and $q=3$. It is clear that $2^{2}+2^{3}=12 \equiv 0(\bmod 2 \cdot 3)$.
3. $p=q=2$. Then $2^{2}+2^{2}=8 \equiv 0 \quad(\bmod 2 \cdot 2)$.

Therefore the sought numbers are: $p=q=2 ; p=2, q=3 ; p=3, q=2$.

## WINTER MATHEMATICAL COMPETITION

## Grade 8
