Glancing at this problem, does the solution involve the fact that $ab+1$ is prime if $a$ and $b$ are prime?

Solution. Let $a_1,a_2,\ldots ,a_k$ be all the distinct residues modulo $p$ of elements in $S$ and $p\nmid a_i$ for all $i = 1,2,\ldots, k$, where $p$ is a prime. If $a_ia_j + 1\equiv a_ia_l + 1\pmod p$ for some $i,j,l$ and $j\neq l$, then $a_i(a_j - a_l) \equiv 0 \pmod p$. But $p\nmid a_i$, so $p\mid a_j - a_l$ which is false. This gives us that $a_ia_1 + 1, a_ia_2 + 1, \ldots , a_ia_k+1$ are all distinct residues modulo $p$. Also note that as $a_1,a_2,\ldots, a_k$ are the residues modulo $p$ of the elements of $S$, the residue $a_ia_j + 1 \pmod p$ also is in $\{a_1,a_2,\ldots ,a_k\}$. This gives us $\{a_ia_1 + 1,a_ia_2 + 1,\ldots ,a_ia_k + 1\} \equiv \{a_1,a_2,\ldots ,a_k\} \pmod p$ for any $i = 1,2,\ldots ,k$. Summing up both the sets modulo $p$ gives us \[a_i(a_1+a_2+\ldots +a_k) + k \equiv (a_1+a_2+\ldots +a_k)\pmod p \implies (a_i - 1)(a_1+a_2+\ldots + a_k) \equiv -k \pmod p \text{ for any i} = 1,2,\ldots ,k.\]If $p\mid a_1+a_2+\ldots + a_k$, then $p\mid -k$, so $k\geq p$ but as none of $a_i$'s are divisible by $p$, we get a contradiction. Therefore $p\nmid a_1+a_2+\ldots +a_k$, so \[a_i - 1 \equiv \frac{-k}{a_1+a_2+\ldots + a_k} \pmod p \text{ for any i} = 1,2,\ldots ,k.\]If $k>1$, then \[a_1 - 1 \equiv \frac{-k}{a_1+a_2+\ldots + a_k} \equiv a_2 - 1\pmod p\]which is false as $a_1,a_2$ are distinct residues modulo $p$. Therefore we have, $k = 1$. This means that if $p\nmid $ any element of $S$, then the number of possible residues of $S$ modulo $p$ is exactly one. Now as $S$ is non-empty, say $a\in S$. We claim that all primes greater than $a^2 - a + 1$ divide some element in $S$. Suppose there is a prime $p$ greater than $a^2 - a + 1$ which does not divide any element of $S$. We proved that then the number of possible residues of $S$ modulo $p$ is exactly one which is $a\pmod p$. Therefore $a^2 + 1 \equiv a \pmod p$, so $p\mid a^2 - a+1$ or $p\leq |a^2 - a + 1|$, but as $a^2 - a + 1 = \left(a - \frac{1}{2}\right)^2 + \frac{3}{4} \ge 0$ and as $p>a^2 - a + 1$, we get that this is false. Therefore we get that all primes greater than $a^2 - a + 1$ will divide at least one element of $S$. Further, as $a^2 - a + 1$ is finite, only finite primes exist which do not divide any element of $S$ and we are done. $~\blacksquare$

Fix an element $s\in S$. Any prime $p\nmid s^2-s+1$ works. Assume not. Let $\{x_1,x_2,\hdots,x_n\}$ are all different residues of $S$ in $\pmod p$. Then for any $a\in\{x_1,\hdots,x_n\}$, we have $\{ax_1+1,ax_2+1,\hdots,ax_n+1\}$ are $n$ different residues of $S$. They must be the same set thus $$a(x_1+x_2+\hdots+x_n)+n\equiv (x_1+x_2+\hdots+x_n)\pmod p$$Let $T=x_1+\hdots+x_n$. Clearly $T\not\equiv 0\pmod p$ as otherwise $n=p$, which means all residues are in $S$. Thus $(a-1)\equiv\tfrac{-n}{T}\pmod p$ for any $a\in\{x_1,\hdots,x_n\}$. This forces $n=1$. So if $x_1=s$, then $s^2+1\in S\implies s^2+1\equiv s\pmod p$. This means $p\mid s^2-s+1$, contradiction.

The result follows from the following statement. If $S$ is a set of residues modulo a prime $p$ such that $S$ contains $SS + 1$ and does not contain $0$, then $S$ is a singleton. A set of integers clearly cannot be constant modulo an infinity of primes. Proof. The number of elements of $SS$ is at least $|S|$ (we are now in the multiplicative group of nonzero residues) and equality holds only if $S$ is a coset of a subgroup. This means that for $k = |S|$ we have $k \mid p - 1$ and the elements of $S$ are the $k$ solutions of an equation $a^k = c$. Any element of $SS$ satisfies $z^k = c^2$. As $z + 1$ is an element of $S$, we also know that $(z + 1)^k = c$. So the polynomials $z^k - c^2$ and $(z + 1)^k - c$ have the same $k$ roots. This means that they must be equal as formal polynomials. However, if $k > 1$, then the linear term in one has coefficient $0$ and in the other $k$.

