# Is a prime factor of a number always less than its square root?

I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for every such number, there exists a prime $p$ such that $p< \sqrt n$.
I was wondering if there is any mathematical proof that no prime $p$ exists for the number $n$ such that $p> \sqrt n$.

-
... but if you move $1/2$ down from the exponent in $n^{1/2}$, it's correct: $p\le \frac{1}{2}n$ – draks ... Jun 21 '12 at 6:18
¿did you see at a simple example? 15=3 * 5 and 5 is a prime certainly larget than the square root of 15! – kjetil b halvorsen Sep 28 '12 at 0:24
proofwiki.org/wiki/… – Trancot Apr 29 '13 at 6:08
Wouldn'd this imply that the set of all prime numbers would be finite, limited by the square root of any number??? – Ed de Almeida Jun 1 at 11:08

No. Consider that the square root of $14$ is about $3.74$ but $14$ has $7$ as a prime factor. Also consider that any prime number such as $2$ is its own (only) prime factor, and any number greater than $1$ is greater than its square root. The theorem you have stated is incorrect: $25$ has no prime factor less than $5$, and $3$ has no prime factor less than $1.732$; however, it is true that every composite number has a prime factor less than or equal to its square root.

-
Ok, now I can see it. If such a prime p exists such that $p$ > $\sqrt n$ and it is not equal to n then it must have a prime $q$ < $\sqrt n$. Otherwise all such primes should be less than $\sqrt n$. Thus I get the solution to my related problem. Thnx for help. – Abhishek Anand Sep 10 '11 at 8:24
That is true, unless n is a square of a prime (e.g. 25), in which case its prime factor is exactly equal to its square root. Now what if n is the square of a composite (e.g. 36)? – Dan Brumleve Sep 10 '11 at 8:39
missed out mentioning n was composite...my bad!! Was more concerned about how to represent $\sqrt n$ here :) – Abhishek Anand Sep 10 '11 at 9:22

You seem to be confused with another statement, which is that the smallest prime factor of a composite number N is less than or equal to $\sqrt N$.

-
No actually the question which got me thinking the above asked question was--> Show that there exists a prime p dividing $n$ (composite number), with $p$ <= $\sqrt n$ . – Abhishek Anand Sep 10 '11 at 8:48
@AbhishekAnand The statements "the smallest prime factor of a composite number$N$ is less than or equal to $\sqrt N$" (in Mark Bennet's answer) and "there exists a prime $p$ dividing $n$ (composite number) with $p\leq\sqrt n$" (in your comment) are obviously equivalent. If some prime factor is $\leq\sqrt n$, then the smallest prime factor can't be any bigger. – Andreas Blass Jul 31 '14 at 1:04

Proof: Suppose $n$ is a positive integer s.t. $n=pq$, where $p$ and $q$ are prime numbers. Assume $p>\sqrt{n}$ and $q>\sqrt{n}$. Multiplying these inequalities we have $p.q>\sqrt{n}.\sqrt{n}$, which implies $pq>n$. This is a contradiction to our hypothesis $n=pq$. Hence we can conclude that either $p\leq \sqrt{n}$ or $q \leq \sqrt{n}$.

-
Welcome to MathSE! Your proof shows if $n$ is the product of two primes, then at most one (prime) factor is greater than $\sqrt{n}$ but this late answer doesn't contribute much to what others said and doesn't directly address the Question, is every prime factor of a positive integer less than its square root? – hardmath Jun 21 '12 at 14:35
proofwiki.org/wiki/… – Trancot Apr 29 '13 at 6:08

N=a*b=ab+b^2-b^2=b^2 + b(a-b)

if b < a then b^2 < N so b < sqrt(N)

if b = a a = b = sqrt(N)

-

It doesn't mean that every factor of $n$ would be less that $\sqrt{n}$, in fact at least one factor would be less than $\sqrt{n}$ if $n$ is not a prime number. Explanation: $$n=\sqrt{n}\cdot \sqrt{n},\quad n=a\cdot b,$$ so 1) if one factor is less than $\sqrt{n}$ then other will be greater than $\sqrt{n}$, 2) if there is no such factor less than $\sqrt{n}$ then both factors would be greater than $\sqrt{n}$ but it's not possible; so, that number must be prime if it doesn't have a factor less than $\sqrt{n}$.

-

I know the answer is late. But, maybe its useful for reference.

For a number n consider these cases:

1. The given number is prime and has only itself and 1 as factors. (1,n)
2. The given number is a square of a prime p
=> n=p^2 or n=p*p
3. The given number is a product of just two prime numbers p & q
=> n=p*q
4. The given number has again two prime factors, but now, and at-least one of them is repeated
=> n = p*p*q OR p*p*p*q OR p*q*q ... etc.
5. The given number has more than two prime factors, each with/without repetition
=> n = p*q*r*... etc.

1 - No other prime factors -- Eg. 11
2 - p=sqrt(n) -- Eg. 5=sqrt(25)
3 - one of p,q will be "< sqrt(n)" and the other will be "> sqrt(n)" -- Eg. 2*7=14
4 - At most one out of p & q could be "> sqrt(n)" -- Eg. 2*2*7=28
5 - At most one of them could be "> sqrt(n)" -- Eg. 2*2*3*7=84

Clearly, the only cases 1,2,3 touch or cross the sqrt(n) border.
Case 1 Is crossing because its only factor is itself
Case 2 Is touching sqrt.. cant cross
Case 3 Will cross sqrt because fac1<sqrt and fac2>sqrt
Case 4 & 5 Could cross sqrt sometimes

Think of square-root as splitting a number into two in the multiplicative sense.
Case 1 - you cant split
Case 2 - your doing the same thing.. splitting into two
Case 3 - you can't split perfectly as the number is not a square. So, there is an unequal split with one side dominating
Case 4 - you are splitting more than twice. The pieces become way too small. But consider this case: if p*p is itself <sqrt(n) q could still be >sqrt(n)
Case 5 - again you are splitting more than twice. The pieces become way too small. But one piece could still become greater than sqrt like in case 4 above

If n is not a perfect square, factors can be bunched up so that one chain will be <sqrt(n) and the other chain will be >sqrt(n). If the chain that is >sqrt(n) has only one member, in that case the prime-factor that is >sqrt(n) exists.

-
Your statement is confusing. Does $42$ comply with this or not? – WimC Apr 28 '13 at 7:19
@WimC I had a lot of corrections to make. Does it make sense now? – Theo Apr 28 '13 at 8:30

There can be at most 1 prime factor of n greater than sqrt(n). Proof : If possible let there exists two greater sqrt(n) then their product should also divide n but which excides n, which contradicts our assumption. Application : If u want to prime factorise n then you need at most primes upto sqrt(n) which largely improves the complexity. The number left after dividing n with all possible powers of primes less than sqrt(n) is indeed a prime or 1.

-