El PTF lo resuelve --si le piensas un poquito...

$q = 2$ es una posibilidad. Busquemos entonces los primos impares que satisfacen la condición dada.

Del pequeño teorema de Fermat se tiene que $q$ debe ser divisor de $2^{q-1} - 1$. Como además $q$ es coprimo con $2$ y es tal que $q | (2^{q}+4) =$ $2(2^{q-1}+2)$ se sigue que $q$ debe ser divisor de $2^{q-1}+2$. Luego, $q$ debe dividir a cualquier combinación de $(2^{q-1} - 1)$ y $(2^{q-1}+2)$. En particular debe tenerse que $q | (2^{q-1}+2) - (2^{q-1}-1) =$ $3$. De esto último se concluye que $q=3$ es el único primo impar que cumple con la restricción dada y terminamos.