My sketch: By Dirichlet, pair up a.b=-1 (mod p) so the number of remainder of S mod p has an upper bound m<=p-1/2. Thus by maximal arguement and primitive root, we reduce to consider modulo p-1, maxsum < 2p-4. By |A+A|>=2|A|-1 and Dirichlet, we reduce to consider 2 case. If |A+A|=2|A|-1 thus arithmetic progression so sum up all remainder have contradiction. If |A+A|=2|A|, prove that it only happen when |A|<=4 thus by case work and choose p large we have q.e.d

Pick any two distinct elements $a,b$ in $S$ and choose any prime $p$ so that $p$ does not divide $a,b,a-b$; we'll prove that $S$ has a number divisible by $p$. Since only finitely many primes can not be chosen, this will imply the result. From now on, reduce $S$ modulo $p$. For contradiction, assume $0\not\in S$. Lemma: If $x,y\in S$, then $(y-1)/x\in S$.

Now $a,b\in S$, so by our lemma, $(b-1)/a\in S$, so $\left(\tfrac{b-1}{a}-1\right)/b=(b-a-1)/ab\in S$. But that means $\tfrac{b-a-1}{ab}\cdot a+1=\tfrac{2b-a-1}{b}\in S$, and so $\tfrac{2b-a-1}{b}\cdot b+1=2b-a\in S$. Using the same argument on $(b,2b-a)$, we see that $2(2b-a)-b=3b-2a\in S$, and similarly $2(3b-2a)-(2b-a)=4b-3a\in S$, and in general $b+n(b-a)\in S$ for integer $n$. But $p\not | b-a$, so by choosing $n\equiv -b/(b-a)\pmod{p}$, we get a contradiction to $0\not\in S$. This completes our proof. $\blacksquare$

