>> Welcome back. And this screencast is going to be a second example of proof by contraposition. Remember, in the first screencast in this series, we learned that proof by contraposition is just merely proving the contrapositive of a conditional statement instead of the original conditional statement. And we would want to do such a thing because maybe the conditional statement that we were originally given is somehow hard to work with in terms of a direct proof. So, we're going to construct a direct proof of a different statement. And here's the statement we're going to play with this time. So, suppose a and b and n are all positive integers. And we're going to prove that if n equals a times b, then either a is less than or equal to the square root of n, or b is less than or equal to the square root of n. Now, a direct proof of this statement would assume n is equal to a times b and do some math and show that either a is less than radical n or b is less than or equal to radical n. Now, there's no obvious way to go from this simple equality to one of these two inequalities. It's kind of like the even, trying to prove that if n squared is even, then n is even. There's no obvious way to prove that the square root of 2 times k is an integer at all, much less than even integer. So, since there's no obvious way to go directly, we're going to go indirectly. So, the main challenge here is to form the contrapositive of the statement. Let me get rid of the markings I have here and just isolate the hypothesis and conclusion. Here's the hypothesis that n is equal to ab. I'll call that p. And here's the conclusion. And notice the conclusion is a disjunction. It's an either/or. Okay, so there's the q. So, the contrapositive would say if not q, then not p. So, let's think about what that would look like. I need to form the negation of this thing in here. So, I would need to negate the statement an is less than or equal to radical n, or b is less than or equal to radical n. If I could mix some logic and math. Now, we know from our logical equivalency rules that this actually transforms into something. I would negate a less than or equal to radical n. And this would turn into an and negate b less than or equal to  or less than or equal to radial n as we. Okay, that's what we call De Morgan's laws back when we first learned about logical equivalencies. Now, just one more step, I think we'll be able to write this. When I negate this inequality, I get this inequality. So, a is greater than n, radical n, and b is greater than radical n. Now, I think that gives us enough information to write down the contrapositive. Let's do this kind of over in this white space here. So, the contrapositive of a statement that I am being asked to prove, the contrapositive of my conjecture says that a, b and n are positive integers that if a is bigger than square root of n, and b is bigger than square root of n, then I have to put the negation of p, and that's just simply n is not equal to ab. Okay, there's the contrapositive. And the step here that was a little bit different than in the previous example was that I had to do a little bit of work with my logical equivalency rules to actually get the hypothesis of that contrapositive. A hypothesis is a negation of something. And I had to do a little work to get there. So, let's prove that statement instead. If I can prove this if then statement, it's equivalent to having proved the conjecture they're being asked to prove. And it makes a little more sense this time because a direct proof of this statement would assume that something about a and something about b, and it's a little easier to think about going from knowledge of a and b to knowledge of a times b than it is going backwards. So, let's move over to a blank space here, and we'll make a no show table, one calling for the step, one calling for the no, and make that a little longer n than the one calling for the reason. Okay, so we are proving the original conjecture by proving it's contrapositive. So, we'll start by assuming that a is bigger than square root of n and b is bigger than the square root of n. And that is the hypothesis, not the very original hypothesis, but the hypothesis of the contrapositive. At the very end of this proof, I'm going to conclude that n is not equal to ab. We don't know exactly why that is yet. However, I do see that I want to say something eventually about a times b, and I'm given knowledge about a, and I'm given information about b, so maybe a good next step would just be to multiply those two things together. So, a times b, let's think about what that is. Well, a is bigger than radical n, and b is bigger than radical n, so the two of them multiplied together will be bigger than radical n times radical n. That's just algebra. That's just multiplying the sides of inequalities together. Now, just take a look at what's on the right hand side of that inequality. This is telling me that ab is bigger than this. This side right here is equal to, well, you take radical n times itself, that's just n, isn't it? So, if you follow, I'm just going to make a third line here, this is not totally necessary, but it's just going to condense what these two lines tell me, that ab is bigger than n, okay? If it's bigger than this thing, and this thing is equal to this thing, then ab is bigger than this thing. Now, and, again, I don't know, even know what I would call that reason. I could just call it algebra. It seems like we dumped that in. But really what I did here was just combine all the, both lines of this inequality together. Now, if ab is bigger than n, one of the things that means is that it's not equal to n. So, this is actually a very sparse no show table. If ab is bigger than n, then it's not equal to n. Okay, we could call that basic arithmetic. If you want to be technical about it, we're using something called the law of trichotomy, trichotomy. I can spell that, okay? The law of trichotomy says that given two numbers, I'll just put this up here, say x and y, one of the three has to hold. Either x is equal to y, x is bigger than y, or x is less than y. But only one of those three things can hold. So, trichotomy. And since the greater than relationship holds between these two numbers, the equality cannot possibly hold. So, the law of trichotomy from arithmetic gets us to our answer here, to our final line. So, this is a really, really quick proof if you understand the basic arithmetic behind it. It's only five lines long. And really you could argue is four lines long because this line P3 is kind of not really necessary, okay? So, that was done using the contrapositive. What we've done is we've proven the contrapositive of the original conjecture we were asked to prove. And so the original conjecture is true.