10
$\begingroup$

I want a number that has a prime factorization that contains all prime numbers less than that number (besides $2$), anyone with an answer please show a proof.

I have made a little progress, if this number exists, then it is one less than a prime number.
proof:
make a list of all the primes less than $n$ $\{P_1,\space P_2,\space P_3,\cdots\}$
$n+1$ is not a factor of any of these primes so it ether is a prime or has a prime that our list missed and since the list contains all primes less than $n$, $n+1$ must be prime.

and more evidence that suggests this exists is the proof that any arbitrary prime gap exists. if $n!+1$ is prime then the prime gap between $n!+1$ and the next prime is at least $n-1$ because:
$n!+2$ is a multiple of $2$ and
$n!+3$ is a multiple of $3$ and so-on until
$n!+n$ which is a multiple of $n$

any more help would be appreciated

$\endgroup$
7
  • 6
    $\begingroup$ Bertrand's postulate? $\endgroup$ Jun 23 '19 at 19:35
  • $\begingroup$ @LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self $\endgroup$
    – spydragon
    Jun 23 '19 at 19:44
  • $\begingroup$ Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants. $\endgroup$ Jun 23 '19 at 19:48
  • $\begingroup$ You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$) $\endgroup$ Jun 23 '19 at 19:51
  • $\begingroup$ @MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works $\endgroup$
    – spydragon
    Jun 23 '19 at 19:52
17
$\begingroup$

This is impossible. For every $n>1$, we have gcd$(n,n-1)=1$. Since there is a prime dividing $n-1$, the result follows.

Edit : I should have assumed $n>2$ since I need a prime divisor of $n-1$.

$\endgroup$
12
  • $\begingroup$ Well, $n=2$ actually works ... $\endgroup$ Jun 23 '19 at 19:51
  • $\begingroup$ @HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$. $\endgroup$
    – Levent
    Jun 23 '19 at 19:53
  • $\begingroup$ what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime? $\endgroup$
    – spydragon
    Jun 23 '19 at 19:56
  • $\begingroup$ @spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$). $\endgroup$
    – Levent
    Jun 23 '19 at 19:57
  • 1
    $\begingroup$ ok, so $n-1$ must be prime therefore $n$ must contain $n-1$, which cannot happen. thanks now it makes sense. $\endgroup$
    – spydragon
    Jun 23 '19 at 20:05
11
$\begingroup$

To make Lord Shark's comment explicit:

Let $n$ be composite and let $p$ be its largest prime factor. Then certainly $n\ge 2p$. By Bertrand's postulate, there exists a prime $q$ between $p$ and $2p$, hence there exist primes below $n$ that do not divide $n$.

$\endgroup$
2
  • $\begingroup$ unless that prime $q$ is in between $n$ and $2p$ $\endgroup$
    – spydragon
    Jun 23 '19 at 19:54
  • $\begingroup$ @spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$. $\endgroup$ Jun 24 '19 at 0:29
4
$\begingroup$

A small dilation on the answer of Levent: Let us imagine there is such a number and there are $n$ primes smaller than that number. Then the smallest number that contains all of those primes is the product of all of those primes, which is called a primorial and is denoted $p_n\#$.

Your question in effect asks, "Is it ever the case that $p_{n+1}>p_n\#$?"

We can start by considering the number $p_n\#+1$. Since every one of the first $n$ primes divides $p_n\#$, and none of them divide $1$, we conclude none of them can divide $p_n\#+1$. So that number must either be a prime or have prime factors. If it has prime factors, they must be other than any of the first $p_n$, and those factors must be smaller than $p_n\#$, and larger than $p_n$ itself. In this case, the prime next larger than $p_n$ would have to be smaller than $p_n\#$ and the answer to your question would be "No". So that forces us to consider that $p_n\#+1$ is in fact a prime, and postulate that it is the prime next larger than $p_n$, i.e. $p_{n+1}$. If it were ever the case that $p_{n+1}=p_n\#+1$, that would be the only possible way to answer your question in the positive.

Here is how Levent's answer sinks that ship. We must now consider the number $p_n\#-1$. As in the case of $p_n\#+1$, each $p_n$ divides $p_n\#$ but none of them divide $1$, so $p_n\#-1$ must either be a prime or have prime factors, in either instance smaller than $p_n\#$. That being the case, $p_n\#+1$ cannot be the prime next larger than $p_n$.

Levent's answer stands on its own in answering your question in the negative. However, the excursion taken here shows that Levent's answer also undercuts the only reasonable candidate for the kind of number you postulate.

$\endgroup$
3
$\begingroup$

Look at it from the other side, the "half-primorials" (see http://oeis.org/A070826) of which the first composite one is 15, which as you know is $3 \times 5$.

But it's not divisible by 7, 11 or 13. Multiply those in and you get 15015. But that's not divisible by 17, 19, 23, 29, ..., 14983 or 15013. Multiply those in... actually, don't, you might tie up your computer for too long.

$\endgroup$
1
$\begingroup$

$n=2\cdot{n\over 2}$ at most for the factoring to work out. But, by that very logic, applying it with Bertrand's Postulate $$\exists c\in\mathbb{P},{n\over 2}\leq c\leq n\implies c\mid n \land 2\nmid n$$ contradicting the possibility of an n with the property of divisibility by 2 working. which then says n doesn't include all primes less than it.

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