1. Not finding help here? Sign up for a free 30min 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!

Show that n is either a prime or the product of two primes

  1. Jun 8, 2015 #1
    1. The problem statement, all variables and given/known data

    Assume that n > 1 is an integer such that p does not divide n for all primes ≤ n1/3. Show that n is either a prime or the product of two primes. (Hint: assume to the contrary that n contains at least three prime factors. Try to derive a contradiction.)

    2. Relevant equations

    Divisibility, etc.

    3. The attempt at a solution

    Assume that there exists three primes such that n = p1p2p3.

    I suspect that you need to somehow show that there is a prime less than the cubic root that does divide n, but I'm not sure how to show it.
     
  2. jcsd
  3. Jun 8, 2015 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's difficult to give a hint without giving away the answer! That's a hint!
     
  4. Jun 8, 2015 #3

    wabbit

    User Avatar
    Gold Member

    Edit : PeroK is right.
     
  5. Jun 8, 2015 #4
    Well, I thought that I had to show through some clever means that one of the factors is less than the cubic root.
     
  6. Jun 8, 2015 #5

    wabbit

    User Avatar
    Gold Member

    Come on, think a little bit. Or rather, look - there's no clever trick, it's all here. Go back to the statement of the problem, what does it say ?
     
  7. Jun 8, 2015 #6
    Okay. I assume that it's three distinct prime factors and not the actual cubic root for some integer, e.g. 53 = 125. In that case, it's obviously contradicted. However, I can see that it implies that at least one of the primes is less than the cubic root. If they were larger, then you wouldn't get n.
     
  8. Jun 8, 2015 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    ##125 = 5^3## is not a contradiction to what's proposed.
     
  9. Jun 8, 2015 #8
    To the condition that p does not divide n for all primes ≤ n1/3? If not, then that's why I assume that it's three distinct primes.
     
  10. Jun 8, 2015 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    For ##n = 125## the primes ##\le n^{1/3}## are ##2, 3## and ##5##. ##125## is divisible by one of these (##p =5##) so does not meet the criteria for ##n##.
     
  11. Jun 8, 2015 #10
    It says that the prime numbers that divide n are necessarily above its cubic root.
     
  12. Jun 8, 2015 #11
    Ah, yes. That's right. I was going the wrong way.
     
  13. Jun 8, 2015 #12
    So I was correct in post #6?
     
  14. Jun 8, 2015 #13
    You must be tired and don't see it. As people said, there is very little room between the question and giving you the answer.
     
  15. Jun 8, 2015 #14
    Well, that and I am multitasking at work, so I'll probably see it when I get home.
     
  16. Jun 8, 2015 #15

    wabbit

    User Avatar
    Gold Member

    Now you know how efficient your multitasking is.
     
  17. Jun 8, 2015 #16
    And that I should probably stop going to bed after midnight.
     
  18. Jun 8, 2015 #17

    wabbit

    User Avatar
    Gold Member

    Ah yes I should try that too some time :smile:
     
  19. Jun 8, 2015 #18
    I must've read the problem too quickly. A product of three distinct primes would give you an integer larger than n because the primes that do divide n are larger than the cubic root. I sure hope that's right.
     
  20. Jun 8, 2015 #19

    wabbit

    User Avatar
    Gold Member

    Yes.
     
  21. Jun 8, 2015 #20
    Thanks for the help and sorry for the brainfart. This is actually a four-week class, so it's moving right along.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Show that n is either a prime or the product of two primes
  1. Prove n<prime<n! (Replies: 10)

Loading...