# Another number theory

• October 17th 2013, 06:03 AM
RuyHayabusa
Another 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. :)
• October 17th 2013, 08:53 PM
SlipEternal
Re: Another number theory
Use a standard induction argument. Show that it is true for $n=3$. Assume it is true for all values up to $n$. Prove it is true for $n+1$.

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

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

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