Solution.. I hope this is right...

actual solution: Let $p$ be prime. Let $Q$ be the set of all remainders of products of distinct elements of $P$ modulo $p$. Let $G$ be the largest subgroup of $\mathbb{Z}_p^{\ast}$ which is contained in $Q$ ($G$ exists because $P$ is infinite and so contains infinitely many things $a$ mod $p$ for some $a$ and thus $Q$ contains the group generated by $a$.) Suppose $G$ does not contain all nonzero residues. Suppose there are only finitely many primes whose residue mod $p$ is not in $G$. Let $b$ be the product of all of these primes modulo $p$. Suppose $b$ is not $0$ (if $b$ is $0$ then $p\in P$). Then by pigeonhole, $bG+1$ contains an element not in $G$. Take a set of primes in $P$, including all those with remainder mod $p$ not in $G$, whose product+1's remainder mod $p$ is not in $G$. Then by the definition of a subgroup, one of this number's prime factors is not in $G$ mod $p$ either, but is in $P$. This is a contradiction, so either $Q$ does contain all nonzero residues, in which case it contains $-1$ and so contains $0$, or there are infinitely many primes which are $b$ mod $p$ for some b not in $Q$. In this latter case, $P$ contains the group generated by $b$ and $Q$ modulo $p$, which is bigger than $Q$. This is again a contradiction, so we conclude that for all $p$, $p\in P$ and we are done.

Did you mean set M instead of set P? Does anyone have another solution?

raxu wrote: 3. Let $P$ be the set of all primes, and let $M$ be a non-empty subset of $P$. Suppose that for any non-empty subset ${p_1,p_2,...,p_k}$ of $M$, all prime factors of $p_1p_2...p_k+1$ are also in $M$. Prove that $M=P$. When you say "any non-empty subset $p_i$ of $M$ " every $p_i$ set have exactly one element?

@Konigsberg Sorry yeah, I used $P$ for what is called $M$ in the problem. The solution should still be correct though.

gurev wrote: actual solution: Let $p$ be prime. Let $Q$ be the set of all remainders of products of distinct elements of $P$ modulo $p$. Let $G$ be the largest subgroup of $\mathbb{Z}_p^{\ast}$ which is contained in $Q$ ($G$ exists because $P$ is infinite and so contains infinitely many things $a$ mod $p$ for some $a$ and thus $Q$ contains the group generated by $a$.) Suppose $G$ does not contain all nonzero residues. Suppose there are only finitely many primes whose residue mod $p$ is not in $G$. Let $b$ be the product of all of these primes modulo $p$. Suppose $b$ is not $0$ (if $b$ is $0$ then $p\in P$). Then by pigeonhole, $bG+1$ contains an element not in $G$. Take a set of primes in $P$, including all those with remainder mod $p$ not in $G$, whose product+1's remainder mod $p$ is not in $G$. Then by the definition of a subgroup, one of this number's prime factors is not in $G$ mod $p$ either, but is in $P$. This is a contradiction, so either $Q$ does contain all nonzero residues, in which case it contains $-1$ and so contains $0$, or there are infinitely many primes which are $b$ mod $p$ for some b not in $Q$. In this latter case, $P$ contains the group generated by $b$ and $Q$ modulo $p$, which is bigger than $Q$. This is again a contradiction, so we conclude that for all $p$, $p\in P$ and we are done. refer to my questions below

Please ignore...

Untypoed from gurev Let $p$ be prime. Let $Q$ be the set of all remainders of products of distinct elements of $M$ modulo $p$. Let $G$ be the largest subgroup of $\mathbb{Z}_p^{\ast}$ which is contained in $Q$ ($G$ exists because $M$ is infinite and so contains infinitely many things $a$ mod $p$ for some $a$ and thus $Q$ contains the group generated by $a$.) Suppose $G$ does not contain all nonzero residues. Suppose there are only finitely many primes whose residue mod $p$ is not in $G$. Let $b$ be the product of all of these primes modulo $p$. Suppose $b$ is not $0$ (if $b$ is $0$ then $p\in P$). Then by pigeonhole, $bG+1$ contains an element not in $G$. Take a set of primes in $M$, including all those with remainder mod $p$ not in $G$, whose product+1's remainder mod $p$ is not in $G$. Then by the definition of a subgroup, one of this number's prime factors is not in $G$ mod $p$ either, but is in $M$. This is a contradiction, so either $G$ does contain all nonzero residues, in which case it contains $-1$ and so contains $0$, or there are infinitely many primes which are $b$ mod $p$ for some b not in $G$. In this latter case, $M$ contains the group generated by $b$ and $G$ modulo $p$, which is bigger than $G$. This is again a contradiction, so we conclude that for all $p$, $p\in M$ and we are done.

