Results 1 to 4 of 4

Math Help - Prime number

  1. #1
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1

    Prime number

    Prove that there is a prime number p such that n < p < n! for all n <2. n is an integer.
    I'm not allowed to use Prime number theorem or this kind of stuff. Should be simple, but you must think of it!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let q_n be the greatest prime, less or equal than n, then 2^{q_n}-1 can only be divisible by primes greater than q_n ( see here), thus,let p be a prime number satisfying p|(2^{q_n}-1) then p>n\geq{q_n} (1) ( since otherwise we'd contradict our definition of q_n)

    From n\geq{q_n} it follows that n!>2^n-1 \geq 2^{q_n}-1 if n>3 ( show by induction that n!>2^n for all n>3 )

    Thus, since p|(2^{q_n}-1) we have n!>2^{q_n}-1\geq{p} (2)

    (1) and (2) complete the proof for n>3
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by vincisonfire View Post
    Prove that there is a prime number p such that n < p < n! for all n > 2. n is an integer.
    For n=3 we can take p=5. Assume that n>3.

    Suppose to the contrary there is no prime p with n<p<n!.

    Let p_1,\ldots,p_r be all the primes less than or equal to n and consider k=p_1\cdots p_r+1.

    k is greater than 1 and not divisible by any of the primes p_1,\ldots,p_r; hence k must be divisible by a prime q\notin\{p_1,\ldots,p_r\}.

    It follows that n!\leqslant q\leqslant k=p_1\cdots p_r+1. But p_1\cdots p_r\mid n!, say n!=bp_1\cdots p_r.

    Hence bp_1\cdots p_r\leqslant p_1\cdots p_r+1 \Rightarrow (b-1)p_1\cdots p_r\leqslant1. This can only hold if the LHS is 0, i.e. b=1 \Rightarrow n!=p_1\cdots p_r. This is impossible for n\geqslant4 (contradiction).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by JaneBennet View Post
    For n=3 we can take p=5. Assume that n>3.

    Suppose to the contrary there is no prime p with n<p<n!.

    Let p_1,\ldots,p_r be all the primes less than or equal to n and consider k=p_1\cdots p_r+1.

    k is greater than 1 and not divisible by any of the primes p_1,\ldots,p_r; hence k must be divisible by a prime q\notin\{p_1,\ldots,p_r\}.

    It follows that n!\leqslant q\leqslant k=p_1\cdots p_r+1. But p_1\cdots p_r\mid n!, say n!=bp_1\cdots p_r.

    Hence bp_1\cdots p_r\leqslant p_1\cdots p_r+1 \Rightarrow (b-1)p_1\cdots p_r\leqslant1. This can only hold if the LHS is 0, i.e. b=1 \Rightarrow n!=p_1\cdots p_r. This is impossible for n\geqslant4 (contradiction).
    I think you might make your proof a little simple though not necessary.
    Let p_1,...,p_r be the primes less than or equal to n.
    Define k=p_1\cdot ... \cdot p_r + 1 and we see there is a prime divisor q \not \in \{ p_1,...,p_r \}.
    Then, n < q \leq k < n!.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  2. Prime number 2
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 1st 2010, 04:03 AM
  3. Prime number
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 1st 2010, 03:53 AM
  4. Replies: 1
    Last Post: September 2nd 2009, 08:31 AM
  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