# If $m$ is odd and not prime

Prove that it must have at least one prime factor $$a \leq \sqrt{m}$$ and that all of its prime factors must be a maximum of $$m/3$$?

Note: I have been able to prove that every non-prime $$m$$ has at least one prime divisor. Am I correct in assuming the proof of the first part will be similar? What I have tried is expressing $$m$$ in terms of two numbers $$a_{1}, a_{2}$$ and assuming one of them to be greater than $$\sqrt{m}$$ to reach a contradiction but it seems incomplete.

• For the contradiction part, shouldn't you assume that all prime factors are greater than $\sqrt{m}$? Since the number has a prime divisor, it must be written as a product of two or more such primes... – Macrophage Jan 21 '19 at 2:09
• Note if $n = a_1a_2$ then $\frac n{a_1} = a_2$ (assuming everything is positive). If $a_1 > \sqrt n$ what does that say about $a_2$? – fleablood Jan 21 '19 at 2:32

You are essentially there. As with the sieve of Eratosthenes, a composite number $$n$$ must have a factor less than $$\sqrt n$$ because two numbers larger than that will multiply to something greater than $$n$$. In you case the minimum factor is $$3$$ because the number is odd, so the maximum factor is at most $$\frac n3$$
Let $$n = a*b$$.
Either $$a \le \sqrt n$$ or $$a > \sqrt n$$.
But if $$a > \sqrt n$$.
Then $$b = \frac na < \frac n{\sqrt n} = \sqrt n$$.