1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Macrophage Jan 21 '19 at 2:09
  • 1
    $\begingroup$ 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$? $\endgroup$ – fleablood Jan 21 '19 at 2:32
4
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.