$$\textbf{VERY CUTE PROBLEM :D}$$ Let $a$ be a random element of $S$. We consider only those elements of $S$ that are generated by $a$ (formally, the elements generated by $a$ satisfy the following: $a$ is generated by itself, $a\cdot a+1=a^2+1$ is generated by $a$, then if $u$ and $v$ is generated by $a$, so is $uv+1$). Call their set $S'$. Clearly $S'$ is included in $S$ and if $u,v\in S'$, then $uv+1\in S'$. It suffices to prove that there are finitely many primes not dividing any element of $S'$. We prove that if $p$ is a prime such that $p>2a^2$, then $p|u$ for some $u\in S'$. Let $T=\{u(\mod~p)~:~u\in S'\}$. Suppose $0\not \in T$. If $a^2+1\equiv a(\mod~p)$, then $p|a^2-a+1$ so $p<|a^2-a+1|$, false. So $T$ must have at least $2$ elements. Let $T=\{a_1,a_2,\cdots ,a_m\}$ where $2\le m\le p-1$, since $0\not \in T$. Note that $a_iT+1$ is contained in $T$ by the definition of $T$. Moreover, since $a_i\not =0$, $|a_iT+1|=|T|$. Therefore, $a_iT+1=T$, for all $i=\overline{1,m}$. This implies that $\sum_{j=1}^m(a_ia_i+1)\equiv \sum_{j=1}^ma_j (\mod~p)$, so $a_is+m\equiv s(\mod~p)$, where $s=\sum_{j=1}^ma_j$. If $s\equiv 0(\mod~p)$, we also get $m\equiv 0(\mod~p)$, impossible, since $2\le m\le p-1$. Therefore $s\not \equiv 0(\mod~p)$ so it has an inverse modulo $p$. But then for all $i$ we have $a_i\equiv 1-ms^{-1}(\mod~p)$, which means all elements of $T$ are equal modulo $p$ i.e. they are equal (since all are residues modulo $p$). This is however a contradiction, since it implies $m=|T|=1$, while we already got that $m\ge 2$! All these being said, we must have $0\in T$, hence the conclusion follows.

Easy for P5? pieater314159 wrote: Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $a$ and $b$ in $S$, the number $ab+1$ is also in $S$. Show that the set of primes that do not divide any element of $S$ is finite. Solution. We generalise the result and prove the following claim : Claim. Let $p$ be a prime which doesn't divide any element of $S.$ Then it follows that $p\mid \min\{S\}^2-\min\{S\}+1.$ Proof. Let $R=\{r_1,r_2,r_3,\ldots,r_k\}$ be the set obtained after reducing $S$ modulo $p,$ here $r_i$'s are distinct modulo $p.$ For now, assume $k\ge 2.$ Since $p$ doesn't divide any element of $S,$ so $k\le p-1$. Consider the set $R'=\{r_1^2+1,r_1r_2+1,r_1r_2+1,\ldots,r_1r_k+1\},$ note that all the elements are distinct modulo $p,$ also by definition of $R,$ we must have $R'\subseteq R$ which forces $R=R'.$ Now adding all elements of $R$ we obtain $s=r_1+r_2+\cdots+r_k$ and adding all elements of $R'$ we get $k+r_1s,$ therefore \[s\equiv k+r_1s\pmod{p}\]We cannot have $p\mid s$ as $k\le p-1.$ Now, we can similarly obtain that $s\equiv k+r_is\pmod{p}$ holds for all $i=1,2,3,\ldots,k,$ which would imply $r_i$'s are same modulo $p$. Contradiction! Thus the only possibility is that $k=1,$ but then we get $r_1\equiv r_1^2+1\pmod{p}\implies p\mid r_1^2-r_1+1.$ Since $\min\{S\}^2-\min\{S\}+1\ne 0,$ hence the claim. And we are done. $~\blacksquare$

pieater314159 wrote: Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $a$ and $b$ in $S$, the number $ab+1$ is also in $S$. Show that the set of primes that do not divide any element of $S$ is finite. Proposed by Carl Schildkraut Let $a$ be any element of $S$ We will show that a prime $p$ which does not divide $a^2-a+1$ must divide some element of $S$ and hence proof will be over. Let $\phi :\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}=\mathbb{Z}_p$ be the canonical homomorphism (basically takes any $n$ to $n$ (mod $p$) ) Let $\phi(a)=a_1$ and $\phi[S]=R$, if $0\in R$ then we are done so assume $0\notin R$ Let $R=\{a_1,a_2,\cdots,a_t\}$ as $p$ does not divide $a^2-a+1$ and $0\notin R$ we get that $1<t<p$ (Edit : I guess the $t>1$ requires a bit clarification, we have $a\in R$ and $a^2+1\in R$ and as $p$ does not divide $a^2-a+1$ , these two are unequal) Note that the elements $a_1a_i+1,a_2a_i+1,\cdots,a_ta_i+1$ are all different for a fixed $i$ , but by given condition they all lie in $R$ and hence they are just an permutation of $R$ This in turn gives that the sets $\{a_1a_i,a_2a_i,\cdots,a_ta_i\}$ are same for all $i$, now let $g_i=\frac{a_i}{a_1}$ then dividing all these sets by $a_1^2$ we get that. The sets $\{g_i,g_2g_i,g_3g_i,\cdots,g_tg_i\}$ are all same and in particular they are all same as $G=\{1,g_2,g_3,\cdots,g_t\}$ This gives us that $G$ is a group under multiplication in the ring $\mathbb{Z}_p$ and hence a subgroup of $\mathbb{Z}_{p}^{\times}$ As $G$ is a subgroup of a cyclic group it itself must be cyclic and hence it must be of form $\{1,g,g^2,\cdots,g^{t-1}\}$ Again viewing in $\mathbb{Z}_p$ we have $\displaystyle\Sigma_{g\in G} g=1+g+g^2+...+g^{t-1}= \frac{g^t-1}{g-1}=0$ (Here we used that $t>1\implies g\neq 1$) Multiplying by $a_1$ gives $\Sigma_{i=1}^t a_i=0$ Remember that $\{a_1,a_2,a_3,\cdots,a_t\}$ and $\{a_1^2+1,a_1a_2+1,a_1a_3+1,\cdots,a_1a_t+1\}$ are permutations of each other. Summing both of them we get $0=t (mod p) \implies p|t$ but this contradicts $1<t<p$. Hence proved.

