Thread: Property of Primes

1. Property of Primes

Q: Prove this fact: If |m| > 1, and if m has no divisor d with $\displaystyle 1 < d \leq \sqrt{|m|}$ then m must be prime.

One idea I had was:
Suppose m is not prime then m must have a divisor d with $\displaystyle 1 < d \leq \sqrt{|m|}$.

Also, I've been trying to think of a useful contradiction to use but I can't come up with any.

2. Hi.
Let us work with natural numbers (so |m|=m) because e.g. -3 satisfies the assumption but is not a prime.
Suppose that m>1 has no proper divisor d such that 1<d<=sqrt(m), and that m is not prime.
Then there is some divisor k of m, k distinct from m and 1.
So m=k*j, where j is also distinct from m and 1.
By hypothesis we have k>sqrt(m), j>sqrt(m).
Multiplying these inequalities we get k*j > sqrt(m)*sqrt(m) = m, which contradicts m=k*j.

3. Just wanted to add something I saw in a textbook, which seems to be related to this property.

If a number M is composite, then one of it's prime divisors $\displaystyle p \leq \sqrt{M}$

The proof is similar

Assume that M is composite and that it's prime divisors are all greater than the square root of M. So when you multiply the prime divisors, the product will be greater than M, which is a contradiction. So a prime divisor must be less than or equal to the square root of M