Proof: There Exists a prime p such that p=< sqrt(n)

[RJLiberator]

Homework Statement

Question: Let n> 1 be an integer which is not prime. Prove that there exists a prime p such that p|n and p≤ sqrt(n).

Homework Equations

Fundamental theorem of arithmetic: Every integer n >1 can be written uniquely (up to order) as a product of primes.

The Attempt at a Solution

Pf. By the F.T.O.A. there exists a prime p such that p|n. [this proves part 1 of the question
We can write n = pq where q,p ∈ℤ and 1 ≤p, q ≤n.
Suppose p ≤ q. For contradiction, assume p > sqrt(n).
Then q ≥ p > sqrt(n). However, if this is true, then:
n = pq > sqrt(n)sqrt(n) > n, and we have a contradiction.
so p ≤ sqrt(n). I feel moderately confident with this proof. Are there any holes that you detect?

 

[fresh_42]

Yep, there is one. How may you assume p ≤ q? What if n = 76 = 4 * 19? Here 19 > sqrt(76). You need to consider this case.

 

[RJLiberator]

@fresh_42 Hmm...

So what you are telling me is I need to break it up into cases.
Its easy enough to prove that there exists some prime p by FTOA.
But we don't know if p > q or if p ≤ q.
So we break it into two cases where I have already shown the case p ≤ q.

Case 2: p > q
I'm struggling here, but we know that n can be broken up into 2 primes by FTOA so with p > q, then we know that q is either a prime which then you can use case 1, or q can be broken up into primes.
I feel like this is not necessary? I understand your example of 76, but we have 4 * 19 which is just 2*38 and here the prime 2 would be p < q.

 

[fresh_42]

Just assume all primes that divide n are greater than sqrt(n).

 

[RJLiberator]

Hm.

But how can we assume that all primes that divide n are greater than sqrt(n)? One might be, but one has to not be.

I see what you are saying that when I suppose p ≤ q that there is something I might be missing in my proof.
In my head, I see if q ≤ p then, as stated in my reply post, q can either be broken up into primes itself or is already prime and less than sqrt(n).

I'm not sure if my initial proof covers all this. Hm.
If I were to assume that all primes > sqrt(n) then we can easily show that n can be broken down into factos of primes and at the least case being two primes which would be incompatible. I see where this is going. Perhaps this is a bit more difficult to write out, as I can easily write it out for the case where there is 2 prime factors, but I'd have to make it for the general case (which is obvious as sqrt(n)sqrt(n)sqrt(n) is clearly greater than n in the prime = 3 factors case)...

 

[fresh_42]

Your proof has been almost perfect. If you assume all prime divisors of n being greater than its root it will immediately lead to the contradiction you showed: $n=p_1^{r_1} \cdot ... \cdot p_k^{r_k} ∧ \sum^{i=k}_{i=1} r_i ≥ 2 ⇒ n ≥ min \{p_i\}^2 > \sqrt{n} \sqrt{n} = n$. So the assumption $∀ p|n : p > \sqrt{n}$ is wrong, i.e. its negation is true: $∃ p|n : p ≤ \sqrt{n}$.
As I said, you've been close to correct.

 

[RJLiberator]

Ohhhh, I see.
That makes a lot of sense.
Since I only need to show the existence of one of them, assuming all are > sqrt(n) is highly logical as this makes the proof easier.

Thank you greatly.