13
$\begingroup$

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

  • 1
    Short proof of @Aryabhata's statement: If $n=ab$ and $a \leq b$ then $a^2 \leq ab=n$.2012-01-26

5 Answers 5

21

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

3

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

  • 0
    Ah yes, that is indeed true. Thanks for pointing it out explicitly to me.2012-01-27
1

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

0

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 and thats the desired contradiction.

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

  • 0
    youre right. edited it to the correct claim.2012-08-05
-2

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

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

  • 0
    Your answer is incomplete.2015-05-11