# Opposite Sets

1. Jun 29, 2011

### Char. Limit

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 $P$ and $Q$. Furthermore, say that $P \bigcup Q = \mathbb{N}$ and $P \bigcap Q = \emptyset$. 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. Jun 29, 2011

### gb7nash

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. -><-

3. Jun 29, 2011

### ideasrule

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.

4. Jun 29, 2011

### Char. Limit

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!

5. Jun 29, 2011

Correct.