Ireland_2017

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(\mathrm{mod}5)$, $2^3\equiv 3(\mathrm{mod}5)$ and Fermat's Little Theorem we see that $2^n\equiv 1(\mathrm{mod}5)$ iff $n$ is divisible by 4. Hence, when $n\equiv -1(\mathrm{mod}5)$ and $n\equiv 0(\mathrm{mod}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(\mathrm{mod}4)$. Suppose $n=4k+2$, then $n+1=4k+3$ and this number is divisible by 5 exactly when $k\equiv 3(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}5)$ and so $2^{34}\equiv 2^2\equiv 4(\mathrm{mod}5)$ which means that 5 does not divide $\text{gcd}(35,2^{34}-1)$. Similarly, we have $2^3\equiv 1(\mathrm{mod}7)$ and so $2^{34}\equiv 2(\mathrm{mod}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.