Please ignore all my previous questions... now here's my only question left: Why are you sure that $M$ contains the group generated by $b$ and $G$ modulo $p$?

For a similar problem see here: http://artofproblemsolving.com/community/c6h3886p11923

Let me give a complete solution; it bears some similarities to gurev's solution but I think more details are needed to make it work. Assume $p$ is a prime not in $M$. Note that $M$ is infinite (if $p_1, \ldots, p_k \in M$ then a divisor of $p_1\ldots p_k+1$ is a new prime in $M$ and keep going). Let $N$ be the set of residues mod $p$ that appear infinitely often in $M$; then $N$ is non-empty. Let $\Sigma$ be the set modulo $p$ generated by all possible products in $N$ (i.e. $\Sigma=\{x_1\ldots x_k\mid x_i\in N\}$. By construction, $\Sigma$ is multiplicative i.e. if $s_i\in \Sigma$ then $\prod s_i\in \Sigma$. ($\Sigma$ is actually a subgroup but we don't need it). Also, $\Sigma$ contains 1 - by Fermat's Little Theorem if $a\in N$ then $a^{p-1}=a\cdot a\cdot \ldots \cdot a$ is in $\Sigma$. Note the following fact: for every $s$ in $\Sigma$ there are primes $p_1, \ldots p_k\in M$ such that $p_1\ldots p_k\equiv s\pmod p$. Indeed, $s=x_1\ldots x_k$ where $x_i$ are in $N$; now $x_i$ are not necessarily distinct but we may choose distinct $p_i$ such that $p_i\equiv x_i\pmod p$ hence the conclusion follows. For simplicity, set $a\Sigma+b=\{as+b\mid s\in \Sigma\}$. The set $\Sigma+1$ has the same cardinality as $\Sigma$, but $\Sigma$ contains 1 (Fermat's Little Theorem) and $\Sigma+1$ does not. Hence there is some element in $\Sigma+1$ but not in $\Sigma$ which means for some $s\in \Sigma$, $s+1\not\in \Sigma$. Choose $p_i\in M$ with $p_1\ldots p_k\equiv s\pmod p$ then $p_1\ldots p_k+1$ decomposes as a product of primes in $M$. If $s+1\equiv 0\pmod p$ we are done. Otherwise, since $\Sigma$ is multiplicative, not all these primes may give remainders in $\Sigma$ so at least one, say $q_1$ does not give a remainders in $\Sigma$. Now consider $q_1\Sigma+1$ versus $\Sigma$. Again, the former does not contain 1 but the latter does, so there is some $s\in \Sigma$ such that $q_1s+1$ is not in $\Sigma$. Write $\prod \widetilde p_i\equiv s\pmod p$ then we obtain some $q_2\mid q_1\widetilde p_1 \ldots \widetilde p_\ell+1$ such that $q_2$ does not give a remainder in $\Sigma$; note that $q_2\neq q_1$. Then proceed with $q_1q_2\Sigma+1$ and so on. We get an infinite supply of $q_i$ whose remainders modulo $p$ are not in $\Sigma$; but at least one of these remainders must the appear infinitely many times which would place it in $N\subset \Sigma$. Contradiction.

assume any p isnt in M and let Q be the product of all primes in M whose congruence occurs finite times mod p in M. (Q=1 if no such prime exists) let C be set of numbers that are products of primes whose congruences all occur infinite times mod p in M, then consider any c in C, possible c=1, and take the number cQ+1. The primes who divide it must be primes whose congruences all occur infinite times mod p in M, and so cQ+1 is in C. So now Q+1 is in C, Do this again, Q^2+Q+1 is in C, do this again and you get 1+Q+...+Q^n is in C. But this sometimes is 0 so p is in M, done.

theflowerking wrote: assume any p isnt in M and let Q be the product of all primes in M whose congruence occurs finite times mod p in M. (Q=1 if no such prime exists) let C be set of numbers that are products of primes whose congruences all occur infinite times mod p in M, then consider any c in C, possible c=1, and take the number cQ+1. The primes who divide it must be primes whose congruences all occur infinite times mod p in M, and so cQ+1 is in C. So now Q+1 is in C, Do this again, Q^2+Q+1 is in C, do this again and you get 1+Q+...+Q^n is in C. But this sometimes is 0 so p is in M, done. "The primes who divide cQ+1 must be primes whose congruences all occur infinite times mod p in M" is not necessarily true. At most we can say such divisor is not a divisor of Q. It can be a prime not in M, regardless its congruences all occur finite or infinite times mod p in M or in P.