I may have overcomplicated this problem, but I haven't seen a similar solution so I decided to post it. We will use the fact that every polynomial of degree $\leqslant n$ has at most $n$ zeroes in $\mathbb Z_p$, and the fact that there exists a primitive root modulo $p$ for odd primes $p$. Let $a \in S$, and let $p>a^2+1$ be a prime. We'll prove that $p \mid x$ for some $x \in S$. Suppose that this isn't true. Let $\{x_1,\ldots,x_k\}$ be all elements of $\mathbb Z_p$ which are represented in $S$. We have $p>k\geqslant 2$ since $a$ and $a^2+1$ aren't equal in $\mathbb Z_p$. Now, we know that for all $i \in \{1,\ldots, k\}$, $x_iS+1=S$, which implies $x_iS=x_jS$ for all $i, j \in \{1,\ldots, k\}$. Let $g$ be a primitive root modulo $p$, and let $x_i=g^{a_i}$, and suppose $0\leqslant a_1< a_2< \ldots <a_k<p-1$. Now we know that as $i $ runs over $ \{1,\ldots, k\}$, the sets $$\{a_i+a_1,a_i+a_2, \ldots, a_i+a_k\}$$are all equal modulo $p-1$. This means that for every $j \in \{2, \ldots,k-1\}$, there exists a unique index $m_j$ such that $a_1+a_k\equiv a_j+a_{m_j} \pmod{p-1}$. However, since $|a_1+a_k-a_j-a_{m_j}|<p-1$, equality holds. Now, because of $(a_i)$ being increasing, we have the following equalities: $$a_1+a_k=a_2+a_{k-1}=\ldots=a_{k}+a_1.$$Similarly, for $j \in \{2,\ldots, k\}$, there exists a unique index $m_j$ such that $2a_i \equiv a_j+a_{m_j} \pmod{p-1}$, and since $2a_1<a_j+a_{m_j}<2a_1+2(p-1)$, we have $2a_1=a_j+a_{m_j}-(p-1)$. Due to $(a_i)$ being increasing, we have the following equalities: $$2a_1=a_2+a_k-(p-1)=a_3+a_{k-1}-(p-1)=\ldots=a_k+a_2-(p-1).$$Substracting equalities $a_j+a_{k+1-j}=a_{j+1}+a_{k-j}$ and $a_{j+1}+a_{k+1-j}=a_{j+2}+a_{k-j}$, we get $a_{j+1}-a_j=a_{j+2}-a_{j+1}$ for $0<j<k-1$, which implies that $(a_i)$ form an arithmetic progression, with difference $d=\dfrac{p-1}{k}$. In particular, $k \mid p-1$. Let $g^{a_1}=u$. Now, since $a_j=a_1+(j-1)\frac{p-1}{k}$ we can write $S=uQ$, where $Q$ is the set of all elements of $\mathbb Z_p$ whose order divides $k$, i.e. all $x \in \mathbb Z_p$ which satisfy $p \mid x^k-1$. Now, if $ux \in uQ$, then $u\cdot(ux)+1=u^2x+1 \in uQ$, which implies $ux+u^{-1} \in Q$. This implies that the polynomials $(ux+u^{-1})^k-1$ and $(ux)^k-u^k$ have $k$ common zeroes (the set of common zeroes is $Q$), so their difference, which is of degree $\leqslant k-1$, is a zero polynomial in $\mathbb Z_p$. However, comparing coefficients alongside $x^{k-1}$, we conclude that $p \mid ku^{k-2}$, which is a contradiction since $u$ is not divisible by $p$ and $k<p$.

Let $a$ denote the minimum element of $S$. We claim that any prime $p$ which doesnt divide any element of $S$ divides $a^2-a+1$, which finishes. Work in $\mathbb F_p.$ Let $X=$$\{x_1,x_2,\dots,x_k\}$ denote the distinct residues of the elements of $S$ modulo $p$. By assumption, $x_i \neq 0$. Now pick any $x\in X$ and note that the set $xX+1$ must be the same as $X$ by the condition of the problem. This gives: $$x\left (\sum_{i=1}^{k} x_i\right) + k =\sum_{i=1}^{k} x_i$$$$ \implies x = 1- \frac k {\sum_{i=1}^{k} x_i}$$ Since $x$ was arbitrary, $k=1$. So $a^2+1\equiv a\pmod p$, so $p\mid a^2-a+1$, as desired. $\square$

Solution with VulcanForge and awang11. The key claim is that $p$ divides some element of $S$ if there are distinct $a,b\in S$ modulo $p$. To see this, consider the functions $f:x\mapsto ax+1$ and $g:x\mapsto bx+1$ modulo $S$. Clearly they are both invertible or we are done, so $f(S)=g(S)=S$. Let $K$ denote the sum of the distinct elements of $S$ modulo $p$. Then we get \[aK+|S|=bK+|S|=K\]modulo $p$. Since $a\ne b$ modulo $p$, this implies $K=0$, so $|S|$ is congruent to $0$ modulo $p$. As $|S|$ cannot contain $0$ elements modulo $p$, this implies the desired. Now, we are done because $p$ can only not divide some element of $S$ if for a fixed $a\in S$ we have $p\mid a^2+1-a$, which is finite.

