Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I remember reading this somewhere but I cannot locate the proof.

share|improve this question
1  
Greatest prime factor? $\sqrt6 = 2.44948974..$ but the greatest prime factor of $6$ is $3$, so it's not true. Or are you asking something else? –  Mikko Korhonen Jan 26 '12 at 20:59
    
What does greatest prime factorization mean? And there certainly can be a prime factor $p|n$ with $p>\sqrt{n}$; take $3|6,3>\sqrt{6}$ for example. Perhaps you mean there is always a nonunit $d|n$ with $d\le n$? –  anon Jan 26 '12 at 21:01
6  
Perhaps you are looking for a proof of: if $n$ is composite, then there is at least one prime $p \le \sqrt{n}$ which divides $n$. –  Aryabhata Jan 26 '12 at 21:04
    
Short proof of @Aryabhata's statement: If $n=ab$ and $a \leq b$ then $a^2 \leq ab=n$. –  Fredrik Meyer Jan 26 '12 at 21:52
add comment

4 Answers

up vote 8 down vote accepted

It is the smallest prime factor that is less than or equal to $\sqrt{n}$, unless $n$ is prime. One proof is as follows: Suppose $n=ab$ and $a$ is the smallest prime factor of $n$, and $n$ is not prime. Since $n$ is not prime, we have $b\ne1$. Since $a$ is the smallest prime factor of $n$, we have $a\le b$. If $a$ were bigger than $\sqrt{n}$, then $b$ would also be bigger than $\sqrt{n}$, so $ab$ would be bigger than $\sqrt{n}\cdot\sqrt{n}$. But $ab=n$.

share|improve this answer
add comment

As stated, what you wrote is false: for example, $5$ is a prime factor of $15$, but the square root of $15$ is less than $4$. Not to mention the fact that if $n$ is prime, then its only prime factor is $n$ itself, certainly larger than $\sqrt{n}$.

What is true is that if $n$ is not prime and not equal to $1$, then it must have a prime factor less than or equal to $\sqrt{n}$.

We can prove this by strong induction: assume the result holds for all $k\lt n$, if $k\gt 1$, then either $k$ is a prime, or it has a prime factor that is no more than $\sqrt{k}$. We wish to prove the same is true for $n$.

If $n$ is prime, we are done. If $n$ is not prime, then there exist $a$ and $b$, such that $1\lt a,b\lt n$ and $n=ab$. We cannot have both $a$ and $b$ greater than $\sqrt{n}$, because then $n = ab \gt \sqrt{n}\sqrt{n} = n$, which is impossible. So either $a\leq\sqrt{n}$, or $b\leq \sqrt{n}$. If $a\leq\sqrt{n}$, then either $a$ is prime, and so $n$ has a prime factor less than or equal to $\sqrt{n}$; or else $a$ has a prime factor $p$ with $p\leq\sqrt{a}$; but a prime factor of $a$ is also a prime factor of $n$, and $a\lt n$ implies $\sqrt{a}\lt\sqrt{n}$, so $p$ is a prime factor of $n$, $p\leq \sqrt{n}$. Either way, $n$ has a prime factor less than or equal to $\sqrt{n}$.

If $b\leq\sqrt{n}$, then repeat the argument with $b$ instead of $a$.

share|improve this answer
    
Arturo: As written, the proof is correct; but I don't think we really need to do an induction on $a$ (or $b$). Specifically, in the case $a \leq \sqrt{n}$, any prime factor $p$ of $a$ satisfies: $p \leq a \leq \sqrt{n}$, and we are done. The $b \leq \sqrt{n}$ case is similar. –  Srivatsan Jan 26 '12 at 22:02
    
@Srivatsan: The amusing thing about the argument above is that I do not need to assume that a positive integer greater than $1$ necessarily has a prime factor; we're actually proving this fact "along the way". –  Arturo Magidin Jan 27 '12 at 1:36
    
Ah yes, that is indeed true. Thanks for pointing it out explicitly to me. –  Srivatsan Jan 27 '12 at 1:38
add comment

As said by others here your claim is false, maybe you've seen that the Smallest prime factor of $n$ is lower or equal to the square root of $n$.

Proof for the first claim: assume that the claim - Smallest prime factor of n is above than square root of $n$ is true. then let $x$ be the smallest prime factor of $n$, so there exists integer $y$ such that $n=xy$. but $x > \sqrt{n}$ and $y\ge x> \sqrt{n}$ so we got $n<xy$ and thats the desired contradiction.

try to think how to change that proof to prove the second claim.

share|improve this answer
    
It's not true in general that the biggest prime factor of $n$ is greater than or equal to $\sqrt{n}$. For example, $5\cdot7\cdot11=385$ and $11 < \sqrt{385}$. –  Michael Hardy Aug 5 '12 at 4:27
    
youre right. edited it to the correct claim. –  Ofek Ron Aug 5 '12 at 10:29
add comment

Greene and Knuth (1990) called numbers for which the greatest prime factor was greater than $\sqrt{n}$ "unusual numbers" - perhaps that's what you're thinking of.

However, it turns out they aren't so unusual after all. As Schroeppel (1972) pointed out, the probability that a random integer will be "unusual" is $\ln2$.

As the other answers have more precisely stated, the statement does hold for the smallest prime factor. (IE: $spf(n) <= \sqrt{n}$)

Source: http://mathworld.wolfram.com/GreatestPrimeFactor.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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