1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Uhh! help with this proof then x is prime .

  1. Apr 21, 2012 #1
    uhh! help with this proof """" then x is prime""".

    1. The problem statement, all variables and given/known data

    For a positive integer x≥2.

    "if x is not divisible by any positive integer n satisfying 2≤n≤√x then x is a prime number"

    a) show that the above statement is true .

    b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??




    2. Relevant equations



    3. The attempt at a solution

    Well firstly I really have problems with proofs in general, but

    x≥4

    so x can be [4,5,6,7,.....∞)

    so by definition of prime number x--> x/x and x/1

    but I really dont know how to approach this
    I know its true because n= [2,3,4,5...∞)
    and so the only numbers not possibly divisible by n are primes, Since n can be any positive integer ≥2, and Since x≠1.

    But how do I put it in mathematical terms??
    HELP!
     
  2. jcsd
  3. Apr 21, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: uhh! help with this proof """" then x is prime""".

    Try and prove the contrapositive. If x is NOT prime then there IS a positive integer satisfying 2≤n≤√x that divides x.
     
  4. Apr 21, 2012 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: uhh! help with this proof """" then x is prime""".

    An integer x>1 is composite if there exists some number 1<n<x that divides n. The integer x is prime if not such number n exists. What this is this theorem is telling you is that you don't have to look at all integers between 2 and x-1 (inclusive). You only need to look at those between 2 and √x (inclusive).

    Hint: Suppose n is an integer that divides x. In other words, m=x/n is an integer. What can you say about m if √xn<x?
     
  5. Apr 21, 2012 #4
    Re: uhh! help with this proof """" then x is prime""".

    Well mn=x so x is not a prime if this condition is satisfied.

    and m can be any positive integer >1 since m=x/n which is greater than 1 since n<x, and n,x are positive integers.

    But I dont really understand when exactly this condition satisfies, namely, mn=x, Since to me mn could be less than, equal, or greater than x.

    Since m>1 and n<x. There are values of x,m,n that satisfy all three conditions ie, <,=,>.
     
  6. Apr 21, 2012 #5
    Re: uhh! help with this proof """" then x is prime""".

    On second thoughts m>x so since n≥2 then mn>x.

    So I think this tells me that if x does not divide some n≥2 then x is not prime?? Although I think for this to be true I need the eqn to be mn=x? Im confused.
     
  7. Apr 21, 2012 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: uhh! help with this proof """" then x is prime""".

    Surely this is not what you meant to say? Any x, prime or not, divides 2x, for example.

    It is true that if x is not divisible by some [itex]n\ge 2[/itex] (except x itself) then x is prime.

    If x= mn and [itex]m>\sqrt{x}[/itex], what can you say about n?

    As for "b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??",
    consider x= 9.
     
  8. Apr 21, 2012 #7
    Re: uhh! help with this proof """" then x is prime""".

    if x=mn and m>√x

    then all I can say from this statement is that mn is > √x. And that n is <√x, Since mn=x. I'm still really lost?
     
    Last edited: Apr 21, 2012
  9. Apr 21, 2012 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: uhh! help with this proof """" then x is prime""".

    If x is composite, we can factor it as x=mn we have two possibilities
    1) m< √x
    2) n< √x

    In both cases, we see that if x is composite, it is divisible by a number which is no larger than √x, which is exactly what you wanted to prove (after you change some strict inequalities to weak inequalities)
     
  10. Apr 22, 2012 #9
    Re: uhh! help with this proof """" then x is prime""".

    Ok thanks Office Shredder and others that helped...

    so does this proof look correct now.

    given ---> 2≤n≤√x and x≥2

    So n≥2 from above inequality.

    Suppose x is not prime, then, by definition of a prime

    m = x/n for some integers m and x,n both≥2

    hence, x=mn

    Now either n< √x or m<√x or m=√x iff n=√x

    In either case x/m or x/n

    But if x is prime, by definition, x cannot divide m or n where m,n≥2

    Hence m is prime iff x does not divide n where 2≤n≤√x

    proof finished.

    and for part b)

    let x=9

    therefore, 2≤n<3

    Now x is prime iff x does not divide n for some integer n satisfying above inequality.

    but 9 does not divide 2 and when x =9, n must =2 (satisfying the above inequality).

    Hence x is prime. Contradiction. 9 is not prime. Therefore above inequality does not hold.
     
    Last edited: Apr 22, 2012
  11. Apr 22, 2012 #10

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: uhh! help with this proof """" then x is prime""".

    I have no idea what you are trying to do. All you need to note is that 9 is not prime and [itex]\sqrt{9}=3[/itex]. "[itex]2\le x< \sqrt{9}= 3[/itex]" is true only for x= 2 and 2 does not divide 9. End of counter example.
     
  12. Apr 22, 2012 #11
    Re: uhh! help with this proof """" then x is prime""".

    Ok thanks, undestood!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Uhh! help with this proof then x is prime .
  1. Prime proofs (Replies: 3)

  2. Proof (primes) (Replies: 1)

  3. Proof about primes (Replies: 1)

Loading...