23
$\begingroup$

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

  • 0
    So let's state things clearly. Because the proposition above is ambiguous. What you mean is: **For a given integer `n`, there is no `p` such that `p` is prime and `p` is a factor of `n`.** Stated this way, the correct way, the proposition is easily proved.2017-01-23

8 Answers 8

35

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.

  • 0
    Yes, that is true, because a number can't be less than the product of two of its prime factors.2018-01-11
14

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

  • 0
    @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.2014-07-31
5

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

  • 0
    http://www.proofwiki.org/wiki/Composite_Number_Has_Prime_Factor_Less_Than_Or_Equal_To_Its_Square_Root2013-04-29
2

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

2

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 fac1sqrt
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)
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). If the chain that is >sqrt(n) has only one member, in that case the prime-factor that is >sqrt(n) exists.

  • 0
    @WimC I had a lot of corrections to make. Does it make sense now?2013-04-28
1

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.

0

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)

0

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