Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook