Coprime, infinitely

Since $a_n = (2^n+1)(3^n+1),$ if $k$ is coprime to all $a_n,$ then for any prime $p|k,$ we have that $2^n \equiv -1$ mod $p$ has no solution, and $3^n \equiv -1$ mod $p$ also has no solution.

It's not hard to check by hand or by computer that $p=23$ is the smallest prime for which this is true. (To see that it is true for $p=23,$ note that $2$ and $3$ are squares mod $23$ and $-1$ is not, by various applications of quadratic reciprocity .) So the smallest possible prime dividing $k$ is $23,$ and hence the smallest $k$ is $\fbox{23}.$

Obiviously,the smallest one must be a prime (if it exists). And $k≠2,3$ ,since $a_{1}=12$ .

Let $r\equiv n(mod (p-1)),0\le r\le p-2$ ,here $p\ge 5$ is prime.By Fermat's little theorem, $2^{p-1}\equiv 1(modp),3^{p-1}\equiv 1(modp), 6^{p-1}\equiv 1(modp)$ .Thus,If $p|(2^{n}+3^{n}+6^{n}+1)$ ,then $p|(2^{r}+3^{r}+6^{r}+1)$ .

That is equivalent to: if $p\nmid (2^{r}+3^{r}+6^{r}+1)$ ,then $p\nmid (2^{n}+3^{n}+6^{n}+1)$ .

Besides, $p|(2^{r}+3^{r}+6^{r}+1)$ $\Rightarrow$ $p|6^{p-1-r}(2^{r}+3^{r}+6^{r}+1)$ $\Rightarrow$ $p|(3^{p-1-r}\cdot2^{p-1}+2^{p-1-r}\cdot 3^{p-1}+6^{p-1}+6^{p-1-r})$ $\Rightarrow$ $p|(3^{p-1-r}+2^{p-1-r}+1+6^{p-1-r})$ ,which means that we only need to check the case when $r=1,2,...,\frac{p-1}{2}$ .

When p=5, $p|(2^{2}+3^{2}+6^{2}+1)$ ; when p=7, $p|(2^{3}+3^{3}+6^{3}+1)$ ; when p=13,17,19, $p|(2^{\frac{p-1}{2}}+3^{\frac{p-1}{2}}+6^{\frac{p-1}{2}}+1)$ ; when p=23,it is not hard to check that $23\nmid(2^{j}+3^{j}+6^{j}+1)(j=0,1,...,11)$ ,while a wiser way is stated by sir Patrick Corn.

So the answer is $\boxed{23}$ .