Prove that there exists such a natural number sequence $a_1,a_2,\ldots$, such that $GCD(a_n,2^{a_n}+1)\rightarrow\infty$ when $n\rightarrow\infty$

Question

Homework exercise: prove that there exists such a natural number sequence $a_1,a_2,\ldots$, such that $GCD(a_n,2^{a_n}+1)\rightarrow\infty$ when $n\rightarrow\infty$. First of all I tried to just find any such sequence that works for at least the first few terms and quickly came up with $a_n=3^n$. This seems to work up until $n=19$, the limit of WolframAlpha. The $GCD(3^n,2^{3^n}+1)$ seems to be $3^n$. I am not sure why this is the case, but since it seems to hold for the first 19 terms, I am conjecturing that it holds for all $n$. Proving (or disproving) this claim didn't prove to be easy. I tried applying Euler's theorem: $$\phi(3^n)=3^n-3^{n-1}=2\cdot3^{n-1}$$ $$2^{3^n}+1\equiv2^{3^{n-1}+2\cdot3^{n-1}}+1\equiv2^{3^{n-1}}+1 \ (\textrm{mod}\ 3^n)$$ but it got me nowhere. This is the point where I ran out of ideas. I didn't manage to find another sequence which seems to answer the original question. Am I on the right path? Should the proof even be constructive? Please help. Thank you.