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

  • 2
    $\begingroup$ 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? $\endgroup$ – Mikko Korhonen Jan 26 '12 at 20:59
  • $\begingroup$ 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$? $\endgroup$ – anon Jan 26 '12 at 21:01
  • 6
    $\begingroup$ 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$. $\endgroup$ – Aryabhata Jan 26 '12 at 21:04
  • 1
    $\begingroup$ Short proof of @Aryabhata's statement: If $n=ab$ and $a \leq b$ then $a^2 \leq ab=n$. $\endgroup$ – 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$.

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Srivatsan Jan 26 '12 at 22:02
  • $\begingroup$ @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". $\endgroup$ – Arturo Magidin Jan 27 '12 at 1:36
  • $\begingroup$ Ah yes, that is indeed true. Thanks for pointing it out explicitly to me. $\endgroup$ – 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}$)

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

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ 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}$. $\endgroup$ – Michael Hardy Aug 5 '12 at 4:27
  • $\begingroup$ youre right. edited it to the correct claim. $\endgroup$ – Ofek Ron Aug 5 '12 at 10:29

The answer is quite simple.

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

| cite | improve this answer | |
  • $\begingroup$ Your answer is incomplete. $\endgroup$ – user99914 May 11 '15 at 7:33

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.