Results 1 to 2 of 2

Thread: Another number theory

  1. #1
    Junior Member
    Feb 2013

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Nov 2010

    Re: 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$.
    Last edited by SlipEternal; Oct 17th 2013 at 08:40 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Using group theory to prove results in number theory
    Posted in the Math Philosophy Forum
    Replies: 6
    Last Post: May 12th 2012, 01:34 AM
  2. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jul 8th 2011, 06:09 PM
  3. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  4. number theory
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Aug 10th 2008, 08:44 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags

/mathhelpforum @mathhelpforum