Hello everyone. In this video, we're going to talk about an if and only if proof using divisibility.
Question: $6\mid(b-a)\Leftrightarrow 2\mid(b-a)\land3\mid(b-a)$ for all $a,b\in\mathbb{Z}$.
So this is my claim. Now with an if and only if proof, we have to prove two directions. We have to prove the forward direction and the reverse direction. So in other words we have to prove 2 things:
Let's see how that goes in practice. We’re going to assume that $6\mid(b-a)$. Some people might actually include the statement, “for the forward direction”, either way is fine. It's very clear what you're doing when you're immediately writing assume that $6\mid(b-a)$.
How are we going to get the $2$ and the $3$ out of $6\mid(b-a)$? So the things that should be running through your head are okay well I know that $6$ is divisible by $2$, and in fact $6$ is divisible by $3$. Can that help me to get to these two results?
Hopefully you're thinking back to what you did this week, and you're thinking, “okay, I remember something about $2$ dividing a number and then that number dividing something else, and then $2$ must divide that other thing.” And that's exactly what I want, that's transitivity.
So let's actually do that. As $6=2(3)$, we have that $2\mid 6$ and we also have that $3\mid 6$. Since $6\mid(b-a)$, applying transitivity twice, we have that $2\mid(b-a)$ and $3\mid(b-a)$.
So you might have called this transitivity, Transitivity of Divisibility, TD, all of those names are perfectly fine to get this result. So we have the “and” statement, that's exactly our conclusion, we're done the forward direction.
At this point, I usually like to start a new paragraph and say, for the reverse direction, I'm going to assume that $2\mid(b-a)\land 3\mid(b-a)$.
Okay, so I have these two smaller numbers that divide $(b-a)$ and I want to show that $6\mid(b-a)$. At this point. it might not be obvious how to combine these. We don't have any theorem that says that like I can multiply these two things and nor should we, right? For example, $2\mid 2$ and $2\mid 2$, but $4\nmid 2$, right? $4\mid 4$, that's fine, but I can't just multiply these two in the sort of obvious way.
So after howling and humming for a little bit, you might say to yourself okay I don't know what to do. I'm going to just use the definition.
So by definition, there exists integers $k$ and $\ell$ such that $2k=b-a$, and $3\ell=b-a$.
Alright, maybe still not $100\%$ sure what we're doing at this point. Well I know that $2k=b-a=3\ell$ so $2k=3\ell$.
Here's the interesting part. So now I have $2k$ so this is going to be even, and I have $3\ell$, the parity depends on $\ell$. And in fact, $3\ell$ is even if and only if $\ell$ is even, and is odd if and only if $\ell$ is odd.
Thus $3\ell$ is even which is possible if and only if $\ell=2m$ for some integer $m$.
So $\ell=2m$, now I'm going to use this equality, $3\ell=b-a$.
So since $3\ell=b-a$, we have that $b-a=3(2m)=6m$, and hence by definition, we have that $6\mid(b-a).\quad\blacksquare$
So the converse direction, a little bit more involved. You need a little bit of a clever idea here to realize that I have $2k=3\ell$ so I know therefore that $\ell$ must be even.
There's a lot of ways to that too. You could say, depending on where you are in the course, since $2\nmid 3$, and $2$ is a prime number, $2\mid\ell$. I believe that's called Euclid's Lemma, there's a whole bunch of different ways to do this.
At this point though, you're probably best off saying well okay $3\ell$ must be even, $3$ is odd, so if $\ell$ is odd, then $3\ell$ is odd. That's not even, that's a contradiction. So therefore, $\ell$ must be even.
Usually one direction’s pretty easy to prove and usually one direction’s a little bit harder, but that's it. So that's all like to say. Thank you very much and hope this helped.