Hello everyone. In this video, we're going to prove the claim
that, "if p and p plus 1 are prime,
then p must be equal to 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 plus 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 we'll 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.
So...
So, I'm going to break this up into Case 1:
"p is odd".
So here's the start of my parity argument.
p is odd so p is an odd prime number.
As we discussed in class, what does this mean?
This means, "then p
is greater than or equal to 3".
So if p is odd, then p is greater than or equal to 3
because it's an odd number and it's a prime number
and we know that prime numbers are greater than 1,
so p must be greater than or equal to 3.
However this means, what about p plus 1, right?
So then p plus 1 is greater than or equal to 4
and p plus 1 is even.
Thus,
p plus 1 has... what?
Well it has… remember p plus 1, what does it must have? Well
it has more factors than we want, right,
because it's gonna have 2 as a factor, right?
p has 1 comma 2,
and p plus 1 as factors
So let's go through this. Now let's see, so p is odd then p is greater than or equal to 3.
However, p plus 1 is greater than or equal to 4, p plus 1 is even.
What does that mean?
So p plus 1 has 1, 2, and p plus 1 as factors.
What does this mean about our statement?
In this case, "if p and p plus 1 are prime".
So if p was an odd prime,
then we know that p plus 1 can't be prime.
So "p and p plus 1 are prime", the hypothesis, is false.
With the hypothesis false, then the implication is true.
"Hence, the hypothesis
that p and p plus 1 are prime is false.
Thus, 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.
So now in Case 2,
we'll look at p being 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 divides p so 2 is a factor of p,
and p is also a factor of p.
So p is even then p has factors 1, 2, and p.
However, according to the hypothesis, p is prime.
So p must have factors 1, 2, p. However, according to the hypothesis is p is prime.
And what can we conclude from this now?
p is prime so p is greater than 1
and p only has
two distinct positive factors
I should write up here positive as well so maybe I'll write this in bold.
So a little bit of a typo up there
because we're only looking at positive factors of these numbers.
However, according to the hypothesis p is prime
so thus p is greater than or equal to 1, 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 equals 2.
This concludes the proof.
Let's read it all one more time
just so that we can look at the cases. So because
we argued that
p and p plus 1, one of these have to be even,
that's what we got when we read this hypothesis.
It seemed to believe that we should use
a parity argument and break this into cases.
So Case 1 when p is odd, we know that
p has to be greater than or equal to 3 because p is a prime number,
so it's greater than 1 and it's odd so it's greater than or equal to 3.
However, this means that p plus 1 is greater than or equal to 4, and p plus 1 is even,
so the number p plus 1 has
three distinct positive prime factors…
three distinct factors…positive factors: 1, 2, and p plus 1.
Hence, the hypothesis that p and p plus 1 are prime is false
because p plus 1 is not prime in this case,
unless the implication is true, right?
Remember A implies B, if A is false then A implies B is true.
Case 2: p is even,
then p must have factors 1, 2, and p.
However, according to the hypothesis...
so remember the interesting cases when the hypothesis is true, right,
so the hypothesis here is true. p and p plus 1 are prime,
then what do we have? Then we have p is prime, so
according to the hypothesis p is prime,
and p is greater than 1 as a result
and p only has two distinct positive factors thus, p equals 2.
So when the conclusion is true the implication is also true, right?
A implies B and the conclusion B is true,
then A implies B is true.
Okay.
Hopefully this helps and thank you for listening.