12
$\begingroup$

Consider a non-empty set $S$ of primes, with the property that, for every finite subset $S'\subset S$, all the primes dividing $\left(\prod_{k\in S'}k\right)+1$ are in $S$.

For instance, it can easily be proven that $2\in S$ (if not, then the smallest member $q$ of $S$ is odd, hence, $q+1$ is even, and thus $2\in S$). In fact, with this way, $2+1=3\in S$, $2\cdot 3+1=7\in S$, $2\cdot 7+1=5\in S$, and so on.

It seems this set must contain all primes, but I could not prove it.

I tried to use that if $p_n$ is the smallest prime that is not contained in $S$, then $p_1,p_2,\dots,p_{n-1}\in S$. $p_n\sim n\log n$ for $n$ large, and if I could somehow show that there is enough residues that can be constructed using subset-products of $p_1,\dots,p_{n-1}$ this should have been handled, but how? Can anybody see a way to do it?

$\endgroup$
2

1 Answer 1

8
$\begingroup$

If I'm not mistaken, it is true that $S$ must contain all primes.

First of all it is obvious that $S$ is infinite -- indeed, as Euclid teach us, if $S$ is finite then $\left(\prod\limits_{p\in S} p\right) + 1$ is coprime to all primes in $S$ and therefore has at least one prime factor not in $S$.

Now let $p$ be a prime number. We will show that $p\in S$. Assume by contradiction that $p\notin S$. Let $R = \{r_1, \ldots , r_k\}$ be residues modulo $p$ that appear infinitely often as residues of primes from $S$ modulo $p$. Since $S$ is infinite $k \ge 1$. Now let $A = \{a_1, \ldots, a_n\}$ be all elements of subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$, spanned by all $r_i$. Also denote by $b$ product of all other primes from $S$ whose residues modulo $p$ are not from $R$.

Note that we can form each $a_i$ as product of different primes from $S$ (and moreover we can use only primes congruent to numbers from $R$ modulo $p$). Then we can also have $ba_i$.

If some of $ba_i + 1$ is congruent to $0$ mod $p$ then we found $p$ and we are done. Thus we can assume that $ba_i + 1$ is never congruent to $0$. Also note that $ba_i$ never congruent to $0$ (since $p\notin S$ by assumption) and all $ba_i$ are pairwise distinct(since $p$ is prime). Therefore $ba_i + 1$ is never congruent to $1$. Finaly note that $1\in A$. From all this we can deduce that there is some $i$ such that $ba_i + 1\notin A$. Let $C$ be corresponding number. Let $q$ be any of its prime divisors. Note that $q$ can't be from exceptional set since we added all of them through $b$. Thus $q$ is congruent to some $r_i$. But then $ba_i + 1\in A$, as product of primes from $R$ -- a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.