1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jan 15, 2016 #1

    RJLiberator

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    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).

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

    3. 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?
     
  2. jcsd
  3. Jan 15, 2016 #2

    fresh_42

    Staff: Mentor

    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.
     
  4. Jan 15, 2016 #3

    RJLiberator

    User Avatar
    Gold Member

    @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 dont 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.
     
  5. Jan 15, 2016 #4

    fresh_42

    Staff: Mentor

    Just assume all primes that divide n are greater than sqrt(n).
     
  6. Jan 15, 2016 #5

    RJLiberator

    User Avatar
    Gold Member

    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)...
     
  7. Jan 15, 2016 #6

    fresh_42

    Staff: Mentor

    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.
     
    Last edited: Jan 15, 2016
  8. Jan 15, 2016 #7

    RJLiberator

    User Avatar
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof: There Exists a prime p such that p=< sqrt(n)
  1. If p is prime (Replies: 2)

Loading...