4
$\begingroup$

"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; $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).

  • 0
    @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.2012-10-06

2 Answers 2

2

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

  • 1
    Again, "No!" - because their product exceeds the integer, which is impossible.2012-10-06
2

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

  • 0
    Thanks i fixed the first one.2012-10-06