If n is equal to or greater than 3 then prove that there's atleast one prime number between n and n!.

Help would be appreciated. :)

Printable View

- Oct 17th 2013, 05:03 AMRuyHayabusaAnother number theory
If n is equal to or greater than 3 then prove that there's atleast one prime number between n and n!.

Help would be appreciated. :) - Oct 17th 2013, 07:53 PMSlipEternalRe: Another number theory
Use a standard induction argument. Show that it is true for $\displaystyle n=3$. Assume it is true for all values up to $\displaystyle n$. Prove it is true for $\displaystyle n+1$.

So, $\displaystyle 3<5<3!=6$, so it is obviously true for $\displaystyle n=3$. Next, assume it is true up to $\displaystyle n$. How would you show it is true for $\displaystyle n+1$? There are two cases. Either $\displaystyle n+1$ is prime or there exists some prime number $\displaystyle n+1 < p < n!$. If it is the latter case, then you are done. So, suppose $\displaystyle n+1$ is prime. Let's consider the factors of $\displaystyle n!$. Since $\displaystyle n+1$ is prime, it is not a factor of $\displaystyle n!$, so any factor of $\displaystyle n!$ that is greater than $\displaystyle n$ is also greater than $\displaystyle n+1$. There are at most $\displaystyle n! - (n+1)$ factors that are greater than $\displaystyle n$ and at most $\displaystyle n-1$ factors that are greater than 1 and less than or equal to $\displaystyle n$. So, for $\displaystyle (n+1)!$, its factors that are greater than $\displaystyle n+1$ are the factors of $\displaystyle n!$ that are greater than $\displaystyle n+1$, those same factors times $\displaystyle n+1$, and also the factors of $\displaystyle n!$ that are no greater than $\displaystyle n$ multiplied by $\displaystyle n+1$. So, there are at most $\displaystyle 2(n!-(n+1)) + (n-1)$ factors of $\displaystyle (n+1)!$ that are greater than $\displaystyle n+1$. All that remains is to show that $\displaystyle (n+1)! - (n+1) > 2(n!-(n+1)) + (n-1)$.

This was only a very rough outline of what you need to prove. You would need to flesh it out.

Edit: Reading through this, this is not a terribly good method. Instead, you should probably use Euler's totient.

$\displaystyle \varphi(n) = n\prod_{p|n}\left(1-\dfrac{1}{p}\right)$

If $\displaystyle n+1$ is prime, $\displaystyle \varphi((n+1)!) = n\varphi(n!)$. If $\displaystyle \gcd((n+1)!,k)=1$ and $\displaystyle k>(n+1)$ then $\displaystyle k$ has a prime factor greater than or equal to $\displaystyle n+1$. So, you just need to show that $\displaystyle \varphi(n!)\ge 2$ for all $\displaystyle n\ge 3$. By assumption, $\displaystyle n+1$ is prime, so it is relatively prime to $\displaystyle n!$. Hence 1 and $\displaystyle n+1$ are both relatively prime to $\displaystyle n!$ making $\displaystyle \varphi(n!)\ge 2$. This means there are at least $\displaystyle 2n$ relatively prime numbers to $\displaystyle (n+1)!$. For every $\displaystyle n\ge 3$, $\displaystyle 2n>n+1$ implying that at least one of the numbers relatively prime to $\displaystyle (n+1)!$ is greater than $\displaystyle n+1$.