Suppose that there are infinitely such primes $p$. Work in $\mathbb F_p$ and let $S=\{a_1,a_2,...,a_n\}$. Claim: If $a \in S$, then $-a$ does not belongs to $S$. Proof: Suppose that there is an $a \in S$ such that $-a \in S$. Hence observe that since the $a_i$ are all distinct, $a.a_i+1$ are all distinct for all $1 \leq i \leq n$. $$\implies \{a_1,a_2,...,a_n\} = \{a.a_1+1,a.a_2+1,...,a.a_n+1\} \quad (\star)$$The same is valid for $-a$, so $x,-x$ for all $x \in S$. Thus $\sum_{i=1}^n a_i=0$. From $(\star)$, $\sum_{i=1}^n a_i = a(\sum_{i=1}^n a_i) +n= n$, so $n=0$ and then $p|n$, so $n=0$ since $n$ is bounded and $p$ can be large enough, but $n$ clearly cannot be $0$. This proves the claim. $\square$ From the claim, $x \mapsto x^2+1$ is a bijection under $S$ $\pmod{p}$. Hence, $\{a_1,a_2,...,a_n\}=\{a_1^2+1,a_2^2+1,...,a_n^2+1\}$ $$\implies (\sum_{i=1}^n a_i^2) +n = \sum_{i=1}^n a_i = a_j(\sum_{i=1}^n a_i)+n$$for all $1 \leq j \leq n$, so $ \sum_{i=1}^n a_i^2= (\sum_{i=1}^n a_i)a_j$. Summing everything, $(\sum_{i=1}^n a_i)^2= n \sum_{i=1}^n a_i^2$, so $p|(\sum_{i=1}^n a_i)^2-n \sum_{i=1}^n a_i^2$, but since $(\sum_{i=1}^n a_i)^2-n \sum_{i=1}^n a_i^2$ is bounded and $p$ can be large enough, we must have $(\sum_{i=1}^n a_i)^2-n \sum_{i=1}^n a_i^2=0$ (not just in $\mathbb F_p$), but this implies that all $a_i$ must be equal, which is clearly a contradiction, so we are done. $\blacksquare$

We work in $\mathbb F_p$. Let $p$ be a prime such that $p\not|m,\forall m\in S$. Claim. $a,b\in S\implies a+n(a-b)\in S,\forall n\in\mathbb N_0$ ($a$ and $b$ are not necessarily distinct). Proof. We induct on $n$. Clearly, $n=0$ works and now we assume it's true for all $n<M$. Note that as $|S|>0$, define $x_n:=bx_{n-1}+1;a_1=a$ for all $n\geq 2\implies x_i\in S$ and thus, $a,b\not\equiv_p 0,1$. Hence, $$x_{p-1}=ba^{p-2}+\sum_{i=0}^{p-3} a^i\equiv_p \frac{b}{a}-\frac{1}{a}$$Now define, $y_n:=x_{p-1}y_{n-1}+1;y_1=b$ for all $n\geq 2\implies y_i\in S$. Thus, $$y_{p-1}=x_{p-1}b^{p-2}+\sum_{i=0}^{p-3}b^i\equiv_p \frac{x_{p-1}}{b}-\frac 1 b\equiv_p\frac{b-a-1}{ab}\in S\overset{sym}{\implies}\frac{a-b-1}{ab}\in S$$Also, if $\ell\in S\implies \ell b+1\in S\implies \ell ab+a+1\in S$ and thus, taking $\ell=(a-b-1)/ab$, we get $a+(a-b)\in S$. Thus, we may assume $M>2$. Now, by our inductive hypothesis, we know that $$(a+(M-1)(a-b), a+(M-2)(a-b))\in S^2\implies 2[a+(M-1)(a-b)]-[a+(M-2)(a-b)]=a+M(a-b)\in S$$which completes the proof of our claim. If $a\not\equiv_p b$, then $\exists w\in\mathbb N$ such that $a+w(a-b)\equiv_p 0$ which is absurd. Thus, $p$ must be a prime divisor of $a-b$ if $a,b\in S$. Also note that $a\in S\implies a^2+1\in S\implies p|a^2-a+1$ and thus, number of such primes $p$ is finite as $x^2-x+1=0$ has no solution in $\mathbb R$.

Suppose $k$ is an element of $S$. Lemma: Any prime $p\nmid k^2-k+1$ is a prime divisor of some element in $S$, which clearly finishes. Proof: Assume not. Call the distinct residues $\pmod p$ in $S$, $r_1,r_2,r_3\ldots r_n$, with $n<p$. Since for any $1\le i\le r$, \[r_ir_1+1, r_ir_2+1, r_ir_3+1, \ldots, r_ir_n+1\]have distinct residues $\pmod p$, their residues are some permutation of $r_1,r_2,r_3\ldots r_n$. Now, we can add them up \[r_i(r_1+r_2+\ldots+r_n)+n\equiv r_1+r_2+\ldots+r_n\pmod p\]. Let $r_1+r_2+\ldots+r_n=x$. So \[r_i\cdot x -x=x(r_i-1) \equiv -n\pmod p\]. Claim: $p\nmid x$. Proof: If not, then $n\equiv0\pmod p$, which implies $n=p$, a contradiction. Since $x$ is relatively prime to $p$, if there are two distinct $r_i$, then $x(r_i-1)$ will have two different residues. So there must be only one residue $r_i$. Now, we have \[r_1^2+1\equiv r_i\pmod p\implies p|r_i^2-r_i+1.\]