My solution: obviously $M$ is infinite. Let $p$ be an arbitrary prime number and assume for a sake of a contradiction that $p\not\in M$. now let $A=\{a_1,a_2,\dots ,a_t\}$ be the set of remainders modulo $p$ such that for every $1\le i\le t$ there are infinitely primes in $M$ such that they equal $a_i$ modulo $p$. Let $G$ be the set of all remainders given by product of some elements of $M$. Let $a$ be the product of all elements of $G-A$ (note that $G-A$ is finite) Note that $0$ doesn't belong to the $G\Longrightarrow 1\not\in Ga+1$.$\bigstar$ (otherwise we are done) note that from the first problem we can find some primes such that their product equals $1$ modulo $p$ hence $1\in G$ but from $\bigstar$ $1\not\in aG+1$ hence there is some $x\in \mathbb{Z}_p$ such that $x\in G,ax+1\not\in G$(other wise $G=aG+1\Longrightarrow 1\in aG+1$ contradiction) thus there are some primes $p_1,p_2,\dots ,p_k\in M$ such that $p_1p_2\dots p_k\equiv x\pmod{p}$ and let $ap_1p_2\dots p_k+1=q_1^{\beta_1}q_2^{\beta_2}\dots q_s^{\beta_s}\equiv ax+1\pmod{p}$ from our discussion we deduce that there is some $1\le i\le s$ such that $q_i\not\in A$ (otherwise $ax+1\in G$ contradiction). so we find a prime $q_i$ such that $q_i\not\in A, q_i\in M-A$ but $q_i$ is coprime with elements of $M-A$ so $q_i\not\in M-A$(because $\text{gcd}(a,q_i)=1$ contradiction. DONE

Fix a prime $p$. Let $X$ be the set of primes from $M$ whose residue mod $p$ can be found infinitely often in $M$ and let $Y=X-M$. It is easy to see that $Y$ if finite as there is only a finite number of residues mod $p$. Define $t=1$ if $Y$ is empty and $t=\displaystyle\prod\limits_{y\in Y} y$ otherwise. For $x\in X$ (and $x=1$), the number $tx+1$ has prime divisors only from $X$ as $(t,tx+1)=1$. Start with $a_1=t+1$ and define $a_{n+1}$ inductively as follows: write $ta_n+1=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$. From the observation made earlier, $p_1,...,p_k\in X$; so for each $p_i$ we can find an infinite number of primes from $M$ with the same residue mod $p$. Choose $\alpha_1$ primes from from $M$ congruent with $p_1$, $\alpha_2$ primes congruent with $p_2$,..., $ \alpha_k$ congruent with $p_k$ and choose them such that they are all distinct (this can be done due to the fact that each $p_i$ has the same residue as an infinite other primes from $M$). Let $a_{n+1}$ be the product of previously $\alpha_{1}+\alpha_2+...+\alpha_k$ primes chosen. Note that $a_{n+1}\equiv ta_n+1( \mathrm{mod}\ p)$, so $a_n\equiv t^n+t^{n-1}+...+t+1 (\mathrm{mod}\ p)$. We are now truly happy: if $t$ is divisible by $p$ it is obvious; if $t\equiv 1(\mathrm{mod}\ p)$, then $p$ divides $a_p$. Otherwise, $a_{p-2}\equiv \dfrac{t^{p-1}-1}{t-1}\equiv 0 (\mathrm{mod}\ p)$, which ends the proof

This looks too easy to be correct but anyway... Define $P(S) := \prod_{s \in S} s$. If $|M|$ is finite then none of the prime divisors of $P(M)+1$ is in $M$, a contradiction so $|M|$ is infinite. Clearly $2 \in M$, so fix any odd prime $p$ and assume FTSOC $p \not \in M$. Call an element $a \in \mathbb{F}_p^{\times}$ to be agis if there's infinitely many $S_i \subset M$ with $S_i \cap S_j$ empty for all $i \neq j$ and $P(S_i) = a$ in $\mathbb{F}_p$ for all $i$, and facis if it's not agis. Claim : There's an element $z \in \mathbb{F}_p^{\times}$ such that $a$ agis implies $za+1 \mod p$ is also agis. Proof : Observe from the definition of agis if $a \in \mathbb{F}_p^{\times}$ is facis then there's a finite set $B_a \subset M$ such that for any $T \subset M$ with $P(T) \equiv a \mod p$, we have $T \cap B_a$ nonempty. The set of primes $q \in M$ for which $q \equiv a \mod p$ is thus also finite (and contained in $B_a$). Let $B := \bigcup_{\text{a is not agis}} B_a$, and $z = P(B) \mod p, Z = \max_{b \in B} b$. So for any set $S$ with $\min_{s \in S} s > Z$ with $P(S) = a$ where $a$ is agis (such set exists by the definition of agisity), if you let $T = S \cup B$ then $P(T)+1$ must be agis, because if it's not then it must have a prime divisor in $B$ which is impossible since all prime divisors of $P(T)+1$ is in $M$ and no element of $B$ divides $P(T)+1 = P(B)P(S)+1$, so if $a$ is agis then $za+1$ is agis too. $\blacksquare$. Note that if $a, b \in \mathbb{F}_p^{\times}$ is agis then $ab \in \mathbb{F}_p^{\times}$ is agis, and thus by primitive roots we see the set of agis elements forms a subgroup (call it $S$) of $\mathbb{F}_p^{\times}$ which is generated by a single element (call it $g$). Let $T = zS+1$, so we have $T = S$. But (working in $\mathbb{F}_p$) $\sum_{s \in S} s = \sum_{0 \leq i \leq |S|-1} g^i = \frac{g^{|S|}-1}{g-1} = 0$, so $0 = \sum_{s \in S} s = \sum_{t \in T} t = \sum_{s \in S} zs + 1 = z \sum_{s \in S} s + \sum_{s \in S} 1 = |S|$, which implies $|S| = p$, a contradiction since $0 < |S| < p$, so done !

