Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
... 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
add comment

6 Answers 6

up vote 16 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
2  
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
add comment

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

share|improve this answer
add comment

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)

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.