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

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 4

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