31
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ This is the same thing as saying the product of the elements of $P_m$ never equals the product of the elements of $P_n$ if $m\ne n$. The product is tabulated at oeis.org/A066838 (but I don't see anything there about this question). (Although, some code is given, that might help you look for examples) $\endgroup$ – Gerry Myerson Nov 25 '17 at 6:11
  • $\begingroup$ I think you should also post this conjecture on MathOverflow to draw more attention and see whether there is a solution. $\endgroup$ – josephz Nov 26 '17 at 7:21
  • 4
    $\begingroup$ @josephz As per your recommendation I just posted it on Mathoverflow as well. Here is the link : mathoverflow.net/questions/287011/… $\endgroup$ – Basanta Raj Pahari Nov 26 '17 at 15:36
  • $\begingroup$ If there was an integer $k$ with no primes between $48k$ and $54k$ then you would have $P_{48k} = P_{54k}$ $\endgroup$ – Henry Nov 27 '17 at 13:54
  • $\begingroup$ @Henry It turns out that the the claim is true at least for large integers. See a conditional proof by Lucia mathoverflow.net/questions/287011/… $\endgroup$ – Basanta Raj Pahari Nov 27 '17 at 14:09
6
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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