Since you directly post it in the solved problems section, I will give an answer rather than move it to the unsoved problems section . First, note that the statement is incorrect because you have to add the hypothesis that there is an odd prime in M : Indeed if M is empty or M = {2}, the statements of the problem are satisfied but not the conclusion... Moreover, if you add the condition that A is not M, you have to assume that M has at least to elements.... Thus, I assume that there is an odd prime p in M and A is allowed to be M. 1) Now, we first prove that M is infinite : Suppose, for a contradiction, that M = {p_1,...,p_n} is finite. Let N = p_1*...*p_n - 1. Then, N > 1 and each prime divisor of N belongs to M. But N is divisible by none of the p_i's, a contradiction. 2) Let q be a prime number. Since M is infinite, there exists a in {1,2,...,q-1} such that x = a mod[q] has an infinite number of solutions in M. In particular, there exist p_1,...,p_(q-1) in M pairwise distincts such that p_i = a mod[q] for i =1,...,q-1. Then, from Fermat's little theorem, we have : N = p_1*...*p_(q-1) - 1 = a ^q-1 - 1 = 0 mod[q]. Thus, q divides N and then q is in M. So that M contains all primes, and since M is contain,ed in P, we have the conclusion. Pierre.

Oh,sorry because of my carelessness.[M] is more than 2!But you note that:"[M] is infinite " is not easy to prove.A is not be M.Be careful!In part 2,you gave me a nice solution , and I have a solution rather short:Suppose,for a contradiction,there exits a prime p,not belong to M,we note the infinite sequences :p_1-1,p_1*p_2-1,...,p_1*p_2*...*p_k-1,...({p_i}^i=1, \infty ) by dirichlet ,there exits j>k: p_1*...*p_k-1=p_1*...*p_j-1(mod p) p_k+1...p_j-1=0(mod p) .So p belongs to M. CONTRADICTION!!So M=P.

If $2\not \in M$, then $A=\{p\}$, with $p\in M$. Because $p-1$ is an even number, it follows that $2\in M$, contradiction, thus $2\in M$. First let us suppose that $M$ is finite. Then let $M$ be $\{2,p_2,\ldots,p_k\}$, $k\geq 3$. Let $A$ be $\{2,p_3,\ldots,p_k\}$, and denote by $P$ the product of all the elements of $M$. Then we have: \[ 2p_3\cdots p_k-1=\frac {P}p_2 -1 = p_2^\alpha \Rightarrow P=p_2^{\alpha+1}+p_2 \ \ \eqno (1) \] and if we consider $A=\{p_3,\ldots,p_k\}$ then we obtain: \[ p_3\cdots p_k-1 = \frac {P}{2p_2} -1 = 2^\beta p_2^\gamma \Rightarrow P=2p_2(2^\beta p_2^\gamma+1) \ \ \eqno (2) \] From $(1)$ and $(2)$ it follows that \[ p_2^{\alpha+1}+p_2 = 2p_2(2^\beta p_2^\gamma+1) \Rightarrow p_2^\alpha +1 = 2^{\beta+1}p_2^\gamma + 2 \Rightarrow 1\equiv 2 \pmod{p_2} \] contradiction, thus indeed $M$ has an infinite number of elements. Suppose now that there is a prime $q$ such that $q\not \in M$. Let $M=\{2,p_2,p_3,\ldots,p_k,\ldots\}$. From the Pigeonhole Principle it follows that from the numbers $2-1,2\cdot p_2-1,\ldots, 2p_2\cdots p_{q+1}-1$ at least two of them have the same residue modulo $q$, let them be $2\cdots p_i-1\equiv 2\cdots p_j-1$, $1\leq i< j\leq q+1$. But then we have \[ 2\cdots p_i(p_{i+1}\cdots p_j-1)\equiv 0 \pmod q \Rightarrow p_{i+1}\cdots p_j-1\equiv 0 \pmod q \Rightarrow q\in M\] which is a contradiction, therefore the supposition was false and $M$ is the set of all primes.

So, I will not qualify for IMO this year again, pfff.... Note that the text was unclear so I changed it to be true, but not in the right form... bad luck. See you next year at IMO, I hope.... Btw, it is a nice problem. Pierre.

