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
23.07.2012 20:48
Approximately Romania TST 2003, day 4, problem 1.
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.
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!
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.
23.04.2016 08:31
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$