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!

Opposite Sets

  1. Jun 29, 2011 #1

    Char. Limit

    User Avatar
    Gold Member

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

    Prove that if a given natural number M has no factors less than or equal to M1/2, then M is prime.

    2. Relevant equations

    None!

    3. The attempt at a solution

    So I was wondering, say I have two sets [itex]P[/itex] and [itex]Q[/itex]. Furthermore, say that [itex]P \bigcup Q = \mathbb{N}[/itex] and [itex]P \bigcap Q = \emptyset[/itex]. Now, can I assume that if all elements of set P obey a certain property, then any element of N that does not obey that property belongs to Q?

    I ask because I'm trying to prove that if a natural number M has no factors less than or equal to M1/2 then M is prime. I'm hoping to use a proof that I almost have complete that if a natural number N is composite, then N has a factor less than or equal to N1/2, but I don't know if the property can transfer this way. Help?

    EDIT: Also, my proof for the latter statement, if it helps:

    Assume that N is composite and that it has no factors less than or equal to N1/2. Now, since N is composite, it has a factor A, which must be greater than N1/2 for the assumption to hold. Therefore, A>N1/2. Now, by inverting the two sides of the equation, we can see that A-1<N-1/2. Multiplying both sides by N, we get that N/A < N1/2. However, as A is a factor of N, N/A must be an integer B that is less than or equal to N1/2. Therefore, N = A*B, and B is a factor of N. But B is less than N1/2, which contradicts the original assumption. Therefore, if N is composite, N has a factor less than or equal to N1/2
     
    Last edited: Jun 29, 2011
  2. jcsd
  3. Jun 29, 2011 #2

    gb7nash

    User Avatar
    Homework Helper

    Yes. P and Q are mutually exclusive and their union is N (and they're each a subset of N). It is given that every member of P has a certain property. Now, a member of N does not have this property. This member must either be in P or Q. Since every member of P has this property, you must conclude that the member is in Q.

    This should work. Another possibility is the following:

    Assume that N is composite and that it has no factors less than or equal to N1/2. So N = xy, where x > N1/2 and y > N1/2. So:

    xy > N1/2N1/2 = N, so N > N. -><-
     
  4. Jun 29, 2011 #3

    ideasrule

    User Avatar
    Homework Helper

    Yes. I suppose you're trying to show that a number is either composite or prime, but I don't think you need to prove it--it's basic enough that you can take it as an axiom.

    Do you have to use set theory? I would just say that M is either prime or composite. We know it can't be composite because that would violate the theorem you just proved, so it must be prime.
     
  5. Jun 29, 2011 #4

    Char. Limit

    User Avatar
    Gold Member

    Excellent! Also, great proof there, GB7... I hadn't even considered that.

    So using the theorem I proved in post 1, I can just say that any number N without a factor less than or equal to N1/2 is prime? Thanks!
     
  6. Jun 29, 2011 #5

    gb7nash

    User Avatar
    Homework Helper

    Correct.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Opposite Sets
  1. In the set? (Replies: 2)

Loading...