Well this seems to be really dumb problem. If $n$ is odd, the answer is obviously $3$. If it's not, we claim that it's $6$. Obviously all $p$ that don't divide $n$ are odd, so $6$ works. Suppose now that some other prime $q$ does the job. Then all sufficiently large primes $p_i \equiv 2 (mod 3)$ are such that $p_i \equiv - 1 (mod q)$. But that's obviously false as there is a large prime $p_j \equiv - 2 (mod q)$ and $p_j \equiv 2 (mod 3)$ due to Dirichlet and CRT, so $q | p_j+2$ and $q | p_j+1$, an obvious contradiction. Edit: Oh it's seems, as @below did, that we shall check $4$ and $9$ as well, but the proof is again by Dirichlet.

Proposed by me, though I agree it's not that much of a nice problem. Suppose the prime $q\geq 5$ is a possible common divisor -- then any $p>n$ with $p\equiv -1 \pmod 3$ must also obey $p\equiv -1 \pmod q$, i.e. $p\equiv -1 \pmod {3q}$. However, by Dirichlet's theorem there actually are infinitely many primes $p\equiv 2 \pmod {3q}$ (and these obey $p\equiv 2 \pmod 3$), contradiction! Similarly, if $4$ is a possible common divisor, then a large $p>n$, $p\equiv 5 \pmod {12}$, gives a contradiction; and if $9$ is a possible common divisor, then a large $p\equiv 2 \pmod 9$ gives a contradiction. Hence the gcd is at most $6$ and now it is clearly $6$ when $n$ is even (as all odd primes $p\equiv 2 \pmod 3$ satisfy $p\equiv 5 \pmod 6$) and $3$ when $n$ is odd (by taking $p=2$).

We claim the answer is $3$ when $n$ is odd and $6$ when $n$ is even. The fact that these work follow from $p+1 \equiv 3 \pmod{3}$ and that if $n$ is odd/even we can/cannot choose $p=2$ giving $p+1=3$ which is not divisible by $2$ and for $p>2$, $2 \vert p+1$. If $n$ is odd then choosing $p=2$ shows the answer can't be divisible by $2$. To complete the problem, it suffices to show: (i) The answer can't be divisible by $9$. (ii) The answer can't be divisible by any prime $q>3$. For (i), by Dirichlet there are infinitely many primes $p \equiv 2 \pmod{9}$ so choose one that doesn't divide $n$ then $9 \nmid p+1$. For (ii), similarly choose $p$ such that $p \nmid n$ and: $$ \begin{cases} p \equiv 2 \pmod{3} \\ p \equiv -2 \pmod{q} \end{cases} $$Then $q \nmid p+1$.

Same but badly written solution as above solutions, I'll share it anyways If $n$ is odd, it is evident that $n=3$. Assume otherwise. We know that $6|p+1$ for all $p$ satisfying the properties above. Hence, $n=6$ works. By Dirichlet's theorem, there are infinitely many primes such that $$p \equiv 1 \mod t$$By CRT we can make arbitray bigger prime $p$ satisfying these properties. Now, observe that $t \nmid p+1$.If $\gcd(t,2)=2, \gcd(t,3)=3$, we can make similiar primes but for $\mod 4t',9t'$.Note that wee can't make these such primes for $n=6$ since for all primes, $6|p+1$ Therefore $n=6,3$ are only answers $ \ \blacksquare$

For a positive integer $n$, let $k_n$ be the largest such number dividing all numbers of the form $p+1$, where $p\nmid n$ is a prime equivalent to $2$ modulo $3$. We claim that $k_n=3$ if $n$ is odd, and $k_n=6$ otherwise. We first define some notation: let $P$ be the set of all prime numbers equivalent to $2$ modulo $3$, and let $P_n$ be the subset of $P$ containing those primes that do not divide $n$. Suppose $n$ is odd. Clearly, we have $2\in P_n$, and hence $k_n \mid 3$. Since for every $p\in P_n$, we have $3\mid p+1$, and thus $k_n=3$. Suppose $n$ is even. In this case, $2 \notin P_n$, and thus for any $p \in P_n$, the number $p+1$ is even and divisible by $3$. Hence, $6\mid k_n$. We now need only show that $k_n$ cannot be any larger than $6$. Note that all sufficiently large primes equivalent to $2$ modulo $3$ are in $P_n$. By Dirichlet, there is always a $p\in P_n$ satisfying $p\equiv 1 \pmod{q}$, where $q\ge 5$ is a prime. Then, $q\nmid p+1$, so $q\nmid k_n$. We now show that $4 \nmid k_n$ and $9 \nmid k_n$. It suffices to pick a $p\in P_n$ satisfying $p\equiv 5\pmod{36}$, which must exist by Dirichlet, and clearly $4\nmid p+1$ and $9\nmid p+1$. Thus $k_n=6$ in this case, and we are done. $\blacksquare$