Does this work? Claim: Let $p$ be a prime and $T$ a set of nonzero residues mod $p$ with at least $2$ elements. Then there exist not necessarily distinct $s,t\in T$ such that $st+1\not\in S$. Proof: We will work entirely mod $p$. Let $T = \{a_1,a_2,\dots ,a_n\}$ with $n\ge 2$ and assume the contrary (there do not exist such $s$ and $t$). Since the elements of $T$ are nonzero we must have $a_ia_j+1\neq a_ia_k+1$ for any distinct $1\le i,j,k\le n$. Hence, for any $i$, $a_1a_i+1, a_2a_i+1, \dots , a_na_i+1$ must be a permutation of $a_1,a_2,\dots ,a_n$. In particular, $a_1 + a_2 + \dots + a_n = a_1a_i + 1 + a_2a_i + 1 + \dots + a_na_i + 1 = a_i(a_1 + a_2 + \dots + a_n) + n$. If $a_1+a_2+\dots +a_n = 0$ we obtain $n=0$, implying $n=p$ since $n>2$ which means $0\in T$, a contradiction. Otherwise, for $i\neq j$ we have $a_1 + a_2 + \dots + a_n = a_i(a_1 + a_2 + \dots + a_n) + n\neq a_j(a_1 + a_2 + \dots + a_n) + n = a_1 + a_2 + \dots + a_n$, also a contradiction and the lemma is proved. Now, let $q$ be a prime such that the elements of $S$ take at least $2$ distinct residues mod $q$. We aim to show that some element of $S$ is a multiple of $q$. Indeed, if one of the residues is $0$, we are already done. Otherwise, by the lemma we can continue adding residues that must appear in $S$, one at a time, unless one of our residues is $0$. But once one of our residues is $0$, we are done. Finally, it suffices to show that there are only finitely many primes $r$ such that the elements of $S$ are all equivalent mod $r$. Assume the contrary, then every one of the primes divides $s-t$ for any distinct $s,t\in S$, absurd and we are done.

Consider a prime $p$ not dividing any element of $S.$ Let $\{m_1, m_2, \dots m_n \}$ be the set of all residues of elements of $S \pmod{p},$ and let $T$ be their sum. For any $m_k \in \{m_1, m_2, \dots m_n \},$ we have that $\{m_1m_k+1, m_2m_k+1, \dots m_nm_k+1\}$ are $n$ distinct residues of $S.$ So then $$\{m_1m_k+1, m_2m_k+1, \dots m_nm_k+1\} = \{m_1, m_2, \dots m_n \}$$ thus $m_kT + n = T \implies m_k-1 \equiv \frac{-n}{T} \pmod{p},$ since if $T = 0$ that means $n = p.$ This forces $n=1,$ and so for any arbitrary element $s$ in $S,$ $s-1 \equiv -1/s \pmod{p} \implies s^2-s+1 \equiv 0 \pmod{p}.$ But there are only a finite number of primes dividing $s^2-s+1,$ contradiction.

Let $p$ be a prime not dividing any $x \in S$. Claim: All elements of $S$ leave the same residue modulo $p$. Proof: Let $r_1, \ldots , r_k$ be the $k$ distinct (clearly nonzero) residues left by elements of $S$ modulo $p$, where $k \in [1, p-1]$. Define set $A_i = \{r_ir_j + 1\}_{j = 1}^{k}$. Note that each $A_i$ has size $k$, is entirely contained in $S$, and no two elements leave the same residue: indeed, $p \mid r_a(r_b - r_c)$ is impossible for any $a, b, c$. Note that this means each $A_i$ is a complete residue set. That is, $A_i = \{r_1, \ldots , r_k\}$. Hence, summing both sets, we get\[(r_i - 1)(r_1 + \ldots + r_k) + k \equiv 0 \pmod p.\]First, check that if $r_1 + \ldots + r_k = 0 \pmod p$ then $k \equiv 0 \pmod p$, impossible given the range of $k$. Then, that means\[r_i \equiv 1 - k(r_1 + \ldots + r_k)^{-1} \pmod p\]is a fixed value across all $i$, so in fact all $r_i$ are the same. However, the assumption is also that they are all distinct, so $k = 1$, as desired. Alas, this also means $r_i \equiv 1 - r_i^{-1} \pmod p \iff p \mid r_i^2 - r_i + 1$ for all $r_i$. However, if we just fix $r_i$ as any element in $S$, this limits the number of values $p$ can possibly be to the number of divisors of a positive integer, which is clearly finite, so we win.

