A conjecture regarding prime numbers

Question

For $n,m \geq 3$, define $ P_n = \{ p : p$ is a prime such that $ p\leq n$ and $ p \nmid n \}$ .

For example : $P_3= \{ 2 \}$ $P_4= \{ 3 \}$ $P_5= \{ 2, 3 \}$, $P_6= \{ 5 \}$ and so on.

Claim: $P_n \neq P_m$ for $m\neq n$.

While working on prime numbers I formulated this problem and it has eluded me for a while so I decided to post it here. I am not sure if this is an open problem or solved one. I couldn't find anything that looks like it. My attempts haven't come to fruition though I have been trying to prove it for a while. If $m$ and $n$ are different primes then it's clear. If $m \geq 2n$, I think we can find a prime in between so that case is also taken care of. My opinion is that it eventually boils down to proving this statement for integers that share the same prime factors. My coding is kind of rusty so would appreciate anybody checking if there is a counterexample to this claim. Any ideas if this might be true or false? Thanks.

Update: Lucia has provided a conditional proof of the claim for large integers on mathoverflow. Please see

https://mathoverflow.net/questions/287011/a-conjecture-regarding-prime-numbers/287039#287039

Answer 1

Let $m,n\ge 3$ be given and suppose that $m\neq n$. Without loss of generality, we can say that $n>m$.

Assume there are primes between $m$ and $n$. Let $p$ be the largest prime number with $n>p\ge m$. It is clear that $p\not\in P_m$. If $p\not\in P_n$, we must have $p\mid n$, so $n\ge 2p$. However, Betrand's postulate tells us there is at least one prime inbetween $p$ and $2p$, contradicting the definition of $p$. We conclude that $p\in P_n$ and $P_n\neq P_m$.

Now, say there are no primes between $n$ and $m$. Now, we have $P_n=P_m$ if and only if $rad(n)=rad(m)$. Say $rad(n)=r$. So now we have $k,l\in\mathbb{N}$ with $n=kr$ and $m=lr$. This is the hard part. (In fact it's very hard, as shown in an answer to the repost on Mathoverflow)

Answer 2

From the set theory perspective, let's note $$P \overset{\text{def}}{=}\{p \in \mathbb{N} \mid p \text{ - prime}\}$$ $$P_{\leq n} \overset{\text{def}}{=} \{p \in P \mid p \leq n \}$$ $$M_n \overset{\text{def}}{=} \{p \in P \mid p \mid n\}$$ $\color{red}{M_n \ne \varnothing, \forall n\geq2}$. Then, it's easy to show $$P_n=P_{\leq n} \setminus M_n \tag{1}$$ $$M_n \subset P_{\leq n} \tag{2}$$ Now, let's assume $\exists n \ne m$, in fact we can assume $\color{red}{n>m}$, such that $\color{blue}{P_n = P_m}$ then $$P_{\leq n} \setminus M_n = P_{\leq m} \setminus M_m \overset{(2)}{\Rightarrow} P_{\leq n}=\left(P_{\leq n} \setminus M_n \right) \bigcup M_n=\left(P_{\leq m} \setminus M_m \right) \bigcup M_n$$ or $$P_{\leq n}=\left(P_{\leq m} \setminus M_m \right) \bigcup M_n \tag{3}$$ given $\color{red}{P_{\leq m} \subset P_{\leq n}}$ and $(2)$, it's easy to deduct that $$M_m \subset M_n \tag{4}$$

There are 3 possible cases to exploit with $(4)$:

---

Case 1 (incomplete). $\forall k \in M_n, k\in M_m$ or $M_n=M_m$ (like $n=2^2 \cdot 3^2, m=2 \cdot 3$ for example), then $\color{green}{P_{\leq n} = P_{\leq m}}$. If $m=\prod\limits_{i} p_{k_i}^{\alpha_i}$ then $n=\prod\limits_{i} p_{k_i}^{\beta_i}$ with $\beta_i \geq \alpha_i$ and at least one $\beta_{i^{*}} > \alpha_{i^{*}}$. Since all $p_i \geq 2$ this means $$m < 2m \leq n$$ From Bertrand postulate there is $p^{*}$-prime in between $m$ and $2m$ with $p^{*} \notin P_{\leq m}$ and $p^{*} \in P_{\leq n}$, thus $\color{green}{P_{\leq m} \ne P_{\leq n}}$ - contradiction.

Obviously $\beta_i \geq \alpha_i$ doesn't cover all the cases, e.g. $n=2 \cdot 3^2, m=2^2 \cdot 3$.

---

Case 2. $\exists k \in M_n, k\notin M_m$ and $k \in P_{\leq m}$. Since $k \in P_{\leq m}$ and $k\notin M_m$ then $k \in P_m=P_{\leq m} \setminus M_m$, but because $k \in M_n$ and $k \in P_{\leq n}$ then $k \notin P_n=P_{\leq n} \setminus M_n$. Thus $\color{blue}{P_n \ne P_m}$ - contradiction.

---

Case 3. $\exists k \in M_n, k\notin M_m$ and $k \notin P_{\leq m}$. Then $n=k\cdot t \geq k > m$

• if $t=1$ then (given $k$ is prime) $n$ is prime and $P_n$ will contain all the prime factors of $m$, but $P_m$ will not contain prime factors of $m$, thus $\color{blue}{P_n \ne P_m}$ - contradiction.
• if $t\geq2$ then between $n$ and $\frac{n}{2}$ exist a prime $p^{*}$ (proposition 1, below). Because $p^{*}>\frac{n}{2}=\frac{kt}{2} \geq k>m \Rightarrow p^{*} \notin P_m$. Also $p^{*} \nmid n$, otherwise $n=qp^{*}\geq 2p^{*} > n$. Thus $p^{*} \in P_n$ and as a result $\color{blue}{P_n \ne P_m}$ - contradiction.

---

Proposition 1. $\forall n \geq 3$ $\exists p$ - prime s.t. $\frac{n}{2}<p<n$

Let's take $k=\left \lfloor \frac{n}{2} \right \rfloor+1 \geq \frac{n}{2}$. Bertrand postulate says $\exists p$ - prime s.t. $k < p < 2k-2$ or $$\color{red}{\frac{n}{2}\leq k} < p < 2k-2=\color{blue}{2 \left \lfloor \frac{n}{2} \right \rfloor \leq n} \tag{5}$$ simply because:

• for $n=2r$ (even) we have $\color{red}{\frac{n}{2}=r < r+1=\left \lfloor \frac{n}{2} \right \rfloor+1=k}$ and $\color{blue}{2 \left \lfloor \frac{n}{2} \right \rfloor=2r=n}$
• for $n=2r+1$ (odd) we have $\color{red}{\frac{n}{2}=r+\frac{1}{2}<r+1=\left \lfloor r+\frac{1}{2} \right \rfloor+1=\left \lfloor \frac{n}{2} \right \rfloor+1=k}$ and $\color{blue}{2 \left \lfloor \frac{n}{2} \right \rfloor=2 \left \lfloor r+\frac{1}{2} \right \rfloor=2r<2r+1=n}$

Bertrand postulate says $(5)$ is true for $k>3$ or $n >4$. For $n=4$ we have $\frac{4}{2}<3<4$ and for $n=3$ we have $\frac{3}{2}<2<3$.