Hello everyone. In this video, we're going to prove the claim that, "if $p$ and $p+1$ are prime, then $p=2$." Now there are many ways to prove this claim. I'm going to give a proof that breaks this into cases, and let me try to explain the reasoning behind this.
So when reading this, you should believe almost instantly that this is true, right? In your mind, you should think okay well, $p$ and $p+1$, well one of these two numbers must be even and because of that, $2$ must be a factor of the even number so one of these prime numbers must be $2$. That's sort of your intuition here.
I'm going to try to write this as best and as formally as I can with the tools that we have and you can go from there. So as I said, I'm going to break this into cases and because of what I just said about $2$ dividing numbers, it seems right to use a parity argument.
Case 1: $p$ is odd.
So here's the start of my parity argument. $p$ is an odd prime number and as we discussed in class, what does this mean? This means that $p\geq 3$.
If $p$ is odd, then $p\geq 3$ because it's an odd number and it's a prime number and we know that prime numbers $> 1$, so $p \geq 3$.
However this means, what about $p+1$, right? So then $p+1 \geq 4$ and $p+1$ is even. Remember $p+1$, what does it must have? Well it has more factors than we want, right, because it's going to have $2$ as a factor. $p+1$ has $1$, $2$, $p+1$ as positive factors.
What does this mean about our statement? In this case, "if $p$ and $p+1$ are prime". So if $p$ was an odd prime, then we know that $p+1$ can't be prime. So "$p$ and $p+1$ are prime", the hypothesis, is false. When the hypothesis is false, then the implication is true.
So we're done in this case, we've proven the implication. Once the hypothesis is false, the implication has to be true. So in this case we're done.
Case 2: $p$ is even.
In this case, what do we know? If $p$ is even, then what are the factors of $p$? Well $1$ is still a factor, $p$ is even which means that $2 \mid p$ so $2$ is a factor of $p$, and $p$ is also a factor of $p$.
So $p$ is even then $p$ has positive factors $1$, $2$, and $p$. However, according to the hypothesis, $p$ is prime.
What can we conclude from this now? $p$ is prime so $p>1$ and $p$ only has two distinct positive factors. So what does this mean? We've written down three factors so two of them must be the same and the only two that can be the same are $2$ and $p$. Thus, $p=2$. This concludes the proof.
Let's read it all one more time just so that we can look at the cases.
Case 1: $p$ is odd. Then $p\geq 3$. However, $p+1\geq 4$ and $p+1$ is even. Thus, $p+1$ has $1, 2,$ and $p+1$ as positive factors. Hence, the hypothesis that $p$ and $p+1$ are prime is false. Thus, the implication is true.
Case 2: $p$ is even. Then $p$ must have factors $1, 2,$ and $p$. However, according to the hypothesis, $p$ is prime. Thus $p>1$ and $p$ only has two distinct positive factors. Thus $p=2$.
So remember the logic used in Case $1$: $A\Rightarrow B$, if $A$ is false then $A\Rightarrow B$ is true. Also the logic used in Case $2$: $A \Rightarrow B$, if $B$ is true, then $A\Rightarrow B$ is therefore true.
Okay, hopefully this helps and thank you for listening.