Suppose for the sake of contradiction that there is a prime $p\not\in M$. Call an integer $m$ good if there are infinitely many $q\in M$ such that $q\equiv m\pmod{p}$. Since $p\not\in M$, we see that $0$ is not good. Let $I\subseteq M$ be the set if all good numbers in $M$. Claim: We have that $M\setminus I$ is finite. Proof: Suppose for sake of contradiction that $M\setminus I$ is infinite. Then, there is some residue mod $p$ that appears infinitely often in $M\setminus I$, so any prime which is that residue mod $p$ is good, which is a contradiction. Thus, $M\setminus I:=\{p_1,\ldots,p_\ell\}$ is finite. $\blacksquare$ Now, let $\alpha=p_1\cdots p_\ell$, and let \[S=\{q_1^{e_1}\cdots q_r^{e_r}:r\in\mathbb{Z}_{\ge 0},q_1,\ldots,q_r\in I\}.\]It's clear that $S$ is closed under multiplication. Suppose $n=q_1^{e_1}\cdots q_r^{e_r}$. Since each of these primes have infinitely many other primes in $M$ that are the same mod $p$, we can create a number $n'$ which is a product of primes in $M$ (each at most once) such that $n'\equiv n\pmod{p}$. Then, we see that $\alpha n'$ is also a product of primes in $M$ since none of $p_1,\ldots,p_{\ell}$ are in the product making $n'$, which has only good primes. Therefore, we see that all prime factors of $\alpha n'+1$ are in $M$, but they are not $p_1,\ldots,p_{\ell}$, so all prime factors of $\alpha n'+1$ are in fact in $I$. Thus, $\alpha n'+1\in S$. But $n'\equiv n\pmod{p}$, so letting $S_p$ be the image of $S$ when we replace everything in $S$ with its residue class mod $p$, we have that $\alpha n+1\in S_p$, so we have $\alpha S_p+1\subseteq S_p$. Note that $\alpha\not\equiv 0\pmod{p}$, so $x\mapsto \alpha x+1$ is a bijection mod $p$, so $|\alpha S_p+1|=|S_p|$, so $\alpha S_p+1=S_p$. Note that $1\in S$ so $1\in S_p$, so $1\in 1+\alpha S_p$, so $0\in\alpha S_p$. But this is a contradiction as $\alpha S$ consists of numbers that are products of primes from $M$, which doesn't have $p$, so no number in $\alpha S$ is divisible by $p$. This is the desired contradiction, so we are done.

Solved with nukelauncher. Fix a prime \(p\notin M\), and consider \(S_p\subseteq\mathbb F_p\) the set of residues modulo \(p\) that appear infinitely often in \(M\). Let \(T_p\subseteq M\) the elements of \(M\) equivalent to some element of \(S_p\) modulo \(p\). Therefore, \(M\setminus T_p\) is finite, so let the product of its elements be \(N\). Let \(a_0=1\); then given that \(a_n\) is the product of some distinct elements of \(T_p\), we can write \[Na_n+1=p_1^{e_1}\cdots p_k^{e_k}\]for \(p_1,\ldots,p_k\in T_p\) (since \(\gcd(N,p_i)=1\)). Replace each \(p_i^{e_i}\) with \(e_i\) distinct elements of \(T_p\), each equivalent to \(p_i\) modulo \(p\), which exist by definition of \(T_p\); then let the resulting product be \(a_{n+1}\). It follows that \(a_{n+1}\equiv Na_n+1\pmod p\), and \(a_{n+1}\) is the product of distinct elements of \(T_p\). Thus this sequence may be extended infinitely. But note that if \(N\equiv1\pmod p\), then some element of \(a_1\), \(a_2\), \(\ldots\) will be \(0\pmod p\); otherwise, \[a_{p-2}\equiv N^{p-2}+N^{p-3}+\cdots+1\equiv\frac{N^{p-1}-1}{N-1}\equiv0\pmod p.\] Both cases yield contradiction.

