"Every composite positive integer has at least one prime factor less than the square root of the integer."

Proof by contradiction:

If $p_1, p_2, ..., p_n$ are prime factors of $x$ greater than $\sqrt{x}$. Then the following holds for $∀$ $i,j∈ℕ$ $i,j<n$; $$p_i > \sqrt{x}$$ $$p_j > \sqrt{x}$$ $$p_ip_j > x$$ $$CONTRADICTION!$$ The question I have now is that; "Is it possible for a positive integer to have more than one prime factor greater than its square root?"

Considering two prime factors of $x$, $p_1$ and $p_2$ greater than $\sqrt{x}$ using the same reasoning above we have $$p_1p_2 > x$$ $$CONTRADICTION!$$ This means a positive composite integer can only have one (but may not have any) prime factor greater than its square root.

This is only a proof of what I think is right but I still have a weird feeling that I'm missing something because I've not come across a theorem like this before. The first one I wrote above is a very popular one, and if what the answer I gave is valid then how come it is not popular(unless it isn't true).

  • $\begingroup$ This is precisely were a famous primality test comes from (i.e. $n$ is prime if no integers $\leq\sqrt{n}$ divide $n$). I don't understand what your question is though, it seems you have just laid out some facts about prime factorisation... $\endgroup$ – user39572 Oct 4 '12 at 23:28
  • 3
    $\begingroup$ Is there any question here? (Except the one you immediately answered youself). $\endgroup$ – Henning Makholm Oct 4 '12 at 23:39
  • 1
    $\begingroup$ Your argument only works for integers with two prime factors. But there are plenty of integers not of that form. $\endgroup$ – Bill Dubuque Oct 4 '12 at 23:53
  • $\begingroup$ @BillDubuque well a positive composite integer always has at least two prime factors and if you multiply any of the two prime factors, the result must be less than or equals to the number. $\endgroup$ – user31280 Oct 6 '12 at 0:30
  • $\begingroup$ @HenningMakholm I just have the feeling that the answer I gave is somewhat invalid. I've read a lot of books and I've failed to come across a statement like the one I stated last. I only wrote my proof out to see if someone can point something I'm missing out. $\endgroup$ – user31280 Oct 6 '12 at 0:38

What you have shown is this:

If an integer has two prime factors, then at least one of them does not exceed the square root of the integer. So the answer to your question is "No."

  • $\begingroup$ What if a positive integer has three prime factors, can two of them exceed the square root of the integer? This exactly is my question! $\endgroup$ – user31280 Oct 6 '12 at 0:33
  • 1
    $\begingroup$ Again, "No!" - because their product exceeds the integer, which is impossible. $\endgroup$ – marty cohen Oct 6 '12 at 22:29

Edit: The quoted material has changed. We leave the old answer, and give a new answer appropriate for the changed question.

New answer: The result is does not hold. If $n$ is a prime, like $17$, then $n$ has a prime factor, namely $n$, which is greater than $\sqrt{n}$, but has no prime factor $\le \sqrt{n}$.

So let us change the question a bit. We show that if $n$ is composite and has a prime factor $p_1\gt \sqrt{n}$, then $n$ has a prime factor $p_2\lt \sqrt{n}$.

Since $n$ is composite, $n\ne p_1$. Let $q=n/p_1$. Then $q\lt \sqrt{n}$, for if $n\ge \sqrt{n}$, then $qp_1\gt (\sqrt{n})(\sqrt{n})=n$. This is impossible, since $qp_1=n$.

Also, $q\gt 1$, for if $q=1$ then $n=p_1$, contradicting the fact that $n$ is composite. It follows that $q$ has a prime divisor $p_2$, which is necessarily $\le q$, and hence $\lt \sqrt{n}$.

Old answer: First, a comment about the quotation that the question starts with. Usually, if $n$ is a positive integer, the numbers $1$ and $n$ are considered to be factors of $n$. So if $n$ is any positive integer greater than $1$, then $n$ has a factor less than $\sqrt{n}$, namely $1$.

So the statement should be reworded to say "Suppose that a positive integer $n$ has a prime factor $p\gt \sqrt{n}$. Then $n$ has a factor other than $1$ which is $\le \sqrt{n}$."

In fact, let $m$ be any factor of $n$, not necessarily prime, such that $m\ne n$ and $m\gt\sqrt{n}$. Then $n$ has a factor $q$ such that $1\le \sqrt{n}$.

For just let $q=\dfrac{n}{m}$. Then $q\ne 1$, and $qm=n$. But if $q\gt \sqrt{n}$, then $qm\gt (\sqrt{n})(\sqrt{n})=n$. This is impossible, since $qm=n$.

  • $\begingroup$ Thanks i fixed the first one. $\endgroup$ – user31280 Oct 6 '12 at 0:43

Your Answer

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