Consider any fixed prime $p$ and let $S_p=\{a_1,\ldots,a_k\}$ be the distinct remainders upon dividing all elements in $S$ by $p$. I claim that either $k=1$ or $k=p$. Indeed, note that if $0 \in S_p$, then $1 \in S_p$, so then if $n \in S_p$ we have $n+1 \in S_p$ as well, so $S_p=\{0,\ldots,p-1\}$. Suppose $k \neq p$, so $0 \not \in S_p$ To prove this, pick some index $1 \leq i \leq k$. Then since $a_i \not \equiv 0 \pmod{p}$, all $a_ia_j+1$ are distinct modulo $p$ (ranging across $1 \leq j \leq k$), which yields $k$ residues. It follows that $$\{a_ia_1+1,\ldots,a_ia_k+1\} \equiv \{a_1,\ldots,a_k\} \pmod{p},$$so summing across all $k$, we have $$a_i(a_1+\cdots+a_k)+k \equiv a_1+\cdots+a_k \implies (a_i-1)(a_1+\cdots+a_k) \equiv -k \pmod{p}.$$As $k \not \equiv 0 \pmod{p}$ because that would imply $k=p$, it follows that $a_1+\cdots+a_k \not \equiv 0 \pmod{p}$ either, so $a_i-1$ is constant mod $p$ and thus $k=1$, as desired. Now, if $p \nmid n$ for all $n \in S$ for some prime $p$, we must have $|S_p|=1$ and thus $p \mid n^2-n+1$ for all $n$ in $S$. Clearly there are a finite number of $p$ that satisfy this (just take an arbitrary $n$), so we're done. $\blacksquare$

Take prime $p$ not dividing $w^2-w+1$ for some $w\in S$ - there are only finitely many that do not. Let $T=\{c_1,c_2,\ldots, c_k\}\subseteq \{0,1,2,\ldots, p-1\}$ be the set of remainders of $a\in S$ modulo $p$. Assume FTSOC that $k\neq 1$ but $0\not\in T$. By writing out $c_ic_j+1$ for $1\leq i\leq j\leq k$, we have $m^2$ numbers, each congruent to some $c_l$. If $m+1$ of $c_ic_j+1$ are congruent to some $c_l$, then by Pigeonhole Principle, there exists $x,y,z$ with $y\neq z$ such that $$c_xc_y+1\equiv c_l\equiv c_xc_z+1\pmod{p} \implies c_y\equiv c_z\pmod{p}\implies y=z$$because $c_x\not\equiv 0\pmod{p}$, a contradiction. Thus, each $c_l$ is congruent to exactly $m$ $c_ic_j+1$'s. By Pigeonhole Principle, choose $t$ such that $c_i^2+1\equiv c_t\pmod{p}$ for at most one $1\leq i\leq k$. Then there are $m-1\geq 1$ indices that form $m-1$ pairs, so we have $x,y,z$ with $y\neq z$ such that $c_xc_y+1\equiv c_t\equiv c_xc_z+1\pmod{p}$, a similar contradiction. Thus, $m=1$. Then $$c_1^2+1\equiv c_1\pmod{p}\implies p\mid c_1^2-c_1+1$$a contradiction, because $c_1\equiv w\pmod{p}$ since $w\in S$. Thus, $0\in T$ as needed.

Let $p > \min(S)^2-\min(S)+1$ be a prime and let $S_p = \{x \in [\![0, p-1]\!] \; | \; \exists y \in S, p \mid x-y\}$. Suppose $0 \not \in S_p$ and consider : $$f(x) = \sum_{a\in S_p} x^a.$$Since $b \mapsto ab+1 \pmod p$ forms an injective map from $S_p$ to $S_p$ where $a\in S_p$, it is also a bijective map and we deduce that $ef(e^a) = f(e)$ whenever $a \in S_p$ where $e^{p-1}+\ldots+1 =0$. Consequently for $a,b \in S$ : $$e^af(e^{ab}) = f(e^a)= \frac{f(e)}{e} = f(e^b) = e^bf(e^{ab}).$$Hence $a\equiv b \pmod p$ or $f(e^{ab})=0$. Lemma. Assume $f \in \mathbb{Q}[X]$ satisfies $f(e) = 0$ where $g(e) =e^{p-1}+\ldots+e+1 =0$, then $g = X^{p-1}+\ldots+X+1 \mid f$. Consider $\mathrm{gcd}(f,g) \in \mathbb{Q}[X]$, it has degree greater than $1$ and divides $g$ which is irreductible over $\mathbb{Q}[X]$ so it equals $g$. Hence $g \mid f$. Assume $f(e^{ab})=0$, then since $0\not \in S_p$ we get that $e^{ab}$ is a root of $\frac{f}{X}$ and that $g(e^{ab})=0$. Hence $g \mid \frac{f}{X}$, but this is absurd because $0\leq \deg(f/X) <p-1$. Consequently $p \mid a-b$ and with $a= \min(S)$ and $b = a^2+1 \pmod p$ we get $p \mid a^2-a+1$, which is an absurdity and concludes.

