1 00:00:00,000 --> 00:00:05,000 Hello everyone. In this video, we're going to talk 
about an if and only if proof using divisibility. 2 00:00:05,000 --> 00:00:07,900 So here we have 6 3 00:00:07,900 --> 00:00:11,700 divides b minus a if and only 
if 2 divides b minus a and 4 00:00:11,700 --> 00:00:15,266 3 divides b minus a. So I've 
been a little bit sloppy here 5 00:00:15,266 --> 00:00:17,666 with what these symbols mean, 6 00:00:17,666 --> 00:00:20,000 but we're going to assume here that a and b 7 00:00:20,000 --> 00:00:24,333 are integers and this is going to 
hold for any integers a and b. 8 00:00:24,333 --> 00:00:25,833 9 00:00:25,833 --> 00:00:28,366 So this is my claim. Now 
with an if and only if proof, 10 00:00:28,366 --> 00:00:30,466 we have to prove two directions. We have to prove 11 00:00:30,466 --> 00:00:33,266 the forward direction and the reverse direction. 12 00:00:33,266 --> 00:00:36,966 So in other words we have to prove that 
this statement implies this statement, 13 00:00:36,966 --> 00:00:41,366 and then we have to prove that this 
statement implies this statement. 14 00:00:41,366 --> 00:00:43,533 Let's see how that goes in practice. 15 00:00:43,533 --> 00:00:45,666 So, proof. 16 00:00:45,666 --> 00:00:46,966 17 00:00:46,966 --> 00:00:49,200 We’re going to assume 18 00:00:49,200 --> 00:00:51,200 19 00:00:51,200 --> 00:00:55,066 that 6 divides b minus a. 20 00:00:55,066 --> 00:00:57,533 So we're going to assume… 21 00:00:57,533 --> 00:01:00,000 we're going to prove the forward direction. 22 00:01:00,000 --> 00:01:02,266 23 00:01:02,266 --> 00:01:05,533 Some people might actually include the statement, 24 00:01:05,533 --> 00:01:08,600 “for the forward 25 00:01:08,600 --> 00:01:12,500 26 00:01:12,500 --> 00:01:15,300 direction” and then use little a here. 27 00:01:15,300 --> 00:01:16,500 28 00:01:16,500 --> 00:01:19,433 Assume that 6 divides b 
minus a. Either way is fine. 29 00:01:19,433 --> 00:01:24,233 It's very clear what you're doing when you're 
immediately writing assume that 6 divides b minus a. 30 00:01:24,233 --> 00:01:28,333 How are we going to get the 2 and 
the 3 out of 6 divides b minus a? 31 00:01:28,333 --> 00:01:31,933 So the things that should be running through your 
head are okay well I know that 6 is divisible by 2, 32 00:01:31,933 --> 00:01:34,300 and in fact 6 is divisible by 3. 33 00:01:34,300 --> 00:01:35,100 34 00:01:35,100 --> 00:01:37,766 Can that help me to get to these two results? 35 00:01:37,766 --> 00:01:40,066 And then hopefully you're 
thinking back to what you did 36 00:01:40,066 --> 00:01:43,066 this week, and you're thinking, “okay, 37 00:01:43,066 --> 00:01:45,533 I remember something about 2 dividing a number and then 38 00:01:45,533 --> 00:01:48,866 that number dividing something else, 
and then 2 must divide that other thing.” 39 00:01:48,866 --> 00:01:51,966 And that's exactly what I want, that's transitivity. 40 00:01:51,966 --> 00:01:54,233 So let's actually do that. So… 41 00:01:54,233 --> 00:01:55,433 42 00:01:55,433 --> 00:01:58,300 since 2 divides 6… 43 00:01:58,300 --> 00:02:00,366 44 00:02:00,366 --> 00:02:04,133 or maybe I should say - let's do this a little bit more precisely. 45 00:02:04,133 --> 00:02:08,600 So as 6 is equal to 2 times 3, 46 00:02:08,600 --> 00:02:09,333 47 00:02:09,333 --> 00:02:11,266 we have that 48 00:02:11,266 --> 00:02:13,433 49 00:02:13,433 --> 00:02:15,533 2 divides 6 50 00:02:15,533 --> 00:02:18,700 and we also have that 3 divides 6. 51 00:02:18,700 --> 00:02:20,800 52 00:02:20,800 --> 00:02:24,566 Since 6 divides b minus a, 53 00:02:24,566 --> 00:02:26,400 applying 54 00:02:26,400 --> 00:02:27,300 55 00:02:27,300 --> 00:02:29,333 transitivity twice, 56 00:02:29,333 --> 00:02:30,166 57 00:02:30,166 --> 00:02:34,166 58 00:02:34,166 --> 00:02:36,300 we have 59 00:02:36,300 --> 00:02:38,500 60 00:02:38,500 --> 00:02:41,800 that 2 divides b minus a 61 00:02:41,800 --> 00:02:42,533 62 00:02:42,533 --> 00:02:45,733 and 3 divides b minus a. 63 00:02:45,733 --> 00:02:50,900 So you might have called this 
transitivity, Transitivity of Divisibility, TD, 64 00:02:50,900 --> 00:02:55,100 all of those names are 
perfectly fine to get this result. 65 00:02:55,100 --> 00:02:56,366 Okay. 66 00:02:56,366 --> 00:03:00,933 So we have the “and” statement, that's exactly 
our conclusion, we're done the forward direction. 67 00:03:00,933 --> 00:03:02,566 68 00:03:02,566 --> 00:03:05,500 At this point, I usually like to 
start a new paragraph and say, 69 00:03:05,500 --> 00:03:08,000 for the reverse direction, 70 00:03:08,000 --> 00:03:12,666 71 00:03:12,666 --> 00:03:14,733 I'm going to assume 72 00:03:14,733 --> 00:03:16,066 73 00:03:16,066 --> 00:03:19,266 that 2 divides b minus a 74 00:03:19,266 --> 00:03:20,500 75 00:03:20,500 --> 00:03:23,533 and 3 divides b minus a. 76 00:03:23,533 --> 00:03:26,733 77 00:03:26,733 --> 00:03:28,466 Okay, so 78 00:03:28,466 --> 00:03:31,866 I have these two smaller 
numbers that divide b minus a 79 00:03:31,866 --> 00:03:34,500 and I want to show that 6 divides b minus a. 80 00:03:34,500 --> 00:03:36,666 At this point. it might not be 
obvious how to combine these. 81 00:03:36,666 --> 00:03:39,933 We don't have any theorem that says 
that like I can multiply these two things 82 00:03:39,933 --> 00:03:43,100 and nor should we, right? For example, 2 divides 2 83 00:03:43,100 --> 00:03:46,900 and 2 divides 2, but 4 
does not divide 2, right? 84 00:03:46,900 --> 00:03:49,733 4 would divide 4, that's fine, 85 00:03:49,733 --> 00:03:53,900 but I can't just multiply these 
two in the sort of obvious way. 86 00:03:53,900 --> 00:03:55,666 So after howling and humming for a little bit, 87 00:03:55,666 --> 00:03:59,200 you might say to yourself okay I 
don't know what to do. I'm going to - 88 00:03:59,200 --> 00:04:01,600 I'm just going to try to… 89 00:04:01,600 --> 00:04:02,866 90 00:04:02,866 --> 00:04:06,000 I'm going to just use the 
definition. So by definition, 91 00:04:06,000 --> 00:04:09,366 92 00:04:09,366 --> 00:04:11,666 there exists 93 00:04:11,666 --> 00:04:14,033 94 00:04:14,033 --> 00:04:16,366 integers 95 00:04:16,366 --> 00:04:20,000 k and l such that 96 00:04:20,000 --> 00:04:22,900 97 00:04:22,900 --> 00:04:27,100 2 times k is equal to b minus a, 98 00:04:27,100 --> 00:04:30,233 and 3 times l is also equal to 99 00:04:30,233 --> 00:04:31,366 100 00:04:31,366 --> 00:04:33,433 b minus a. 101 00:04:33,433 --> 00:04:37,033 102 00:04:37,033 --> 00:04:38,766 Alright, 103 00:04:38,766 --> 00:04:42,733 maybe still not a hundred percent sure what we're doing at this point. 104 00:04:42,733 --> 00:04:46,733 I know that b minus a are equal to 
these two things so hence, I can say 105 00:04:46,733 --> 00:04:47,900 106 00:04:47,900 --> 00:04:51,533 2 times k is equal to 3 times l, alright. 107 00:04:51,533 --> 00:04:52,966 108 00:04:52,966 --> 00:04:55,133 Here's the interesting part. So now I have 109 00:04:55,133 --> 00:04:57,900 2 times k, so this is going to be even, 110 00:04:57,900 --> 00:04:58,666 111 00:04:58,666 --> 00:05:02,333 and I have 3 times l, this is… this depends… 112 00:05:02,333 --> 00:05:02,933 113 00:05:02,933 --> 00:05:05,033 parity depends on l. 114 00:05:05,033 --> 00:05:08,500 115 00:05:08,500 --> 00:05:11,766 And in fact, if this is even if and only if l is even, 116 00:05:11,766 --> 00:05:13,633 and is odd if and only if I is odd. 117 00:05:13,633 --> 00:05:15,800 So I can actually say, 118 00:05:15,800 --> 00:05:17,733 so thus 119 00:05:17,733 --> 00:05:18,633 120 00:05:18,633 --> 00:05:22,833 3 times l is even 121 00:05:22,833 --> 00:05:24,066 122 00:05:24,066 --> 00:05:26,166 which is possible 123 00:05:26,166 --> 00:05:29,200 124 00:05:29,200 --> 00:05:32,333 if and only if 125 00:05:32,333 --> 00:05:33,700 126 00:05:33,700 --> 00:05:37,133 I is equal to 2 times m for some 127 00:05:37,133 --> 00:05:38,966 128 00:05:38,966 --> 00:05:41,166 integer 129 00:05:41,166 --> 00:05:43,200 m. 130 00:05:43,200 --> 00:05:47,000 So l is equal to 2m, I'm going to use this 131 00:05:47,000 --> 00:05:48,900 132 00:05:48,900 --> 00:05:51,866 equality here. So since 133 00:05:51,866 --> 00:05:52,800 134 00:05:52,800 --> 00:05:56,000 3l is equal to b minus a, 135 00:05:56,000 --> 00:05:56,866 136 00:05:56,866 --> 00:05:58,433 we have 137 00:05:58,433 --> 00:06:00,300 138 00:06:00,300 --> 00:06:03,333 that b minus a is equal to 3 139 00:06:03,333 --> 00:06:06,266 times 2m, that is equal to 6m, 140 00:06:06,266 --> 00:06:07,700 141 00:06:07,700 --> 00:06:11,000 and hence by definition, 142 00:06:11,000 --> 00:06:13,600 143 00:06:13,600 --> 00:06:15,700 we have 144 00:06:15,700 --> 00:06:18,233 145 00:06:18,233 --> 00:06:21,100 that 6 divides 146 00:06:21,100 --> 00:06:21,666 147 00:06:21,666 --> 00:06:23,466 b minus a. 148 00:06:23,466 --> 00:06:25,566 This finishes our proof. 149 00:06:25,566 --> 00:06:26,866 150 00:06:26,866 --> 00:06:28,966 So the converse direction, 
a little bit more involved. 151 00:06:28,966 --> 00:06:32,633 You need a little bit of a 
clever idea here to realize that 152 00:06:32,633 --> 00:06:37,566 I have 2k is equal to 3l so I know 
therefore that l must be even since - 153 00:06:37,566 --> 00:06:40,666 there's a lot of ways to that too. You 
could say well since 2 doesn't divide… 154 00:06:40,666 --> 00:06:41,600 155 00:06:41,600 --> 00:06:44,566 depending on where you are in the 
course, since 2 doesn't divide 3, 156 00:06:44,566 --> 00:06:47,066 and 2 is a prime number, 2 must divide l. 157 00:06:47,066 --> 00:06:47,766 158 00:06:47,766 --> 00:06:50,433 I believe that's called Euclid's Lemma, there's 
a whole bunch of different ways to do this. 159 00:06:50,433 --> 00:06:53,200 At this point though, you're probably best off saying 160 00:06:53,200 --> 00:06:56,033 well okay 3 times l must be even, 161 00:06:56,033 --> 00:06:59,466 3 is odd, so if l is odd, then 3 times l is odd. 162 00:06:59,466 --> 00:07:02,733 That's not even, that's a contradiction. 
So therefore, l must be even. 163 00:07:02,733 --> 00:07:04,600 164 00:07:04,600 --> 00:07:07,833 So forward direction - usually one 
direction’s pretty easy to prove 165 00:07:07,833 --> 00:07:10,500 and usually one direction’s a little bit harder, 166 00:07:10,500 --> 00:07:11,066 167 00:07:11,066 --> 00:07:12,800 but that's it. So that's all I have to say. 168 00:07:12,800 --> 00:07:14,566 Thank you very much and hope this helped.