Irish Mathematical Olympiad

Because $(2^n + n) - (2^n - 1) = n + 1$, we have $\text{gcd}(2^n + n, 2^n - 1) = \text{gcd}(n + 1, 2^n - 1)$.
From $2^2 \equiv 4 \pmod{5}$, $2^3 \equiv 3 \pmod{5}$ and Fermat's Little Theorem we see that $2^n \equiv 1 \pmod{5}$ iff $n$ is divisible by 4. Hence, when $n \equiv -1 \pmod{5}$ and $n \equiv 0 \pmod{4}$, the two numbers $2^n + n$ and $2^n - 1$ are both divisible by 5. They can only be co-prime for $n \equiv 2 \pmod{4}$.
Suppose $n = 4k + 2$, then $n + 1 = 4k + 3$ and this number is divisible by 5 exactly when $k \equiv 3 \pmod{5}$. Such $k$ can be written as $k = 5m + 3$ and so $n = 20m + 14$. This means that the smallest candidates for $n$ for which $2^n + n$ and $2^n - 1$ could be co-prime, are $n = 14, 34, 54, \dots$.
Next we observe that $2^n \equiv (-1)^n \equiv 1 \pmod{3}$ for all even numbers $n$. Hence, whenever $n+1$ is divisible by 3, the two numbers $2^n + n$ and $2^n - 1$ are both divisible by 3. This rules out $n = 14$.
Consider $n = 34$, then $n + 1 = 35 = 5 \cdot 7$. As we have seen above, $2^4 \equiv 1 \pmod{5}$ and so $2^{34} \equiv 2^2 \equiv 4 \pmod{5}$ which means that 5 does not divide $\text{gcd}(35, 2^{34} - 1)$. Similarly, we have $2^3 \equiv 1 \pmod{7}$ and so $2^{34} \equiv 2 \pmod{7}$, which shows that 7 does not divide $\text{gcd}(35, 2^{34} - 1)$. Hence, $\text{gcd}(35, 2^{34} - 1) = 1$ and $n = 34$ is the smallest positive even integer for which $n+1$ is divisible by 5 and for which $2^n + n$ and $2^n - 1$ are co-prime.