I have a different solution to this problem. As Valentin did i proved that $2\in M$, and also $3$ is in $M$, just doing some easy cases modulo 3. (we could not have another prime that is $2 \bmod 3$ and we could not have a prime that is $1 \bmod 3$). This shows that $|M|>3$ because $5$ and $7$ must also be in $M$ ($3\times 2-1= 5$ and $3\times 5-1 =14$). Now suppose that $M$ is finite and let $p$ and $q$ be any to primes in $M$. Let $P$ be the product of all the elements of $M$. We know that $\frac{P}{p}-1 = p^{\alpha}$ for some integer $\alpha > 0$ and that $\frac{P}{q}-1= q^{\beta}$ for some integer $\beta>0$. We also have that there $1<\frac{P}{pq}-1=p^{a}q^{b}$ (the inequality holds because $|M|> 3$ with at least one of the exponents positive. Suposse WLOG that $a>0$. We have that: $\frac{P}{pq}\equiv 1 (\bmod p)$ $\implies \frac{P}{p}\equiv q \equiv 1 (\bmod p)$ So $q>p$ and $b=0$ (otherwise we would have that $p=1$ which is imposible). (*) Now let $p$ be the biggest prime in $M$. And let $r$ be any prime in $M$ different from $2$ or $p$. Using (*) we have that: 1) $p\equiv 1 (\bmod r)$ 2) $2\equiv 2 (\bmod r)$ $\implies 2p \equiv 2 (\mod r)$. So $2p-1$ has a prime divisor that is not in $M$. Contradiction. So $M$ is infinite. Now suppose that there is some prime $p \notin M$. Since $M$ is infinite there are infinitely primes $q$ so that $q \equiv t (\bmod p)$ for some $1\le t < p$. Take $p-1$ from those primes and call $D$ their product. Fermat's little theorem tells us that $D\equiv r^{p-1}\equiv 1 (\bmod p)$ so that $p| D-1$ which is a contradiction. So $p$ does not exist and $M=\mathcal{P}$

Valentin Vornicu wrote: If $2\nin M$, then $A=\{p\}$, with $p\in M$. Because $p-1$ is an even number, it follows that $2\in M$, contradiction, thus $2\in M$. First let us suppose that $M$ is finite. Then let $M$ be $\{2,p_2,\ldots,p_k\}$, $k\geq 3$. Let $A$ be $\{2,p_3,\ldots,p_k\}$, and denote by $P$ the product of all the elements of $M$. Then we have: \[ 2p_3\cdots p_k-1=\frac {P}p_2 -1 = p_2^\alpha \Rightarrow P=p_2^{\alpha+1}+p_2 \eqno (1) \] and if we consider $A=\{p_3,\ldots,p_k\}$ then we obtain: \[ p_3\cdots p_k-1 = \frac {P}{2p_2} -1 = 2^\beta p_2^\gamma \Rightarrow P=2p_2(2^\beta p_2^\gamma+1) \eqno (2) \] From (1) and (2) it follows that \[ p_2^{\alpha+1}+p_2 = 2p_2(2^\beta p_2^\gamma+1) \Rightarrow p_2\alpha +1 = 2^{\beta+1}p_2^\gamma + 2 \Rightarrow 1\equiv 2 \pmod{p_2} \] contradiction, thus indeed $M$ has an infinite number of elements. Suppose now that there is a prime $q$ such that $q\nin M$. Let $M=\{2,p_2,p_3,\ldots,p_k,\ldots\}$. From the Pigeonhole Principle it follows that from the numbers $2-1,2\cdot p_2-1,\ldots, 2p_2\cdots p_{q+1}-1$ at least two of them have the same residue modulo $q$, let them be $2\cdots p_i-1\equiv 2\cdots p_j-1$, $1\leq i< j\leq q+1$. But then we have \[ 2\cdots p_i(p_{i+1}\cdots p_j-1)\equiv 0 \pmod q \Rightarrow p_{i+1}\cdots p_j-1\equiv 0 \pmod q \Rightarrow q\in M\] which is a contradiction, therefore the supposition was false and $M$ is the set of all primes. But $\gamma$ can be $0$, then can not lead to contradiction.

Valentin Vornicu wrote: \[ p_2^{\alpha+1}+p_2 = 2p_2(2^\beta p_2^\gamma+1) \Rightarrow p_2^\alpha +1 = 2^{\beta+1}p_2^\gamma + 2 \Rightarrow 1\equiv 2 \pmod{p_2} \] contradiction, thus indeed $M$ has an infinite number of elements. Indeed there is a hole there; what if $\gamma = 0$ ? Fortunately there probably is a patch. Then $p_2^\alpha +1 = 2^{\beta+1} + 2$, so $p_2^\alpha = 2^{\beta+1} + 1$. Then by Catalan's conjecture (Preda Mihailescu theorem), either $\alpha = 1$ or $p_2=3$, $\alpha= \beta = 2$. Since $p_2$ could be any of the at least two odd primes $p,q$ in $M$, the second possibility dies, since it leads to $p=q=3$. But the first possibility then also leads to $P = p^2+p = q^2 + q$, whence $p=q$, absurd. I also took the opportunity to correct some typos in Valentin's post, which now, with this completion, should be ok.

