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 that (p^2)-4 is 3 almost-prime infinitely often?

  1. Jan 8, 2014 #1
    1. The problem statement, all variables and given/known data

    Hello. I'm working on a self-study project where I'm trying to prove that (p^2)-4 is 3-almost prime infinitely often where p is prime. I have a proof, but I'm a little unsure. For instance, I am not sure that one counterexample suffices in my lemma to make the global statement that it makes. I am also not sure that the actual contradiction in this proof-by-contradiction indicates that the alleged theorem is true, though I thought I had structured it essentially correctly. So I am basically looking for feedback, and I appreciate responses in advance.

    Thanks,
    Rob Gross

    2. Relevant equations



    3. The attempt at a solution

    Lemma.

    Given prime p, there is a greater even r that is not divisible by 3 such that r - p is prime.

    Proof.

    1.0 Suppose it is the case that given prime p, a greater even r does not exist such that r
    is not divisible by 3 and r-p is prime.

    1.1 Counterexample: given prime 29, 46 exists. 46 is not divisible by 3,
    and 46-29=17.

    1.2 The supposition of 1.0 is false. So it must be the case that given prime p,
    a greater even r not divisible by 3 must exist such that r - p is prime.

    Theorem: (p^2) - 4, where p is prime >3, is 3-almost prime infinitely often.

    Proof.

    2.0 Suppose p is the last prime m>3 such that (m^2) - 4 is 3-almost prime. Call each factor of
    (p^2) - 4 respectively a, b and c, each prime, such that (p^2) - 4 = abc. Note that every prime squared less 4 is divisible by 3, so let a = 3.

    2.1 Consider [(p+y)^2] - 4 where p + y is prime.

    2.2 The expression [(p + y)^2] - 4 cannot be prime because all squared primes less 4 are divisible by 3.

    2.3 The expression [(p + y)^2] - 4 cannot be semiprime because being divisible by 3, either
    (p + y) + 2 or (p + y) - 2 is divisible by 3. (The term p + y itself cannot be divisible by 3 as it is prime.) So, either [(p + y) - 2] / 4 is some 3a while (p + y) + 2 is prime or has factors; or,
    [(p + y) + 2] / 4 is some 3a while [(p + y) - 2] / 4 is prime or has factors.

    2.4 The expression [(p + y)^2] - 4 cannot be 3-almost prime because (p^2) - 4 is the last
    (m^2) - 4 example that is 3-almost prime, and p+y > p.

    2.5 Therefore, [(p+y)^2] - 4 must be 4-or-more-almost prime.

    2.6 Note [(p+y)^2] - 4 must equal some hijk, where h, i and j are prime and k may or may not be prime.

    2.7 Note [(p+y)^2] - 4 equals (p^2) + 2py + (y^2) - 4, which equals
    [(p^2) - 4] + [2py + (y^2)].

    2.8 Note [(p^2) - 4] + [2py + (y^2)] = 3bc + [2py + (y^2)] = hijk.

    2.9 This means 3bc + y(2p + y) = hijk.

    2.10 Let us let q equal the sum p+y. This means q is prime and y=q-p.

    2.11 Substituting q-p for y in 2.9: 3bc + (q - p)(2p + q - p) = hijk.

    2.12 This means 3bc + (q - p)(q + p) = hijk.

    2.13 This means 3bc + [(q^2) - (p^2)] = hijk.

    2.14 Note that every prime squared less another prime squared is always divisible by 24.

    2.15 This means 3bc + [(q^2) - (p^2)] is divisible by 3, and so hijk is divisible by 3.

    2.16 Suppose we let y = r - 2p where p + y = r - p and where r - p is a prime and r is not divisible by 3. Per the lemma, finding such an r is always possible. Note that the observations made heretofore are true for any value of y. It should therefore still be the case that
    [(p+y)^2] - 4 must equal some hijk, where h, i and j are prime and k may or may not be prime; it should still be the case that 3bc + [(q^2) - (p^2)] is divisible by 3, and so hijk is divisible by 3.

    2.17 Substituting r - 2p for y in 2.9: 3bc + (r-2p)(r) = hijk.

    2.18 This means 3bc + (r^2) - r = hijk.

    2.19 Because r is not divisible by 3, this means (r^2) - r is not divisible by 3.

    2.20 3bc is divisible by 3, so adding 3bc to (r^2) - r results in a sum not divisible by 3.

    2.21 So 3bc + (r^2) - r is not divisible by 3, and neither is hijk.

    2.22 This is a contradiction with 2.15.

    2.23 The only resolution to this contradiction is to assume the supposition of 1.0 is incorrect, and there cannot be a last prime m such that (m^2) - 4 is 3-almost prime where m is prime.

    2.24 Therefore, there are infinitely many 3-almost primes in the form (m^2) - 4 where m is prime.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Jan 8, 2014 #2
    Mini proofs: every prime squared less 4 is divisible by 3 because (p^2)-4 is (p+2)(p-2). We know p, being prime, is not divisible by 3, so either p+2 or p-2 is divisible by 3, since every consecutive odd triplet contains exactly one number divisible by 3.

    The expression (q^2) - (p^2) where p, q are prime is divisible by 24 because it is [(q^2) - 1] - [(p^2) - 1], and
    every prime squared less unity is divisible by 24:

    Best explanation
     
  4. Jan 8, 2014 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't even think the proof of your lemma is correct. You seem to be saying that since for p=29 there is an even r=46 not divisible by 3 such that r-p is prime somehow implies that there is such an r for ALL primes p. That hardly makes sense.
     
  5. Jan 8, 2014 #4
    I know; I said as much. The broader question I'm asking about that is, so when is one counterexample good enough for a proof by contradiction and when isn't it? The proposition itself seems sound enough--- it's not exactly *hard* to take a prime p, find a prime q to add to it, and get a number that isn't divisible by 3.
     
    Last edited: Jan 9, 2014
  6. Jan 9, 2014 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, your doubts are justified. It's just that you are contradicting the wrong thing. What you want to assert is that for ALL primes p, there exists an r. The negation of that is that THERE EXISTS a prime p such that there is no such r. Finding a particular example of a prime p such that there is such an r doesn't contradict the negation. Does that make sense?
     
  7. Jan 9, 2014 #6
    Yes, that does make sense. I'm working on a new lemma.
     
    Last edited: Jan 9, 2014
  8. Jan 9, 2014 #7
    Given prime p, there is a greater even r that is not divisible by 3 such that r-p is prime.

    1.0 Proving this is tantamount to proving that given p, a prime q exists such that p+q=r
    where r is even and not divisible by 3.

    1.1 Relative to p, a greater prime q exists as there are infinitely many primes.

    1.2 Suppose for all greater primes q, p+q is always an even number divisible by 3.

    1.3 The supposition of 1.2 is absurd. Given p, there could be no primes 2-apart
    greater than p; if greater prime q and q+2 are both prime, p+q and p+q+2 would
    both have to be divisible by 3. If greater prime q and q+4 are both prime,
    p+q and p+q+4 would have to be divisible by 3. If greater prime q and q+8
    are both prime, p+q and p+q+8 would have to be divisible by 3. Since these
    cases cannot be, in effect, the existence of p would end the existence of any p+n primes
    where n is not divisible by 6. This obviously runs counter to every principle of
    prime number distribution; whether or not twin primes or
    4-apart primes or 8-apart primes are infinitely many, they do not simply end for every
    given p. That is an absurd proposition.

    1.4 Because 1.2 is absurd, it must be the case that of the infinitely many primes q
    that can be added to p, p+q will not be divisible by 3 in every case.

    1.5 Therefore, there is always some prime q to add to prime p such that p+q=r
    where r is even and not divisible by 3.

    1.6 The condition of 1.0 being proved, the lemma is proved.

    Better?
     
  9. Jan 9, 2014 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Better. But way too complicated. Try simplifying it hugely. Just consider p+5 and p+7 and your divisibility by 3 argument.
     
  10. Jan 9, 2014 #9
    Okay. You're probably right, but I'm a little bit leery of relying exclusively on p+5 and p+7 because it would *seem* to suggest an infinitude of twin primes, which has not been established (i.e., if you run out of twin primes, then you don't have that problem anymore!) I thought invoking the entire panorama of primes that would contradict the possibility of divisibility by 3 would be a safer argument.

    Any thoughts on the rest of it?
     
  11. Jan 9, 2014 #10
    I discovered a boo-boo from 2.19 on. It should have read:

    2.19 Because r is not divisible by 3, this means (r^2) - 2pr is not divisible by 3.

    2.20 3bc is divisible by 3, so adding 3bc to (r^2) - 2pr results in a sum not divisible by 3.

    2.21 So 3bc + (r^2) - 2pr is not divisible by 3, and neither is hijk.

    2.22 This is a contradiction with 2.15.

    2.23 The only resolution to this contradiction is to assume the supposition of 1.0 is incorrect, and there
    cannot be a last prime m such that (m^2) - 4 is 3-almost prime where m is prime.

    2.24 Therefore, there are infinitely many 3-almost primes in the form (m^2) - 4 where m is prime.

    * * *

    But, I realize that just because r is not divisible by 3 does not guarantee that (r^2) - 2pr is not divisible by 3. One counter-example I discovered is 16^2 - (2*5*16) = 96.

    Back to the drawing board.
     
  12. Jan 9, 2014 #11
    My fundamental premise here is that when y is not given a value, the statement 3bc + [(q^2) - (p^2)] = hijk has to be divisible by 3 in every case, because 3bc is inherently divisible by 3, and [(q^2) - (p^2)] is inherently divisible by 3. But when you assign a value to y such as 2-rp, where r is an even number not divisible by 3, then you get 3bc + (r^2) - 2pr = hijk, and 3bc + (r^2) - 2pr is only divisible by 3 *sometimes*. I wonder if this is still enough to establish the contradiction.
     
  13. Jan 9, 2014 #12
    Actually, it would appear that when p is prime and r is an even number not divisible by 3, and r-p is prime, it seems (r^2) - 2pr is *always* divisible by 3. I can't find a counterexample. Argh. Argh. Argh.
     
    Last edited: Jan 9, 2014
  14. Jan 9, 2014 #13
    It would appear that when p is prime and r is an even number not divisible by 3, and r-p is prime that (r^2) - 2pr is always divisible by 24, which makes sense, I suppose, because it's being substituted for (q^2) - (p^2). But I'd be interested to know why, on its own, that (r^2) - 2pr is always divisible by 24 under the condition that r-p is prime.
     
  15. Jan 9, 2014 #14
    I see why now, for anyone who's interested.

    If r-p is prime, then r-p must equal some q that's prime.

    That means r=p+q.

    Substituting p+q for r in the statement r(r - 2p) we get

    (p + q) (q + p - 2p)

    which is

    (q + p) (q - p)

    which is (q^2) - (p^2), which is always divisible by 24.
     
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 that (p^2)-4 is 3 almost-prime infinitely often?
Loading...