Solved with only myself . Fix a prime $p$. We will show $p\in P$. Consider the sets \[M_q=\{\prod_i p_i\mid \forall i,p_i< q \wedge p_i\in M\}\]as $q$ varies through the elements of $M$, which are then taken modulo $p$. Clearly the sets eventually do not change as $q$ increases: for concreteness, say that for some $r$ and every prime $q>r$, $M_q=M_r\pmod{p}$. Similarly, let $s>r$ be some prime such that for every $q>s$, if we define \[N_t=\{\prod_i p_i\mid \forall i,r<p_i<t\wedge p_i\in M\},\]we have $N_s=N_q\pmod{p}$. Observe that for each $q>s$, we have $qN_s\subseteq N_s\pmod{p}$. Let \[a=\prod_{i\le r} p_i.\]Observe that $a+1\in M_r\pmod{p}$ by noting $a+1$ must lie in $N_s$, $a(a+1)+1=a^2+a+1\in M_r\pmod{p}$ by noting $a$ times some integer congruent to $a+1$ mod $p$ that is the product of distinct primes greater than $r$ is some product of primes in $M$, and this also lies in $N_s$ because $a$ cannot divide this number. A similar argument shows that all \[a^k+a^{k-1}+\cdots+1=\frac{a^{k+1}-1}{a-1}\]lie in $M_r$ mod $p$. If any such number is divisible by $p$ we are immediately done. If $a\equiv 1$ mod $p$ taking $k=p-1$ finishes and otherwise taking $k=p-2$ works.

Claim 1:- $2 \in \mathbb{M}$ Proof:- This is obvious. Claim 2:- $\mathbb{M}$ is infinite. Proof:- Suppose not and let $p$ to be the minimum prime in $\mathbb{M}$ other than $2$ and let $X=\prod_{p_i \in A/[2,p]} {p_i}$ Clearly $p|x+1$ and $p|2x+1$ Hence assume $x+1=2^b p^l$ and $2x+1=p^q$ Since $\gcd(x+1,2x+1)=\gcd(x+1,x)=1$,hence $l=0$ or $q=0$ Now $q=0$ is absurd so $l=0$ with $x=2^b-1$ Clearly if $b=2k$ then $p=3$,and if $b=2k+1$ is absurd hence $p=3$ But we are done since $7 \in \mathbb{M}$ and hence $7|2^b-1$ for even $b$ which is impossible,hence $\mathbb{M}$ is infinite. If $M$ was infinite then choose an odd prime $p$ which isn't in $M$ Let $p_1,p_2,......$ be an increasing sequence of elements of $M$ and consider the numbers $p_1+1,p_1 p_2 +1...$ Clearly two of them give the same remainder when divided by $p$ so we can find $i<j$ such that $p|p_1 p_2......p_-p_1 p_2.....p_j$.Since $p$ is not $p_1,p_2,.....,p_i$,so $p$ must divide $\prod{p_j}+1$,but by assumption all prime factors of this number belong to $M$ hence $M=P$

@above: If proving $M$ infinite was enough to make the problem trivial, the problem would be too easy: $M$ is infinite by doing Euclid's proof that there are infinitely many primes exactly. I suggest trying to prove that $M=P$ starting from that.

GeronimoStilton wrote: @above: If proving $M$ infinite was enough to make the problem trivial, the problem would be too easy: $M$ is infinite by doing Euclid's proof that there are infinitely many primes exactly. I suggest trying to prove that $M=P$ starting from that. Yeah actually I will add that part.

GeronimoStilton wrote: @above: If proving $M$ infinite was enough to make the problem trivial, the problem would be too easy: $M$ is infinite by doing Euclid's proof that there are infinitely many primes exactly. I suggest trying to prove that $M=P$ starting from that. If $M$ was infinite then choose an odd prime $p$ which isn't in $M$ Let $p_1,p_2,......$ be an increasing sequence of elements of $M$ and consider the numbers $p_1+1,p_1 p_2 +1...$ Clearly two of them give the same remainder when divided by $p$ so we can find $i<j$ such that $p|p_1 p_2......p_l-p_1 p_2.....p_j$.Since $p$ is not $p_1,p_2,.....,p_i$,so $p$ must divide $\prod{p_j}+1$,but by assumption all prime factors of this number belong to $M$ hence $M=P$ Yeah,I should've write this there but I was a but lazy to do it