Hi mavropnevma, it's long time that I do see you (my fault, obviously ) mavropnevma wrote: Indeed there is a hole there; what if $\gamma = 0$ ? Fortunately there probably is a patch. Then $p_2^\alpha +1 = 2^{\beta+1} + 2$, so $p_2^\alpha = 2^{\beta+1} + 1$. Then by Catalan's conjecture (Preda Mihailescu theorem), either $\alpha = 1$ or $p_2=3$, $\alpha= \beta = 2$. Since $p_2$ could be any of the at least two odd primes $p,q$ in $M$, the second possibility dies, since it leads to $p=q=3$. But the first possibility then also leads to $P = p^2+p = q^2 + q$, whence $p=q$, absurd. Although you know for sure what I am going to write, I want to add that the equation $p^x-2^y=1$ (i.e. $\omega(2^y+1)=1$) can be solved completely by elementary tools: $y$ cannot be even, since $m^2+1$ cannot be a power of a prime (see point 1 here) $y$ is odd, so that $p=3$. Assuming $\min\{x,y\}\ge 2$ (otherwise trivially no solutions) we have that $x$ is even (working mod 4), so that we have to solve $2^y=\left(3^{x/2}+1\right)\left(3^{x/2}-1\right)$ and we already know how to conclude.. The real reason of this message is that me and a my friend (Salvatore Tringali) worked together on some extension of the problem itself..in particular we showed that 1. Let $\{v_i\}_{i \in \mathbb{N}}$ be a sequence of positive integers and $A$ a set of relatively prime integers $\ne \pm 1$ such that $|A| \ge 3$ and $p \in A$ whenever $p \in \mathbb P$ (the set of all positive rational primes) and $p$ divides $\prod_{b \in B} b^{v_b} - 1$ for some finite nonempty set $B \subsetneq A$. Then $\mathbb P \subseteq A$. 2. Fix a set $\{q_1,q_2,\ldots,q_n\}:=\mathfrak{P} \subseteq \mathbb{P}$ with $n\ge 3$ (not necessarily finite) and a infinite sequence of positive integers $v_1,v_2,v_3\ldots$ such that if a prime $p$ divides $(\prod_{i\in I}{q_i}^{v_i})+1$ for some nonempty and finite subset $I$ of $S_n:=\{1,2,\ldots,n\}$ and not equal to $S_n$ itself , then $p \in \mathfrak{P}$. Show that $n$ cannot be finite, and that if there exists $k\in \mathbb{N}$ such that $2^k+1 \in \mathbb{P}\setminus\mathfrak{P}$ then there exist at most $\displaystyle \frac{4^k-1}{3}$ distinct positive integers $n_i$ such that $\displaystyle p \nmid q_{n_i}^{v_{n_i}}-1$. (see here) Cheers, P. Leonetti

First we prove that $|M|>3.$ Indeed assume that $M=\{p_1<p_2<p_3\}.$ If $p$ is a prime factor of $p_1-1,$ then $p<p_1$ and $p$ would be in $M,$ impossible, therefore $p_1-1=1 \Rightarrow p_1=2.$ Now assume $3\notin M.$ If $p_2\equiv 1\pmod 3,$ we arrive at a contradiction, so it must be the case that $p_2\equiv 2 \pmod 3.$ But now $p_1p_2-1\equiv 0 \pmod 3,$ contradiction. Therefore we have $3\in M$ and $2\cdot 3-1=5,$ so $5\in M$ and $M=\{2, 3, 5\}.$ But $3\cdot 5-1=14$ and $7\notin M,$ contradiction. Thus $|M|\geq 4.$ Now assume $M$ is finite and let $M=\{p_1<p_2<\cdots<p_k\}.$ For $i=1, 2, \cdots, k-1$ we look at the numbers $$x_i=\prod_{j=1, j\neq i}^{k}{p_j}-1, y_i=\prod_{j=1, j\neq i}^{k-1}{p_j}-1, z=\prod_{j=1}^{k-1}{p_j}-1.$$ Note that the only prime factor of $x_i$ must be $p_i$, the only prime factor of $z$ must be $p_k$ and also $y_i\geq 2\cdot 3-1>1,$ since $k\geq 4.$ Let's assume that $p_k\mid y_i$ for some $i.$ This means $$\prod_{j=1, j\neq i}^{k-1}{p_j}\equiv 1\equiv \prod_{j=1}^{k-1}{p_j} \pmod {p_k},$$so $p_k\mid p_i-1,$ absurd. Thus the only prime factor of $y_i$ must be $p_i$ for all $i.$ But now $$0\equiv x_i=\prod_{j=1, j\neq i}^{k}{p_j}-1\equiv p_k-1 \pmod {p_i},$$so $p_i\mid p_k-1$ for all $i.$ Since the $p_i$ are relatively prime, we obtain $\prod_{j=1}^{k-1}{p_j}\mid p_k-1.$ But surely we must have $1<z=p_k^{\alpha}$ for some $\alpha>0.$ In the end, $p_k^{\alpha}+1=z+1\mid p_k-1,$ clearly impossible. Therefore our assumption was false and $|M|=\infty.$ Now assume to the contrary that $M\not\equiv \mathbb{P}$ and let $p$ be the smallest prime not in $M.$ Since $|M|=\infty,$ there exists a residue class $0\not\equiv c\pmod p,$ for which we have $q\equiv c\pmod p$ for infinitely many $q\in M.$ Let us select exactly $p-1$ such primes, namely $q_1, q_2, \cdots, q_{p-1}.$ Now with the help of Fermat's little theorem we notice $q_1\cdot q_2\cdots q_{p-1}\equiv c^{p-1}\equiv 1\pmod p,$ so by the problem statement it must be the case that $p\in M,$ contradiction. Finally, we arrive at $M\equiv \mathbb{P}$ and we are done. $\blacksquare$

