Results 1 to 12 of 12

Math Help - Odd Primes Proof (Should be simple)

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Odd Primes Proof (Should be simple)

    Hello all,

    I have a quick question that someone might be able to help me understant. This statement says:

    Consider the list of odd primes [3,5,7,....]
    Prove that if a and b are adjacent odd primes in the lis, then their sum a+b necessarily has 3 prime factors, where these factors need not be distinct.

    Example: 3+5=8=2x2x2 (3 repeated factors of 2)
    Example: 47+53=100=2x2x5x5 (4 prime factors)

    How do I prove this? I also don't understand how it says a+b necessarily have 3 prime factors, but my 2nd example has 4 ????

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    I think that you are supposed to take the problem as " a+b has at least 3 prime factors (not necessarily distinct)".

    You can do this by contradiction. What if a+b has exactly two? Can you say what one of the prime factors is? Does it cause a problem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by roninpro View Post
    I think that you are supposed to take the problem as " a+b has at least 3 prime factors (not necessarily distinct)".

    You can do this by contradiction. What if a+b has exactly two? Can you say what one of the prime factors is? Does it cause a problem?
    Well let me see here, if a+b=d, then a|d and b|d which means that there is at least two numbers that divide d. We also know that since a and b are odd, the sum of them is an even number. All even numbers are divisible by 2, which is prime. that means that 2|d, which means we now know that there is at least 3 numbers that divide d.

    Is this a feasible proof?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You have some good and bad elements in your statement.

    First, a+b=d does not imply a|d,\  b|d. Look at some of your examples: 3+5=8, but neither 3 nor 5 divide 8. However, you are correct in saying that d should be even, so 2|d. From here, though, you can't necessarily conclude that d/2 has three prime factors. How do you know that d/2 is not prime?

    You can try the contradiction route. Suppose a+b=d has only two prime factors, where a,b are two adjacent odd primes on the list. We know that one of the prime factors must be 2. The second prime factor must be 2 or odd. If it is 2, then d=4, and that is not a sum of two adjacent odd primes. What is wrong if it is odd?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    I don't understand this. Let me look herein:
    List=3,5,7,11,13,17

    3+5=8=2x2x2
    5+7=12=2x2x3
    11+13=24=2x2x2x3

    So you are saying that if I have two generic ODD primes, p and q, and I add p and q to get d, then 2|d with at least two more primes who don't necessarily need to be distinct. We will call them e and f.

    So lets assume e is even. So now 2*e|d. This makes sense considering that d has to be even, so even numbers can be divided by even numbers. d is not prime however, nor does it need to be. Same case if f is even as well, 2*e*f|d and will yield an even number that divides into an even number. This seems reasonable.

    So lets assume e is odd. The argument still makes sense that 2*e|d because 2*e is also even, regardless of whether e is odd or not.

    So now i'm totally at odds (no pun intended) with how we can still say there are at least 3 primes. To be quite honest, I don't even know if what I just said above is even relevant or useful, it is just my train of thought.
    then
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    So lets assume e is even. So now 2*e|d. This makes sense considering that d has to be even, so even numbers can be divided by even numbers.
    This is fine. If e is even, then you are done. You can then factor 2 out of e and write 2\cdot 2\cdot e=d. We have written d as a product of at least 3 primes. ( e could be either prime or composite, but it doesn't matter.)

    So lets assume e is odd. The argument still makes sense that 2*e|d because 2*e is also even, regardless of whether e is odd or not.
    Fine. But if we want to conclude, we need to show that e is not prime. If it is prime, then we fail, since d will be written as a product of only two primes. For a contradiction, suppose that e is prime. We can write \frac{a+b}{2}=e. How does this contradict the assumption that a,b are adjacent odd primes?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Apr 2009
    Posts
    96
    I don't understand how a+b = 2e contradicts the assumption that a,b are adjacent primes. Also, for the first part, we said assume e is even. How can we be sure we can factor 2 out of e and still be left with 3 numbers?
    Example:
    2*e*f=d
    You're stating that f|e and f|d, so then we can write 2*f*e=d. So now you stated that assume that f would be 2. So now 2*2*e ? Why do we divide e to begin with?

    List=3,5,7,11,13,17

    3+5=8=2x2x2 , so 2x6 --> 2x2x3
    5+7=12=2x2x3, so 3x4 --> 3x2x2
    11+13=24=2x2x2x3, so 3x8 --> 3x2x2x2

    I guess that makes sense now that I see the pattern, but I don't know how to really explain why that is.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by roninpro View Post
    This is fine. If e is even, then you are done. You can then factor 2 out of e and write 2\cdot 2\cdot e=d. We have written d as a product of at least 3 primes. ( e could be either prime or composite, but it doesn't matter.)



    Fine. But if we want to conclude, we need to show that e is not prime. If it is prime, then we fail, since d will be written as a product of only two primes. For a contradiction, suppose that e is prime. We can write \frac{a+b}{2}=e. How does this contradict the assumption that a,b are adjacent odd primes?
    You should ask yourself, how big is \frac{a+b}{2}? And from that see  e can't be prime.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by roninpro View Post
    This is fine. If e is even, then you are done. You can then factor 2 out of e and write 2\cdot 2\cdot e=d. We have written d as a product of at least 3 primes. ( e could be either prime or composite, but it doesn't matter.)



    Fine. But if we want to conclude, we need to show that e is not prime. If it is prime, then we fail, since d will be written as a product of only two primes. For a contradiction, suppose that e is prime. We can write \frac{a+b}{2}=e. How does this contradict the assumption that a,b are adjacent odd primes?
    Okay, I said that we have 3 primes that go into d which are 2,e,f . So techincally, 2|d, 2*e|d, 2*f|d, 2*e*f|d. So why must we prove that e is composite? I see that you're analyzing a+b=d=2*e but omitting f, and a+b is even so divded by 2 is also even considering a and b are adjacent odd primes. So now we know that e is even which we have said before, but why must it be composite?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Okay, I said that we have 3 primes that go into d which are 2,e,f .
    This is incorrect. You are assuming what you are trying to prove.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by roninpro View Post
    This is incorrect. You are assuming what you are trying to prove.
    Okay, so let me ask,

    We can write \frac{a+b}{2}=e. How does this contradict the assumption that a,b are adjacent odd primes?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    Okay, so let me ask,

    We can write \frac{a+b}{2}=e. How does this contradict the assumption that a,b are adjacent odd primes?
    Well if \frac{a+b}{2} is prime, then can  a and  b be adjacent primes?
    Last edited by chiph588@; May 14th 2010 at 12:05 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 10th 2010, 08:35 PM
  2. Mod proof with primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 06:32 PM
  3. Proof of primes.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 26th 2009, 12:12 AM
  4. Primes proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2005, 06:13 AM
  5. Infinite Primes Proof
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 11th 2005, 08:40 AM

Search Tags


/mathhelpforum @mathhelpforum