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

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

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Abhishek Anand Sep 10 '11 at 8:24
  • 1
    $\begingroup$ 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)? $\endgroup$ – Dan Brumleve Sep 10 '11 at 8:39
  • 1
    $\begingroup$ missed out mentioning n was composite...my bad!! Was more concerned about how to represent $\sqrt n$ here :) $\endgroup$ – Abhishek Anand Sep 10 '11 at 9:22
  • $\begingroup$ But then while doing prime factorization number it is said check primes only till root of the number. Why? Where I am getting confused? $\endgroup$ – vishal mishra Sep 22 '17 at 6:03
  • $\begingroup$ Is it true that at most there exists only one prime factor strictly greater than the square root and that it would be of order one? All the counterexamples along the lines of this answer that I can find (6, 10, 15, 20, 21) all have only one factor above the root. $\endgroup$ – Double AA Jan 11 '18 at 18:43

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

  • $\begingroup$ 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$ . $\endgroup$ – Abhishek Anand Sep 10 '11 at 8:48
  • $\begingroup$ @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. $\endgroup$ – 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}$.

  • 2
    $\begingroup$ 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? $\endgroup$ – hardmath Jun 21 '12 at 14:35
  • $\begingroup$ proofwiki.org/wiki/… $\endgroup$ – Trancot Apr 29 '13 at 6:08

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.

  • $\begingroup$ Your statement is confusing. Does $42$ comply with this or not? $\endgroup$ – WimC Apr 28 '13 at 7:19
  • $\begingroup$ @WimC I had a lot of corrections to make. Does it make sense now? $\endgroup$ – 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.


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)


A prime factor is not always less than the square root as you could see with the $14 = 2 \times 7$ as a counter example, since $7 \gt \sqrt14$. But you can show that when the number is not prime, the smallest prime divisor less than the number itself is less than or equal to the square root.

Let $n$ be a positive composite integer and $d$ be the smallest prime factor of $n$ less than $n$ itself.

Write $n = dq$ for some integer $q \gt 0$. We should have $q \gt 1$, otherwise we would have $n = d$. So, either $q \lt d$ or $q \ge d$.

Suppose then that $q \lt d$. Then either $q$ is prime or a product of primes. In either cases we would have found prime divisors of $n$ less than $d$, a contradiction to the fact that $d$ is the smallest. So $q \ge d$, and we can divide $q$ by $d$ and write $q = kd + r$ for some integer $k$ and $0 \le r \lt d$. Substituting this back in the first equation you get $n = d(kd + r) = d^2k + dr \ge d^2$, therefore $d^2 \le n$ and so $d \le \sqrt n$.

So clearly the smallest prime factor of a number is either the number itself in case it's prime or it's less than or equal to the square root of the number. An upper bound for divisors less than $n$ would be $\frac{n}{2}$. You can look at $n = dq$ and see that you want $q >= 2$ again and in this case $d$ is maximum when $q = 2$ and you would have $n = 2d$ so $d = \frac{n}{2}$.


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.