Results 1 to 2 of 2

Math Help - Another number theory

  1. #1
    Junior Member
    Joined
    Feb 2013
    From
    US
    Posts
    37
    Thanks
    1

    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
    Joined
    Nov 2010
    Posts
    1,865
    Thanks
    728

    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.
    Last edited by SlipEternal; October 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: July 8th 2011, 06:09 PM
  3. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  4. number theory
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: August 10th 2008, 08:44 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum