We can easily prove by induction that $a_n=2\cdot n!+1$ for all $n\geqslant 0$. Let $m$ be a positive integer that $gcd(m,a_n)=1$ for all $n\geqslant 0$. Note that all of $a_n$s are odd, and so $m=2^t$ works for all $t\geqslant 0$. Since $a_0=3$, $3\nmid m$. Suppose that $m$ has a prime divisor $p\geqslant 5$. Consider $a_{p-3}=2\cdot (p-3)!+1$. We get $$(p-3)! \cdot (-2)(-1) \equiv -1\pmod{p} \implies p\mid a_{p-3}.$$So, the answer is $2^t$ for all nonnegative integer $t$.

Can someone explain to me how we prove by induction that $a_n=2n!+1$?

stamatelos wrote: Can someone explain to me how we prove by induction that $a_n=2n!+1$? The base case $n=0$ holds true, as $a_0=3=2\cdot 0!+1$. For the inductive step, suppose the statement holds true for some $n \in\mathbb{N}_0$. Then, $a_{n+1}=a_n+n(a_n-1)=(2n!+1)+n(2n!)=2n!\cdot(n+1)+1=2(n+1)!+1$, as needed.

any other way to prove that has this form?I think thats was just guessing the form of the sequence cause i dont see any sense to think that from in the first place

stamatelos wrote: any other way to prove that has this form?I think thats was just guessing the form of the sequence cause i dont see any sense to think that from in the first place I suppose if you wanted to, you could manipulate it as $\frac{a_{n+1}-1}{2}=(n+1)\cdot \left(\frac{a_n-1}{2}\right)$, from which the conclusion follows; here there isn't anything like a characteristic polynomial you could use to solve the recursion, but guessing the form of the sequence isn't a difficult task anyways.

Rewrite the recurrence as $a_{n+1}=(n+1)a_n - n$, and dividing the both sides of the recurrence by $(n+1)!$ gives $\frac{a_{n+1}}{(n+1)!} = \frac{a_n}{n !} - \frac{n}{ (n+1)!}. $Then we can also $\frac{n}{(n+1)!} = \frac{1}{n!}- \frac{1}{(n+1)!}$, thus the given recurrence can be rewritten as $\frac{a_{n+1}-1}{(n+1)!}=\frac{a_n - 1}{n!}=\cdots = \frac{a_0-1}{0!} ,$ yielding $a_n=2n!+1\ (n=0,\ 1,\ \cdots).$

Set $a_n=b_n+1$ then the recurrence becomes $b_{n+1}=(n+1)b_n$ and now we prove by induction that $b_n=2 \cdot n!$ Clearly when $n=0$ its trivial, so let it work for $n=k$ now: $$b_{k+1}=(k+1)b_k=2(k+1)! \implies a_n=2 \cdot n!+1 \; \; \forall n \in \mathbb N_0$$Now note that for a prime $p>5$ we have $2 \cdot (p-3)! \equiv (p-1)! \equiv -1 \pmod p$ hence $p \mid a_{p-3}$ which means that $m$ doesnt have any prime factor up to $5$ and now since $\gcd(m,3)=1$ we have that $m$ doesnt have any prime factor up to $3$, hence $m$ its a power of $2$ which clearly fits, thus we are done