Sprites wrote: GeronimoStilton wrote: @above: If proving $M$ infinite was enough to make the problem trivial, the problem would be too easy: $M$ is infinite by doing Euclid's proof that there are infinitely many primes exactly. I suggest trying to prove that $M=P$ starting from that. If $M$ was infinite then choose an odd prime $p$ which isn't in $M$ Let $p_1,p_2,......$ be an increasing sequence of elements of $M$ and consider the numbers $p_1+1,p_1 p_2 +1...$ Clearly two of them give the same remainder when divided by $p$ so we can find $i<j$ such that $p|p_1 p_2......p_l+p_1 p_2.....p_j$.Since $p$ is not $p_1,p_2,.....,p_i$,so $p$ must divide $\prod{p_j}+1$,but by assumption all prime factors of this number belong to $M$ hence $M=P$ Yeah,I should've write this there but I was a but lazy to do it Shouldn’t it be $p|p_1 p_2......p_l-p_1 p_2.....p_j$ instead of $p|p_1 p_2......p_l+p_1 p_2.....p_j$ ?

Yuri-chan wrote: Sprites wrote: GeronimoStilton wrote: @above: If proving $M$ infinite was enough to make the problem trivial, the problem would be too easy: $M$ is infinite by doing Euclid's proof that there are infinitely many primes exactly. I suggest trying to prove that $M=P$ starting from that. If $M$ was infinite then choose an odd prime $p$ which isn't in $M$ Let $p_1,p_2,......$ be an increasing sequence of elements of $M$ and consider the numbers $p_1+1,p_1 p_2 +1...$ Clearly two of them give the same remainder when divided by $p$ so we can find $i<j$ such that $p|p_1 p_2......p_l+p_1 p_2.....p_j$.Since $p$ is not $p_1,p_2,.....,p_i$,so $p$ must divide $\prod{p_j}+1$,but by assumption all prime factors of this number belong to $M$ hence $M=P$ Yeah,I should've write this there but I was a but lazy to do it Shouldn’t it be $p|p_1 p_2......p_l-p_1 p_2.....p_j$ instead of $p|p_1 p_2......p_l+p_1 p_2.....p_j$ ? Yes it should be,thanks typos fixed

FTSoC there is prime $p \not \in M$. We can now split $M$ into disjoint sets\[M = S_1 \cup S_2 \cup \ldots S_{\ell} \cup T\]such that each set $S_i$ consists of infinitely many primes that all leave the same residue $a_i$ modulo $p$, where $a_1, a_2, \ldots , a_{\ell}$ are distinct and $\ell$ is an integer from $0$ to $p$. This leaves $T$ to be the set of primes $q \in M$ such that there are only finitely many primes $q' \in M$ for which $q' \equiv q \pmod p$. Clearly, $T$ is finite, else it contains infinitely primes of a certain residue. Let $P$ be the product of everything in $T$. We define sequence $a_n$ inductively, as follows: $a_0 = 1$ If $a_n$ is the product of distinct elements of $M \backslash T$, then define $a_{n+1}$ as follows: consider the quantity $Pa_n + 1$, all of whose prime factors are in $M$. Furthermore, all primes dividing it must not be in $T$, since all such primes divide $P$ and are thus relatively prime to $Pa_n + 1$. Hence, we may write $Pa_n + 1 = p_1^{k_1}\ldots p_r^{k_r}$ for some primes $p_1, \ldots , p_r \in M \backslash T$. Now, let $a_{n+1}$ be formed by replacing each $p_i^{k_i}$ by the product of some distinct primes $q_1q_2\ldots q_{k_i}$ for which\[q_1 \equiv \ldots \equiv q_{k_i} \equiv p_i \pmod p.\]This way, we maintain the status of each $a_i$ being the product of different primes in $M \backslash T$, as well as $a_{n+1} \equiv Pa_n + 1 \pmod p$ so\[a_{N} \equiv P^N + P^{N-1} + \ldots + 1 \pmod p.\] Having defined this sequence, we will now show that some element of this sequence will be divisible by $p$, which would imply $p \in M \backslash T \subseteq M$, a contradiction. Indeed, if $P \equiv 0 \pmod p$ then we immediately have $p \in M$, a contradiction. Otherwise, if $P \equiv 1 \pmod p$, then\[a_{p - 1} \equiv 1 + 1 + \ldots + 1 \equiv 0 \pmod p\]and in all other cases\[a_{p-2} \equiv P^{p-2} + P^{p-3} + \ldots + 1 \equiv \frac{P^{p-1} - 1}{P - 1} \equiv 0 \pmod p.\]Either way, in all cases, we get $p \in M$, contradiction, as desired.

