Let $\mathbb{P}$ be the set of all primes and let $M$ be a subset of $\mathbb{P}$ with at least three elements. Suppose that for all $k \geq 1$ and for all subsets $A=\{p_1,p_2,\dots ,p_k \}$ of $M$ ,$A\neq M$ , all prime factors of $p_1p_2\dots p_k-1$ are in $M$ . Prove that $M=\mathbb{P}$.
Problem
Source: 2019 Switzerland MO
Tags: number theory
10.03.2019 17:36
Suppose $M\neq \mathbb{P}$. Let $p$ be the smallest prime in $\mathbb{P}-M$. For each $i(1\leq i\leq p-1)$, there are less than $p-1$ primes in $M$ which can be expressed in the from $pk+i$. So $M$ is a finite set, but this is certainly wrong.
10.03.2019 17:46
Romania TST 2003: https://artofproblemsolving.com/community/c6h3886p11923 (see also https://artofproblemsolving.com/community/c6h1106813p5017928)
31.03.2019 20:21
XbenX wrote: Let $\mathbb{P}$ be the set of all primes and let $M$ be a subset of $\mathbb{P}$ with at least three elements. Suppose that for all $k \geq 1$ and for all subsets $A=\{p_1,p_2,\dots ,p_k \}$ of $M$ ,$A\neq M$ , all prime factors of $p_1p_2\dots p_k-1$ are in $M$ . Prove that $M=\mathbb{P}$. Solution. First we claim that $M$ is an infinite set. Indeed, for any finite subset $\{p_1,p_2,\dots ,p_k \}\subseteq M$, any prime factor $p$ of $ p_1\cdot p_2\cdots p_k-1$ is also in $M$ by the given condition. But $p\notin\{p_1,p_2,\dots ,p_k\}$ since $p_i\nmid p_1\cdot p_2\cdots p_k-1$. The claim is thus proven.The Pigeonhole-Principle implies that, for any $p\in\mathbb{P}$, there exist $k\in\{1,2,\cdots,p-1\}$ and $p-1$ primes $p_i\in M$ such that $p_i\equiv k\pmod{p}$ for every $i\in\{1,2,\cdots,p-1\}$. Therefore, the Fermat's Little Theorem yields $$p_1\cdot p_2\cdots p_{p-1}\equiv k^{p-1}\equiv1\pmod p,$$which means $p\mid p_1\cdot p_2\cdots p_{p-1}-1$ thereby $p\in M$. Hence $M=\mathbb{P}$. $\blacksquare$