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!

Every positive integer except 1 is a multiple of at least one prime.

  1. May 19, 2014 #1

    s3a

    User Avatar

    1. The problem statement, all variables and given/known data
    The problem (and its solution) are attached in TheProblemAndSolution.jpg. Specifically, I am referring to problem (c).

    2. Relevant equations
    Set theory.
    Union.
    Integers.
    Prime numbers.

    3. The attempt at a solution
    I see how we have all multiples of all prime numbers in the union of the sets, but I can't see how “every positive integer except 1 is a multiple of at least one prime number”. If I could intuitively grasp the sentence I just quoted, then I can see how to get to the final result.

    Any help in getting me to intuitively understand the part I quoted would be greatly appreciated!
     

    Attached Files:

  2. jcsd
  3. May 19, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Isn't that a trivial statement given the definition of prime numbers?
    Hint: look at the factors of the number.
     
  4. May 19, 2014 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's not TOTALLY trivial. If a number ##n## isn't prime then it can be factored into ##n=ab## where neither ##a## nor ##b## is one. If neither one is prime then they are both composite and ##a<n##. Then factor ##a##. You need to argue that this can't go on forever. It's sort of intuitively obvious but to write a formal proof you need to say that there is not an infinite sequence of decreasing positive integers. There is a little meat here.
     
  5. May 20, 2014 #4

    s3a

    User Avatar

    Thanks for the replies.

    I think I now understand it intuitively. Basically, prime numbers are numbers that can't be factored further (except for factors of 1 and the number itself), and all composite numbers can be divided by a prime number, since a prime number is at least one of the multiplicands of the factored form of the composite numbers, right?

    Assuming I've understood the intuitive argument, I would like to move to the formal proof, so, Dick or mfb (or anyone else), could you please show me how you would (formally) prove that “every positive integer except 1 is a multiple of at least one prime number”?
     
  6. May 20, 2014 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I am aware of that, and still consider this as trivial. You can use induction as well.

    Right.
    Dick gave you one approach, induction is another possible way to prove it.
     
  7. May 20, 2014 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I agree with mfb. If you think you understand it intuitively, you should start the proof, not us.
     
    Last edited: May 20, 2014
  8. May 21, 2014 #7

    s3a

    User Avatar

    Well, is it formal to say the following?:

     
  9. May 21, 2014 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's not very good. Use mfb's suggestion and induction. Suppose all integers less than or equal to N have a prime factor. Use that to prove all integers less than or equal to N+1 have a prime factor. Think about it and think about induction.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted