$\forall a\ge 2, \exists n\ge 1$ such that $2n+1\mid a+n!$ Let $a\ge 2$ be an integer. Prove that $\exists n\ge 1$ such that $$2n+1\mid a+n! \text{ or }a-n!$$
I think we'll construct a solution for $n$ as a function of $a$. But I have no idea what that function looks like. I just took care of some trivial cases.
First if $a$ is a factorial number i.e. $a=k!$ then set $n=k$
If $a$ is of the form $k!+2k+1$ then set $n=k$ and observe that $$a-n!=2k+1$$
Note that if $a\equiv 1$ or $2$ $\pmod 3$ then set $n=1$,so we only have to deal with multiples of $3$ now .

As you've already noted, $n = 1$ works with either $a \equiv 1 \pmod{3}$ (since $3 \mid a - 1$) or $a \equiv 2 \pmod{3}$ (since $3 \mid a + 1$). Also, as aschepler's question comment indicates, $n = 4$ works where $a$ has just one factor of $3$. This is because with $a = 3i$, then if $i \equiv 1 \pmod{3}$, we get $a + 4! = 3(i + 8) \equiv 0 \pmod{9}$, while if $i \equiv 2 \pmod{3}$, then $a - 4! = 3(i - 8) \equiv 0 \pmod{9}$.
This just leaves where $a$ is an integral multiple of $9$. As Dan's question comment indicates, $n = 20$ works for $a = 9$. Consider next if $a$ has any other odd factors, say $j \gt 1$. If so, then $2n + 1 = 9j \; \to \; n = \frac{9j - 1}{2}$ works since $3(3j) \mid a$, with $3 \neq 3j$, plus $3 \lt n$ and $3j \lt n$, so $3(3j) \mid n!$, which means $2n + 1 \mid a + n!$ (as well as $2n + 1 \mid a - n!$).
The final case to consider is with $a = 9(2^k)$ for $k \ge 1$. Then for $k = 1$ let $b = a + 1$, and for $k \ge 2$ let $b = a - 1$. Then $b \equiv 3 \pmod{4}$, so there's at least one prime $p \equiv 3 \pmod{4}$ where $p \mid b$. Let $p = 2n + 1 \; \to \; n = \frac{p - 1}{2}$. Then as shown in If $p\equiv 3\pmod{4}$ is a prime, then $\frac{p-1}{2}! \equiv \pm1 \pmod p$, we get that $n! \equiv \pm 1 \pmod{p}$. Thus, since $a \equiv \pm 1 \pmod{p}$, we have that either $2n + 1 \mid a + n!$ or $2n + 1 \mid a - n!$.
This concludes the proof since all cases for $a$ have been handled.
