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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

There can be at most $1$ prime factor of $n$ greater than $\sqrt{n}$.

Proof: If possible let there be two distinct prime factors of $n$ which are greater than $\sqrt{n}$, say $a$ and $b$. As both $a$ and $b$ are different prime factors of $n$ their product $c = a \times b$ should also be the factor of $n$. But $c$ would exceed $n$ as both $a$ and $b$ are greater than $\sqrt{n}$, which contradicts our assumption, hence there can only be one prime factor of $n$ greater than $\sqrt{n}$.

Application: If u want to do prime factorization of $n$ then you only need primes up to $\sqrt{n}$ which largely improves the complexity of prime factorization. The number left after repeatedly dividing $n$ with all primes factors less than $\sqrt{n}$ is indeed a prime or $1$.

Repeatedly dividing $n$ with all primes factors less than $\sqrt{n}$:

You iterate over all primes less than $\sqrt{n}$. If the current prime $p$ divides $n$ you keep on dividing $n$ by $p$ until $n$ becomes $1$ or the $p$ no longer divides $n$. In the end, either $n$ will become $1$ or some number greater than $\sqrt{n}$ would be left which would also be a prime factor of $n$ but it will be the only prime factor which is greater than $\sqrt{n}$

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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)

Answer 8

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