Solution with rama1728. A very nice problem. Assume there is a prime $p \notin M.$ Some residues $\pmod{p}$ occur infinitely often as primes in $M,$ and others only occur finitely often. Take all primes in $M$ equivalent to the latter residues (only finitely many) and put them in a subset $S \in M.$ Call a finite subset $T$ of $M$ good if $S \in T.$ Denote $P(T)$ as the product of the elements in $T.$ We create a sequence of good subsets. Take $T_1 = S,$ and suppose $P(S) = s.$ Let the prime factorization of $s+1$ be $p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}.$ Note $p_1,p_2, \dots p_k \in M \setminus S.$ In the prime factorization, replace each $p_i^{a_i}$ with $a_i$ distinct primes in $M \setminus S$ equivalent to $p_i \pmod{p},$ so the primes replacing $p_i^{a_i}$ and $p_k^{a_k}$ are disjoint for any $i \ne k.$ This can be done since there are infinitely many primes in $M \setminus S$ that are $\equiv p_i \pmod{p}.$ Then the product of these primes taken over all $p_i^{a_i}$ is $\equiv s+1 \pmod{p}.$ If $T_2$ is the union of these primes and $S,$ then $P(T_2) \equiv s^2+s \pmod{p}.$ Extending this process creates a sequence of good subsets $T_1,T_2, T_3 \dots $ with products equivalent to $s, s^2+s, s^3+s^2+s \dots$ modulo $p.$ Claim: Unless $s \equiv 0 \pmod{p},$ the sequence $s+1, s^2+s + 1, s^3+s^2+s+1, \dots $ must eventually hit $0 \pmod{p}.$ Proof: If $s \equiv 1$ it's easy. Otherwise, see $0 \equiv \frac{s^{p-1}-1}{s-1} = s^{p-2} + s^{p-3} + \dots + 1 \pmod{p}.$ $\square$ So eventually we'll get a good subset $T$ where the $P(T) + 1 \equiv 0 \pmod{p},$ implying $p \in M,$ contradiction. $\blacksquare$ Remark: The solution extends the idea in Euclid's Proof of the Infinitude of Primes. In Euclid's Proof, we assume there are finitely many primes, multiply them all and add one, and the result must be a multiple of a new prime $p$. In this problem, we fix $p,$ and cleverly build up a finite subset of primes in $M$ so that when we multiply them all and add one, the result is a multiple of $p.$

Nice problem! It is obvious that $M$ has infinitely prime numbers . Suppose that $p$ is the smallest prime number that is not in the $M$.Let $S \in M$ be the prime numbers in the $M$ such that we have infinitely of them (modulo $p$) thus $M -S$ has finite numbers take $s$ be the product of all numbers in $M - S$.So $s+1=q_1^{\alpha _1} \cdots q_r^{\alpha_r}$ that $\{ q_1,\cdots q_r \} \in S$ by the assume we have infinitely many primes in $S$ that are equivalent to $q_1,\cdots q_r$ (modulo $p$) so we can make a number with prime numbers in $S$ that is equivalent to $s+1$ (modulo $p$).Take $s_1$ be such number thus all the prime factors of $ss_1+1$ are in the $S$ and $ss_1+1 \equiv s^2+s+1 (mod p)$ by the same we can take $s_2$ with product of some prime numbers in $S$ such that $s_2 \equiv s^2+s+1 (mod p)$,... we can take $s_{p-2}$ by the sam way such that $s_{p-2} \equiv s^{p-2}+\cdots+s+1=\frac{s^{p-1}-1}{s-1}$ so $ss_{p-2}+1 \equiv s^{p-1}+s^{p-2}+\cdots +1=\frac{s^p-1}{s-1}=s_{p-1}$. Now we have tow cases if $s$ in not $1 (mod p)$ then $p \mid s_{p-2}$ and if $s\equiv 1 (mod p)$ the $p \mid s_{p-1}$ wich all of cases implying $p \in M$ wich is a contradiction...

