1
$\begingroup$

I have absolutely no idea where to start, since I hardly ever have to use inequalities when it comes to working with primes. If anyone could help, I would really appreciate it. An example that shows what the inequality is trying to prove is: $p_1=2, \, p_2=3, \, p_3=5 \implies p_3 = 5 \leq p_1p_2+1 = 2.3+1$

Edit: It was very confusing and badly worded so I fixed it.

$\endgroup$
5
  • 1
    $\begingroup$ Are you familiar with Euclid’s proof of infinitely many primes? $\endgroup$ – J. W. Tanner Jul 2 '20 at 23:59
  • $\begingroup$ Hi, to me it does not seem clear what the actual inequality you want to show is. $\endgroup$ – Watercrystal Jul 3 '20 at 0:00
  • 1
    $\begingroup$ @Watercrystal: the OP is trying to show $$p_{n+1}\leq p_1\cdots p_n+1$$ where $p_n$ represents the $n^{th}$ prime. $\endgroup$ – Clayton Jul 3 '20 at 0:09
  • $\begingroup$ Ah, I read $p_n$ rather than $p_{n+1}$, my bad. $\endgroup$ – Watercrystal Jul 3 '20 at 0:11
  • $\begingroup$ @Watercrystal Yes, that's it $\endgroup$ – Kevin Catino Jul 3 '20 at 0:31
2
$\begingroup$

$p_1p_2\dots p_n+1$ cannot be divisible by $p_1, p_2, ..., $ or $p_n$,

because it leaves remainder $1$ when divided by any of those primes.

Therefore, $p_1p_2\dots p_n+1$ is prime or divisible by a prime greater than $p_n$.

In any case, there is another prime besides $p_1,p_2,...,p_n$ that is at most $p_1p_2\dots p_n+1$.

Therefore, $p_{n+1}\le p_1p_2\dots p_n+1$.


This is how Euclid proved there are infinitely many primes.

$p_1p_2\dots p_n$ is called the primorial.

$\endgroup$
1
  • 1
    $\begingroup$ Very clear explanation. Thank you so much! $\endgroup$ – Kevin Catino Jul 3 '20 at 0:52
1
$\begingroup$

This result also follows from Bertrand's postulate (now proved) which states that in the interval between any integer $k$ and $2k$ there is at least one prime. This also holds when $k$ is a prime, for example $p_n<p_{n+1}<2p_n$.

So if $p_1p_2\dots p_{n-1}\ge 2$ then $p_n<p_{n+1}<2p_n\le p_1p_2\dots p_{n-1}p_n<p_1p_2\dots p_{n-1}p_n+1$.

$\endgroup$
1
  • $\begingroup$ Interesting. Did not know about that. Thank you! $\endgroup$ – Kevin Catino Jul 3 '20 at 11:40

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.