# Thread: Odd Primes Proof (Should be simple)

1. ## 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!

2. I think that you are supposed to take the problem as "$\displaystyle a+b$ has at least 3 prime factors (not necessarily distinct)".

You can do this by contradiction. What if $\displaystyle a+b$ has exactly two? Can you say what one of the prime factors is? Does it cause a problem?

3. Originally Posted by roninpro
I think that you are supposed to take the problem as "$\displaystyle a+b$ has at least 3 prime factors (not necessarily distinct)".

You can do this by contradiction. What if $\displaystyle 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?

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

You can try the contradiction route. Suppose $\displaystyle a+b=d$ has only two prime factors, where $\displaystyle 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 $\displaystyle d=4$, and that is not a sum of two adjacent odd primes. What is wrong if it is odd?

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

6. 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 $\displaystyle e$ is even, then you are done. You can then factor 2 out of $\displaystyle e$ and write $\displaystyle 2\cdot 2\cdot e=d$. We have written $\displaystyle d$ as a product of at least 3 primes. ($\displaystyle 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 $\displaystyle e$ is not prime. If it is prime, then we fail, since $\displaystyle d$ will be written as a product of only two primes. For a contradiction, suppose that $\displaystyle e$ is prime. We can write $\displaystyle \frac{a+b}{2}=e$. How does this contradict the assumption that $\displaystyle a,b$ are adjacent odd primes?

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

8. Originally Posted by roninpro
This is fine. If $\displaystyle e$ is even, then you are done. You can then factor 2 out of $\displaystyle e$ and write $\displaystyle 2\cdot 2\cdot e=d$. We have written $\displaystyle d$ as a product of at least 3 primes. ($\displaystyle e$ could be either prime or composite, but it doesn't matter.)

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

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

Fine. But if we want to conclude, we need to show that $\displaystyle e$ is not prime. If it is prime, then we fail, since $\displaystyle d$ will be written as a product of only two primes. For a contradiction, suppose that $\displaystyle e$ is prime. We can write $\displaystyle \frac{a+b}{2}=e$. How does this contradict the assumption that $\displaystyle 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?

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

11. Originally Posted by roninpro
This is incorrect. You are assuming what you are trying to prove.
We can write $\displaystyle \frac{a+b}{2}=e$. How does this contradict the assumption that $\displaystyle a,b$ are adjacent odd primes?
We can write $\displaystyle \frac{a+b}{2}=e$. How does this contradict the assumption that $\displaystyle a,b$ are adjacent odd primes?
Well if $\displaystyle \frac{a+b}{2}$ is prime, then can $\displaystyle a$ and $\displaystyle b$ be adjacent primes?