Let $m\in S$ be some random element from $S$. There are only finitely many prime divisors of $m^2-m+1$. We claim that if $p\nmid m^2-m+1$ then some element of $S$ is divisible by $p$. Suppose for contradiction that there is a prime that does not divide any element from $S$. Let $\{a_1,a_2,\ldots,a_k\}$ be the elements from $S$ each with different residues $\pmod{p}$ covering all residues in $S$. Let $x\in S$ be a random element in $S$. Then, $\{xa_1+1, xa_2+1, \ldots, xa_k+1\}$ also consist of different residues $\pmod{p}$, and since they cover all elements in $S$, we have \[xa_1+1+xa_2+1+\cdots+xa_k+1 \equiv a_1+a_2+\cdots+a_k \pmod{p}\]\[\Longrightarrow (1-x)(a_1+a_2+\cdots+a_k) \equiv k \pmod{p}\]But this holds for any element $x\in S$. This means that $S\pmod{p}$ is constant. So, $m\equiv m^2+1\pmod{p}$, which means that $p\mid m^2-m+1$, which is impossible. $\blacksquare$

Amazing problem!, though kinda easy for P5. Take any $a \in S$ and we'll prove that for every prime $p > a^2 - a + 1$, there exists a positive integer $b \in S$ that is divisible by $p$. Let $f(x) = x^2 + 1$. Then consider the sequence $a, f(a), f^2(a), \dots$. By pigeonhole principle, there exists $f^i(a) \equiv f^j(a)$, so we may pick the largest $k$ such that $a, f(a), f^2(a), \dots, f^{k-1}(a)$ leave different remainders divided by $p$. Note that $p \nmid a^2 - a + 1 = f(a) - a$, so we may assume $k \ge 2$. It's clear that $k \le p$. Let $a_i$ be the remainder of $f^i(a)$ divided by $p$. Claim: We can generate a remainder $r$ different from $a_0, a_1, \dots, a_{k-1}$ from $a_0, a_1, \dots, a_{k-1}$ unless $k = p$. Proof. Assume the contrary, $k \neq p$ and $\{a_ia_0 + 1, a_ia_1 + 1, \dots, a_ia_{k-1} + 1\} \equiv \{a_0, a_1, \dots, a_{k-1}\} (p)$for all $0 \le i \le k-1$. Since $k \ge 2$, we can pick distinct $i, j$ from $\{0, 1, \dots, k-1\}$. Thus, we have $\{a_ia_0 + 1, a_ia_1 + 1, \dots, a_ia_{k-1} + 1\} \equiv \{a_ja_0 + 1, a_ja_1 + 1, \dots, a_ja_{k-1} + 1\} (p)$, so we get $p \mid (a_i - a_j)(a_0 + a_1 + \dots + a_{k-1})$. Hence, $p \mid a_0 + a_1 + \dots + a_{k-1}$. But, we have $\{a_ia_0 + 1, a_ia_1 + 1, \dots, a_ia_{k-1} + 1\} \equiv \{a_0, a_1, \dots, a_{k-1}\} (p)$. Combined with the fact that $p \mid a_0 + a_1 + \dots + a_{k-1}$, we see that $p \mid k$, a contradiction. $\blacksquare$ By claim, we can generate different remainder $r$ from $a_0, a_1, \dots, a_{k-1}$ until $k = p$, so at some point, we get a complete residue class modulo $p$, which means that there is a positive integer $b$ such that $p \mid b$, as wanted. $\blacksquare$

Gegagedigeda! Gegagedigedagedago! Finite set of primes? WHAT! Help me! Like = Help DING! Create nugget set $T \subset S$! $T$ has all remainders on divide by Gegagedigedageda$p$, excactly once. Fix $n \in S$, map $u \mapsto nu+1 \pmod{p}$ is natural bigegagedijective! Conclusion: \[ \sum_{_{nugge}t \in T} { }_{nugge}t \equiv \sum_{_{nugge}t \in T} n {}_{nugge}t + 1 \pmod{p} \implies \forall n \in S (n-1)\sum_{_{nugge}t \in T} {}_{nugge}t \equiv -|T| \pmod{p}! \]Fake nugget for many gegagedesidue! Follow that: exists only one gegagedesidue in $S$ and $r^2 + 1 \equiv r \pmod{p}$! But only finite many prime divide $r^2 - r + 1$... gegagedigedagedago completion!