# $\require{enclose}\enclose{horizontalstrike}{\rm Greatest}\!$ Least prime factor of $n$ is less than square root of $n$, proof

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

• 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
• 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

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

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

• 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

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}$)

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.

• 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

Given that n is composite so $n=p\cdot q\cdot r\cdot s\cdot t\cdots$ where $p,q\cdots$ are primes by fundamental theorem of arithmetic.
Now assume without loss of generality that $p<q<r<\cdots$. So $p<q\cdot r\cdot t\cdots$.
Now take square root on both sides then $\sqrt{p}<\sqrt{q\cdot r\cdot s\cdot t\cdots}$. Now multiply both sides by $\sqrt{p}$. We get $p<\sqrt{p\cdot q\cdot r \cdot s \cdot t\cdots}$ and $\sqrt{p\cdot q\cdot r\cdot s\cdot t\cdots}$ is equal to $\sqrt{n}$.
Hence established that $p \leq \sqrt{n}$.