Is a Number Prime if It Has No Factors Less Than Its Square Root?

[Char. Limit]

Homework Statement

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

Homework Equations

None!

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 M^1/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 N^1/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 N^1/2. Now, since N is composite, it has a factor A, which must be greater than N^1/2 for the assumption to hold. Therefore, A>N^1/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 < N^1/2. However, as A is a factor of N, N/A must be an integer B that is less than or equal to N^1/2. Therefore, N = A*B, and B is a factor of N. But B is less than N^1/2, which contradicts the original assumption. Therefore, if N is composite, N has a factor less than or equal to N^1/2

 

[gb7nash]

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?

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.

Assume that N is composite and that it has no factors less than or equal to N^1/2. Now, since N is composite, it has a factor A, which must be greater than N^1/2 for the assumption to hold. Therefore, A>N^1/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 < N^1/2. However, as A is a factor of N, N/A must be an integer B that is less than or equal to N^1/2. Therefore, N = A*B, and B is a factor of N. But B is less than N^1/2, which contradicts the original assumption. Therefore, if N is composite, N has a factor less than or equal to N^1/2

This should work. Another possibility is the following:

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

xy > N^1/2N^1/2 = N, so N > N. -><-

 

[ideasrule]

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?

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.

I ask because I'm trying to prove that if a natural number M has no factors less than or equal to M^1/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 N^1/2, but I don't know if the property can transfer this way. Help?

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.

 

[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 N^1/2 is prime? Thanks!

 

[gb7nash]

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 N^1/2 is prime? Thanks!

Correct.