Find all prime numbers $p, q$ such that $p q$ divides $2^{p}+2^{q}$.

## - Exercise Solutions -
First, note that if $p=2, 2q$ divides $4+2^q$ if and only if either $q=2$ or $2q$ divides 6, since for any odd $q$, $q$ divides $2^{q-1}-1$, so $2q$ divides $2^q-2$. Hence the solutions: $(p, q)=(2,2),(2,3)$ or $(3,2)$. We will now assume $p$ and $q$ are odd. Let $\omega_p$ and $\omega_q$ be the orders of 2 modulo $p$ and $q$ respectively. Suppose $p$ divides $2^p+2^q$, hence $2^{p-1}+2^{q-1}$ (since 2 is invertible modulo $p$, we can divide by 2), and since $p$ divides $2^{p-1}-1$, $p$ divides $2^{q-1}+1$, so $p$ divides $2^{2(q-1)}-1$. Therefore, $\omega_p$ divides $p-1$ and $2(q-1)$ but does not divide $q-1$. Let $v_2$ be the 2-adic valuation. The fact that $\omega_p$ divides $p-1$ implies that $v_2(\omega_p) \leq v_2(p-1)$, and the fact that $\omega_p$ divides $q-1$ but not $2(q-1)$ implies that $v_2(\omega_p) = 1 + v_2(q-1)$ (to convince yourself, look at the prime factorizations). Now, symmetrically, we have $v_2(\omega_q) \leq v_2(q-1)$, and thus $v_2(\omega_p) = 1 + v_2(q-1) > v_2(\omega_q)$. Symmetrically, $v_2(\omega_q) > v_2(\omega_p)$, which is absurd.

## 2 TD of arithmetic

## - Statements -