$n=4$ works

jelena_ivanchic wrote: $n=4$ works Except it doesn't. The lowest $n$ that works is $34$.

Eka01 wrote: jelena_ivanchic wrote: $n=4$ works Except it doesn't. The lowest $n$ that works is $34$. Clearly $n=5k-1$ for some odd integer $k$ and by Euclid's algorithm, we have $$\gcd(2^n+n, 2^n-1)=\gcd(5k, 2^{5k-1}-1).$$It is easy to see that $k=1, 3, 5$ fail: $\gcd(5, 15)=5\neq 1$; $\gcd(15, 2^{14}-1)\neq 1$ as $3=2^2-1\mid 2^{14}-1$; $\gcd(25, 2^{24}-1)\neq 1$ as $5\mid 15=2^4-1\mid 2^{24}-1$. But $k=7$ indeed works as $2^{34}-1\equiv 3 \pmod{5}$ and $2^{34}-1\equiv 1\pmod{7}$, so we get that $\gcd(35, 2^{34}-1)=1$, as desired. $\blacksquare$

Sammy27 wrote: Eka01 wrote: jelena_ivanchic wrote: $n=4$ works Except it doesn't. The lowest $n$ that works is $34$. Except it is not the lowest! I claim that $\boxed{n_{\text{min}}=9}$. Clearly $n=5k-1$ for some integer $k$ and by Euclid's algorithm, we have $$\gcd(2^n+n, 2^n-1)=\gcd(5k, 2^{5k-1}-1).$$It is easy to see that $k=1$ fails as $\gcd(5, 15)=5$. But $k=2$ indeed works as $\gcd(10, 511)=1$, and we are done. $\blacksquare$ I think you misread the question