Let $S$ be a nonempty set of primes satisfying the property that for each proper subset $P$ of $S$, all the prime factors of the number $\left(\prod_{p\in P}p\right)-1$ are also in $S$. Determine all possible such sets $S$.
Problem
Source:
Tags: pigeonhole principle, number theory proposed, number theory
Drytime
23.07.2012 20:48
Approximately Romania TST 2003, day 4, problem 1.
mavropnevma
23.07.2012 21:29
I took the opportunity to correct some typos in Valentin's post at that link, and also fill a hole in the reasoning. That proves that if $|S| \geq 3$ then we must have $S$ to be the set of all primes. For the problem at hand, there are extra solutions. Any singleton $S = \{p\}$ works; otherwise we must have $2\in S$, and all doubletons $S=\{2,p\}$ work, provided $p$ is a Fermat prime.
navid
29.07.2012 17:28
I remember this problem was originally proposed in Saint Petersburg at 1995. My solution based on 2steps : first: This set Must be infinite (Its obvious) Second: Assume there exist a priime number P which dooesnt include in this set , now consider this numbers from elements of P: q1, q1*q2, q1*q2*q3,......, q1*q2*.....*qp now by pigeonhole principle the diffrence of 2 numbers above must be divisible by p and then were done!
biomathematics
19.04.2016 11:31
navid wrote: I remember this problem was originally proposed in Saint Petersburg at 1995. My solution based on 2steps : first: This set Must be infinite (Its obvious) Second: Assume there exist a priime number P which dooesnt include in this set , now consider this numbers from elements of P: q1, q1*q2, q1*q2*q3,......, q1*q2*.....*qp now by pigeonhole principle the diffrence of 2 numbers above must be divisible by p and then were done! Obviously the set may not be infinite.
shinichiman
23.04.2016 08:31
For $|S|=2$ then $S= \{ 2 \}$ and for $|S|=3$ then $S= \{ 2,p \}$ where $p$ is a Fermat prime.
For $|S| \ge 3$, first, we will prove that $S$ is a infinite sets. Indeed, assume the contradiction that $S$ has $l$ elements $S= \{ p_1,p_2, \cdots ,p_l \}$ with $2=p_1<p_2< \cdots <p_l$.
If all of these primes are Fermat primes, denote $p_i=2^{k_i}+1$. From the statement of the problem and a notation that $\gcd (p_2p_3 \cdots p_l-1, p_i)=1$ for all $2 \le i \le l$ we follows $p_2p_3 \cdots p_l-1=p_1^m=2^m$.
For $m=1,2$ then $l=2$, a contradiction. $m=3$ also gives a contradiction. With $m \ge 4$, according to Zsigmondy's theorem, there exists a prime divisor $p$ of $2^m+1$ such that $p \nmid 2^x+1 \; \forall 1 \le x \le m-1$. However, $p$ is a Fermat prime, so this can only happen when $p=2^m+1$ or $|S|=2$, a contradiction.
If not all of the elements of $S$ are Fermat primes, which means there exists $p_i \ne 2^l+1$. This follows that there exists $p_j \; (j<i)$ such that $2 \ne p_j$ and $p_j \mid p_i-1$. We also have that $p_1p_2 \cdots p_{i-1}p_{i+1} \cdots p_l-1=p_i^k$ so $p_j \mid p_1p_2 \cdots p_{i-1}p_{i+1} \cdots p_l-2$, a contradiction.
Thus, $S$ is an infinite set if $|S| \ge 3$.
Consider an arbitrary prime $q$, since set $S$ is infinite so there exists $k \in \mathbb{N}, 1<k<q$ such that there are infinite prime $p \equiv k \pmod{q}$ in $S$. Hence, we pick $q-1$ such prime $p$ then we must have all the divisor of $\prod_{p \equiv k \pmod{q}} p -1$ are in $S$. We also have $q \mid \prod_{p \equiv k \pmod{q}} p -1$ so this gives $q \in S$. Hence, for $|S| \ge 3$ then $S$ is the set of all primes.
MV2
17.05.2022 10:55
Solution. Let $S = \{p_{1}, p_{2}, .. , p_{n}\}$ and $p_{1} < p_{2} < .. < p_{n}$ Claim 1: $p_{1} = 2$ Proof. For the time being, Let $P = \{p_{1}\}$. According to the condition there is a $p \in S$ such that $p|p_{1} - 1$. But $p > p_{1}$ which implies $p_{1} = 2$. $\square$ Claim 2: $p_{2} = 2^{\alpha} + 1$ for some positive integer $\alpha$ Proof. For the time being, Let $P = \{p_{2}\}$. It is easy to see that for all $p > p_{2}$ and $p \in S$, $p \nmid p_{2} - 1$ which implies $p_{1}|p_{2} - 1 \Rightarrow p_{2} = p_{1}^{\alpha} + 1 = 2^{\alpha} + 1$ for some positive integer $\alpha$. $\square$ Claim 3: $p_{3} = 2^{\alpha + 1} + 1$ Proof. For the time being, Let $P = \{p_{1}, p_{2}\} = \{2, p_{2}\}$. If $p_{3} > 2p_{2} - 1$ then there will be no prime in $S$ which will divide $2p_{2} - 1$. Therefore, $p_{3} \leq 2p_{2} - 1$. Now, $p_{2} < p_{3} \leq 2p_{2} - 1 \Rightarrow 2^{\alpha} + 1 < p_{3} \leq 2^{\alpha + 1} + 1$. Since $p_{1}, p_{2}$ alone must divide $p_{3} - 1$. Hence, $p_{3} = p_{1}^a p_{2}^b + 1 = 2^a (2^{\alpha} + 1)^b + 1$ for some positive integers $a, b$. If $a = 1, b =1$ then $p_{3} > 2p_{2} - 1 \Rightarrow b = 0$ and we have, $2^{\alpha} + 1 < p_{3} = 2^{a} + 1 \leq 2^{\alpha + 1} + 1 \Rightarrow a = \alpha + 1 \Rightarrow p_{3} = 2^{\alpha + 1} + 1$. $\square$ Since both $p_{2}$ and $p_{3}$ are fermat primes, $\alpha = 2^{m}, \alpha + 1 = 2^{n} \Rightarrow 2^{m}(2^{n - m} - 1) = 1 \Rightarrow m = 0, n = 1 \Rightarrow \alpha = 1 \Rightarrow p_{2} = 3, p_{3} = 5$. Hence, $S = \{2, 3, 5, p_{4} , p_{5}, .. , p_{n}\}$. Once again for the time being, Let $P = \{3, 5, p_{4}, p_{5}, .. , p_{n}\}$. According to the condition, $2^{\beta} + 1 = 3\cdot5\cdot p_{4} \cdot\cdot \cdot p_{n}$. If $3|2^{\beta} + 1$ then $\beta$ is odd and if $5|2^{\beta} + 1, \beta = 4k - 2$ for some positive integer $k$ which is a contradiction. The contradiction can be avoided only if $|S|$ is infinite or $|S| \leq 2$. Claim 4: If $|S|$ is infinite then $S$ must contain all the primes Proof. On the contrary, Let $p$ be a prime and $p \notin S$. For some positive integer $i$, Consider the following sequence $p_{i}p_{i+1}\cdot\cdot\cdot p_{i+p-1} - 1, p_{i}p_{i+1}\cdot\cdot\cdot p_{i+p-2} - 1, .. , p_{i}p_{i+1} - 1, p_{i} - 1$. Since none of these numbers is divisible by $p$, According to PHP we must have atleast two numbers with the same remainder modulo $p$ and their difference being divisible by $p$ which implies $p \in S$ which is a contradiction. $\square$ Hence, $S = \{p\}, \{2, F_{n}\}$ and the set of all primes, for any prime $p$ and for any $n$th fermat prime $F_{n}$. $\blacksquare$