Note the similarity to TSTST 2015/3.

dreammath wrote: Let $\mathcal{P}$ be the set of all primes, and let $M$ be a subset of $\mathcal{P}$, having at least three elements, and such that for any proper subset $A$ of $M$ all of the prime factors of the number $ -1+\prod_{p\in A}p$ are found in $M$. Prove that $M= \mathcal{P}$. Valentin Vornicu Can anyone check for the validity of this proof? I have a wrong feeling about it. First we prove that the cardinality of $M|$ is infinite. FTSOC assume that the set of primes is finite so $M=\{p_1,\cdots p_k\}$.Let $\mathcal{P}=p_1p_2\cdots p_k$ the product of all the numbers.Now note that for any $1\leq i\leq k$ .$$\dfrac{\mathcal{P}}{p_i}-1=p_i^{\alpha_i}\Longleftrightarrow \mathcal{P}=(p_i^{\alpha_i}+1)\cdot p_i$$Now choosing two indices $i,j$ we see that $p_i(p_i^{\alpha_i}+1)=p_j(p_j^{\alpha_j}+1)$.Thus $p_i=(1+p_j^{\alpha_j})$ and $p_j=(1+p_i^{\alpha_i})$ so $p_i\equiv 1\mod p_j$ and $p_j\equiv 1\mod p_i$which is a contradiction thus $|M|$ is not finite. Next note that $2\in M$ because $|M|\geq 3$ so there is an odd-prime $p$ and so $2\mid p-1$.Chose $p$ as the smallest odd-prime $\not\in M$ and consider the following infinite numbers : - $$p_1-1,p_1p_2-1,p_1p_2p_3-1\cdots$$By PHP two of these numbers give the same remainder when divided by $p$.Thus $p\mid (p_1p_2\cdots p_j)-(p_1\cdots p_j)=p_1p_2\cdots p_i(p_{i+1}\cdots p_j-1)$. $p$ doesnt divide any $p_k$ so $p\mid p_{i+1}\cdots p_j-1$ which is a contradiction.Thus $M=\mathcal{P}$ and we are done.$\square$

Claim 1:-$2 \in M$ Proof:- This is obvious,just choose any prime $p$ and by the property $x|p-1$ implies $2 \in M$ Claim:- The set $M$ is infinite. Proof:-For the sake of contradiction,assume that $p$ is the smallest prime in $M$ and $x=\prod_{p_i \in M/[2,p]} p_i$.(since all prime factors of $x-1$ and $2x-1$ are greater than p) Clearly any prime factor of $x$ is greater than $p$ and by definition all prime factors of $x-1$ and $2x-1$ are in $M$.It follows that $2x-1=p^a$ and $x-1=2^b p^c$ for $a \ge 1,b,c\ge 0$ Now since $\gcd(x-1,2x-1)=1$ so $c=0$ and $x=2^b+1$ then $p^a=2^{b+1}+1$. Clearly by size arguments,$p^k=3,p=3$. But we are already done since this also implies $5$ and $7$ are $\in M$,but however $7 \nmid 2^b+1$ a contradiction hence the result is true. Now the result is clear by size arguments.