A slightly different solution, motivated by trying very hard to get a $-1 \pmod{p}$ element into $M$. (For example, if we can't do this, then we should not have any quadratic nonresidues mod $p$, etc.) Obviously $M$ is infinite, since if $M$ is finite we may multiply all its elements and add $1$ to form a number which must be divisible by a prime not in $M$. Suppose $M \neq P$, and let $p$ be an arbitrary prime not in $M$. Let $g$ be a primitive root modulo $p$ and construct the nonempty set $T=\{a_1,\ldots,a_n\}$ where $1 \leq a_i \leq p-1$ such that the mod-$p$ residues which occur infinitely many times in $M$ are precisely $g^{a_1}\ldots,g^{a_n}$. Then by Bezout's (!), we can form $g^{d'}$ by multiplying distinct elements of $M$, where $d'=\gcd(a_1,\ldots,a_n)$—specifically, we find an integer combination, and by replacing $-k$ with $(p-2)k$ (for $k$ positive) we make it nonnegative. Then we can obviously form $g^{d'k}$ for any positive integer $k$, so in conclusion we can form any $\gcd(a_1,\ldots,a_n,p-1):=d$-th power of $g$ (or equivalently $d$-th power mod $p$ in general). Note that each $a_i$ is divisible by $d$, so these elements are all $d$-th powers as well. Since the other residues of $M$ mod $p$ occur finitely many times, we can let their product be $N$. Therefore, consider $$g^dN+1,g^{2d}N+1,\ldots,g^{\tfrac{p-1}{d}\cdot d}N+1.$$Each of these values must be $d$-th powers modulo $p$, otherwise that value cannot be formed by multiplying only $d$-th powers, but it is also not divisible by any non-power of $d$, since all the non-powers of $d$ in $M$ divide $N$. Furthermore, since $p \nmid N$, we have $$g^{id}N+1 \equiv g^{jd}N+1 \pmod{p} \iff g^{(i-j)d} \equiv 1 \pmod{p} \iff \frac{p-1}{d} \mid i-j,$$which is not possible for the values of $i,j$ we are considering (namely $1 \leq i,j \leq \tfrac{p-1}{d}$), so by Pigeonhole we must have $$\{g^dN+1,\ldots,g^{p-1}N+1\}\equiv\{g^d,\ldots,g^{p-1}\} \pmod{p},$$but we cannot have $g^{id}N+1 \equiv g^{p-1} \equiv 1 \pmod{p}$, since this implies $p \mid g^{id}N$: absurd. Therefore such a $p$ cannot exist, i.e. $M=P$ (indeed, if $p \in M$ but we attempt this argument, we will get $p \mid N$ and there is no injectivity and therefore no contradiction). We are done. $\blacksquare$ Remark: An alternative way of finding the appropriate contradiction is as follows: consider the $\mathbb{F}_p[x]$ polynomial $x^{\frac{p-1}{d}}-1$, which has roots $g^d,\ldots,g^{p-1}$. On the other hand, if we write the polynomial $(xN+1)^{\frac{p-1}{d}}-1$, since $xN+1$ should be a $d$-th power if $x$ is, this polynomial also has roots $g^d,\ldots,g^{p-1}$. Observe that neither polynomial is identically zero. If we notice now that $x=0$ is also a root, then we get a contradiction since the nonzero $(xN+1)^{\frac{p-1}{d}}-1$ now has more roots than its degree (look at leading coefficient)—this is isomorphic to the original solution. Alternatively, a "foolproof" way of finding a contradiction, without noticing the root of $0$, is to remark that since $x^{\frac{p-1}{d}}-1$ and $(xN+1)^{\frac{p-1}{d}}-1$ share some number of roots equal to their degree, they must be the same polynomial up to scaling by a nonzero factor. But the constant coefficient of $(xN+1)^{\frac{p-1}{d}}-1$ is clearly $0$, which cannot result from scaling the constant coefficient of $x^{\frac{p-1}{d}}-1$ (i.e. $-1$) by a nonzero factor: contradiction. This was how I originally did the problem, but then I realized that since the constant coefficient was $0$, then $0$ was a root and we get a simpler contradiction, and then I realized that we didn't need the polynomial at all.

Trivially $M$ is not finite or else we would have no primes from $M$ dividing $\prod_{p \in M} p+1$. Suppose FTSOC there exists an odd prime $p$ with $p \not \in M$, then let $\mathcal F$ the set of primes $q$ in $M$ satisfying that there only exists finitely many $q' \in M$ with $q' \equiv q \pmod p$, clearly $\mathcal F$ is finite otherwise it would contradict it's own definition by PHP. Now let $F=\prod_{p \in \mathcal F}$ (or $1$ if $\mathcal F$ is empty), construct a sequence starting with $a_0=1$ and the following inductive construction: If we have that $F \cdot a_n+1=\prod_{i=1}^{k} p_i^{\alpha_i}$ where $a_n$ was either $1$ or the product of some primes in $M$ in which case observe that trivially no element of $\mathcal F$ divides this number, now consider $\pmod p$ and replace each "extra" $p_i$ with like $q_1 \equiv q_2 \equiv \cdots \equiv q_{\alpha_i} \equiv p_i \pmod p$ which can be done as each $p_i$ lies outside $\mathcal F$ and thus we can find infinitely many primes in $M$ that can replace it $\pmod p$, now we call $a_{n+1}$ to be the product of all the $q_{\ell}$'s and then we repeat the process to get all the elements of the sequence. It's now clear that $a_i$ is the product of some primes in $M$ for all $i \ge 1$, but also $a_i \equiv \sum_{j=0}^{i} F^j \pmod p$ which means that if $F \equiv 1 \pmod p$ then $a_{p-1} \equiv 0 \pmod p$, if $p \mid F$ then $p$ was already in $M$ and in any other case by fermat's little theorem we get that $a_{p-2} \equiv 0 \pmod p$. Now clearly $2 \in M$ because $2 \mid p_i+1$ for some large $p_i$, therefore we are done .