1 00:00:00,000 --> 00:00:04,600 Hello everyone. In this video, 
we're going to prove the claim 2 00:00:04,600 --> 00:00:08,300 that, "if p and p plus 
1 are prime, 3 00:00:08,300 --> 00:00:11,100 then p must be 
equal to 2." 4 00:00:11,100 --> 00:00:12,500 5 00:00:12,500 --> 00:00:16,566 Now there are many ways 
to prove this claim. 6 00:00:16,566 --> 00:00:20,933 I'm going to give a proof that breaks this into cases, 7 00:00:20,933 --> 00:00:26,000 and let me try to explain the 
reasoning behind this. 8 00:00:26,000 --> 00:00:28,000 So when reading this, 
you should believe 9 00:00:28,000 --> 00:00:30,200 almost instantly that 
this is true, right? 10 00:00:30,200 --> 00:00:31,633 In your mind, you should 
think okay well, 11 00:00:31,633 --> 00:00:36,000 p and p plus 1, well one of these two numbers must be even... 12 00:00:36,000 --> 00:00:40,000 and because of that, 2 must be 
a factor of the even number 13 00:00:40,000 --> 00:00:43,066 so one of these prime 
numbers must be 2. 14 00:00:43,066 --> 00:00:45,533 That's sort of your intuition here. 15 00:00:45,533 --> 00:00:49,300 I'm going to try to write this as 
best and as formally as I can 16 00:00:49,300 --> 00:00:52,000 with the tools 
that we have, 17 00:00:52,000 --> 00:00:53,900 and we'll go 
from there. 18 00:00:53,900 --> 00:00:56,133 So as I said, I'm going to break this into cases 19 00:00:56,133 --> 00:00:59,000 and because of what I just said 
about 2 dividing numbers, 20 00:00:59,000 --> 00:01:01,166 it seems right to use 
a parity argument. 21 00:01:01,166 --> 00:01:03,266 So... 22 00:01:03,266 --> 00:01:04,300 23 00:01:04,300 --> 00:01:06,500 So, I'm going to break 
this up into Case 1: 24 00:01:06,500 --> 00:01:07,900 25 00:01:07,900 --> 00:01:09,866 "p is odd". 26 00:01:09,866 --> 00:01:11,200 27 00:01:11,200 --> 00:01:13,000 So here's the start of 
my parity argument. 28 00:01:13,000 --> 00:01:15,433 p is odd so p is an odd prime number. 29 00:01:15,433 --> 00:01:18,300 As we discussed in class, 
what does this mean? 30 00:01:18,300 --> 00:01:21,133 This means, "then p 31 00:01:21,133 --> 00:01:22,166 32 00:01:22,166 --> 00:01:24,533 is greater than 
or equal to 3". 33 00:01:24,533 --> 00:01:24,566 34 00:01:24,566 --> 00:01:26,933 So if p is odd, then p is 
greater than or equal to 3 35 00:01:26,933 --> 00:01:29,500 because it's an odd number 
and it's a prime number 36 00:01:29,500 --> 00:01:31,433 and we know that prime numbers are greater than 1, 37 00:01:31,433 --> 00:01:33,500 so p must be greater 
than or equal to 3. 38 00:01:33,500 --> 00:01:35,600 39 00:01:35,600 --> 00:01:38,700 However this means, what 
about p plus 1, right? 40 00:01:38,700 --> 00:01:42,533 So then p plus 1 is greater 
than or equal to 4 41 00:01:42,533 --> 00:01:44,733 42 00:01:44,733 --> 00:01:48,000 and p plus 
1 is even. 43 00:01:48,000 --> 00:01:49,500 44 00:01:49,500 --> 00:01:50,866 Thus, 45 00:01:50,866 --> 00:01:55,133 p plus 1 has...
what? 46 00:01:55,133 --> 00:01:59,166 Well it has… remember p plus 1, what does it must have? Well 47 00:01:59,166 --> 00:02:02,533 it has more factors 
than we want, right, 48 00:02:02,533 --> 00:02:04,533 because it's gonna have 
2 as a factor, right? 49 00:02:04,533 --> 00:02:06,700 p has 1 comma 2, 50 00:02:06,700 --> 00:02:10,833 and p plus 1 
as factors 51 00:02:10,833 --> 00:02:10,866 52 00:02:10,866 --> 00:02:15,266 So let's go through this. Now let's see, so p 
is odd then p is greater than or equal to 3. 53 00:02:15,266 --> 00:02:19,200 However, p plus 1 is greater than or equal to 4, p plus 1 is even. 54 00:02:19,200 --> 00:02:20,100 55 00:02:20,100 --> 00:02:21,400 What does 
that mean? 56 00:02:21,400 --> 00:02:25,533 So p plus 1 has 1, 2, 
and p plus 1 as factors. 57 00:02:25,533 --> 00:02:27,833 What does this mean 
about our statement? 58 00:02:27,833 --> 00:02:31,166 In this case, "if p and p 
plus 1 are prime". 59 00:02:31,166 --> 00:02:33,866 So if p was 
an odd prime, 60 00:02:33,866 --> 00:02:36,366 then we know that p 
plus 1 can't be prime. 61 00:02:36,366 --> 00:02:38,866 62 00:02:38,866 --> 00:02:41,633 So "p and p plus 1 are prime", 
the hypothesis, is false. 63 00:02:41,633 --> 00:02:44,900 With the hypothesis false, then the implication is true. 64 00:02:44,900 --> 00:02:46,533 65 00:02:46,533 --> 00:02:49,233 "Hence, the hypothesis 66 00:02:49,233 --> 00:02:54,866 that p and p plus 1 
are prime is false. 67 00:02:54,866 --> 00:02:59,366 Thus, the implication is true." 68 00:02:59,366 --> 00:03:02,066 69 00:03:02,066 --> 00:03:04,800 So we're done in this case, 
we've proven the implication. 70 00:03:04,800 --> 00:03:08,133 Once the hypothesis is false, 
the implication has to be true. 71 00:03:08,133 --> 00:03:10,066 So in this case 
we're done. 72 00:03:10,066 --> 00:03:13,400 73 00:03:13,400 --> 00:03:16,433 So now in Case 2, 74 00:03:16,433 --> 00:03:19,133 we'll look at p 
being even. 75 00:03:19,133 --> 00:03:19,166 76 00:03:19,166 --> 00:03:21,433 In this case, what 
do we know? 77 00:03:21,433 --> 00:03:22,800 78 00:03:22,800 --> 00:03:25,233 If p is even, then 79 00:03:25,233 --> 00:03:27,366 what are the 
factors of p? 80 00:03:27,366 --> 00:03:29,733 81 00:03:29,733 --> 00:03:33,000 Well 1 is still a 
factor, p is even 82 00:03:33,000 --> 00:03:37,233 which means that 2 divides 
p so 2 is a factor of p, 83 00:03:37,233 --> 00:03:41,233 and p is also 
a factor of p. 84 00:03:41,233 --> 00:03:42,966 85 00:03:42,966 --> 00:03:46,233 So p is even then p 
has factors 1, 2, and p. 86 00:03:46,233 --> 00:03:46,266 87 00:03:46,266 --> 00:03:46,333 88 00:03:46,333 --> 00:03:50,866 However, according to the 
hypothesis, p is prime. 89 00:03:50,866 --> 00:03:50,966 90 00:03:50,966 --> 00:03:52,133 91 00:03:52,133 --> 00:03:55,600 So p must have factors 1, 2, p. However, according to the hypothesis is p is prime. 92 00:03:55,600 --> 00:03:58,166 93 00:03:58,166 --> 00:04:01,033 And what can we conclude 
from this now? 94 00:04:01,033 --> 00:04:02,166 95 00:04:02,166 --> 00:04:04,400 p is prime so p is 
greater than 1 96 00:04:04,400 --> 00:04:05,666 97 00:04:05,666 --> 00:04:08,933 and p only has 98 00:04:08,933 --> 00:04:10,266 99 00:04:10,266 --> 00:04:14,966 two distinct 
positive factors 100 00:04:14,966 --> 00:04:20,766 I should write up here positive as well so maybe I'll write this in bold. 101 00:04:20,766 --> 00:04:22,700 So a little bit of 
a typo up there 102 00:04:22,700 --> 00:04:25,100 because we're only looking at 
positive factors of these numbers. 103 00:04:25,100 --> 00:04:26,933 104 00:04:26,933 --> 00:04:29,300 However, according to the 
hypothesis p is prime 105 00:04:29,300 --> 00:04:32,466 so thus p is greater than or 
equal to 1, p only has two 106 00:04:32,466 --> 00:04:34,766 distinct positive factors. 107 00:04:34,766 --> 00:04:37,866 So what does this mean? We've written 
down three factors so two of them 108 00:04:37,866 --> 00:04:41,100 must be the same and the only two 
that can be the same are 2 and p. 109 00:04:41,100 --> 00:04:43,900 Thus, p 
equals 2. 110 00:04:43,900 --> 00:04:46,833 This concludes 
the proof. 111 00:04:46,833 --> 00:04:49,366 Let's read it all 
one more time 112 00:04:49,366 --> 00:04:51,766 just so that we can look 
at the cases. So because 113 00:04:51,766 --> 00:04:53,400 we argued that 114 00:04:53,400 --> 00:04:55,700 p and p plus 1, one of these have to be even, 115 00:04:55,700 --> 00:04:58,500 that's what we got when 
we read this hypothesis. 116 00:04:58,500 --> 00:05:01,633 It seemed to believe 
that we should use 117 00:05:01,633 --> 00:05:04,400 a parity argument and 
break this into cases. 118 00:05:04,400 --> 00:05:06,733 So Case 1 when p is 
odd, we know that 119 00:05:06,733 --> 00:05:10,100 p has to be greater than or equal 
to 3 because p is a prime number, 120 00:05:10,100 --> 00:05:13,100 so it's greater than 1 and it's odd 
so it's greater than or equal to 3. 121 00:05:13,100 --> 00:05:17,633 However, this means that p plus 1 is greater than or equal to 4, and p plus 1 is even, 122 00:05:17,633 --> 00:05:21,100 so the number 
p plus 1 has 123 00:05:21,100 --> 00:05:23,433 124 00:05:23,433 --> 00:05:27,433 three distinct positive 
prime factors… 125 00:05:27,433 --> 00:05:33,100 three distinct factors…positive 
factors: 1, 2, and p plus 1. 126 00:05:33,100 --> 00:05:36,300 Hence, the hypothesis that p and 
p plus 1 are prime is false 127 00:05:36,300 --> 00:05:38,266 because p plus 1 is not prime in this case, 128 00:05:38,266 --> 00:05:40,400 unless the implication 
is true, right? 129 00:05:40,400 --> 00:05:45,566 Remember A implies B, if A is 
false then A implies B is true. 130 00:05:45,566 --> 00:05:46,533 131 00:05:46,533 --> 00:05:48,500 Case 2: p is even, 132 00:05:48,500 --> 00:05:53,100 then p must have 
factors 1, 2, and p. 133 00:05:53,100 --> 00:05:57,100 However, according 
to the hypothesis... 134 00:05:57,100 --> 00:05:58,166 135 00:05:58,166 --> 00:06:01,433 so remember the interesting cases when the hypothesis is true, right, 136 00:06:01,433 --> 00:06:05,100 so the hypothesis here is true. 
p and p plus 1 are prime, 137 00:06:05,100 --> 00:06:09,100 then what do we have? Then 
we have p is prime, so 138 00:06:09,100 --> 00:06:11,666 according to the 
hypothesis p is prime, 139 00:06:11,666 --> 00:06:13,933 and p is greater 
than 1 as a result 140 00:06:13,933 --> 00:06:17,900 and p only has two distinct positive 
factors thus, p equals 2. 141 00:06:17,900 --> 00:06:22,200 So when the conclusion is true 
the implication is also true, right? 142 00:06:22,200 --> 00:06:25,900 A implies B and the conclusion B is true, 143 00:06:25,900 --> 00:06:27,966 then A implies 
B is true. 144 00:06:27,966 --> 00:06:29,800 145 00:06:29,800 --> 00:06:31,633 Okay. 146 00:06:31,633 --> 00:06:35,499 Hopefully this helps and 
thank you for listening.