Hello everyone. In this video, we're going to talk about an if and only if proof using divisibility.
So here we have 6
divides b minus a if and only if 2 divides b minus a and
3 divides b minus a. So I've been a little bit sloppy here
with what these symbols mean,
but we're going to assume here that a and b
are integers and this is going to hold for any integers a and b.
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 that this statement implies this statement,
and then we have to prove that this statement implies this statement.
Let's see how that goes in practice.
So, proof.
We’re going to assume
that 6 divides b minus a.
So we're going to assume…
we're going to prove the forward direction.
Some people might actually include the statement,
“for the forward
direction” and then use little a here.
Assume that 6 divides b minus a. Either way is fine.
It's very clear what you're doing when you're immediately writing assume that 6 divides b minus a.
How are we going to get the 2 and the 3 out of 6 divides b minus 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?
And then 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. So…
since 2 divides 6…
or maybe I should say - let's do this a little bit more precisely.
So as 6 is equal to 2 times 3,
we have that
2 divides 6
and we also have that 3 divides 6.
Since 6 divides b minus a,
applying
transitivity twice,
we have
that 2 divides b minus a
and 3 divides b minus a.
So you might have called this transitivity, Transitivity of Divisibility, TD,
all of those names are perfectly fine to get this result.
Okay.
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 divides b minus a
and 3 divides b minus a.
Okay, so
I have these two smaller numbers that divide b minus a
and I want to show that 6 divides b minus 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 divides 2
and 2 divides 2, but 4 does not divide 2, right?
4 would divide 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 -
I'm just going to try to…
I'm going to just use the definition. So by definition,
there exists
integers
k and l such that
2 times k is equal to b minus a,
and 3 times l is also equal to
b minus a.
Alright,
maybe still not a hundred percent sure what we're doing at this point.
I know that b minus a are equal to these two things so hence, I can say
2 times k is equal to 3 times l, alright.
Here's the interesting part. So now I have
2 times k, so this is going to be even,
and I have 3 times l, this is… this depends…
parity depends on l.
And in fact, if this is even if and only if l is even,
and is odd if and only if I is odd.
So I can actually say,
so thus
3 times l is even
which is possible
if and only if
I is equal to 2 times m for some
integer
m.
So l is equal to 2m, I'm going to use this
equality here. So since
3l is equal to b minus a,
we have
that b minus a is equal to 3
times 2m, that is equal to 6m,
and hence by definition,
we have
that 6 divides
b minus a.
This finishes our proof.
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 is equal to 3l so I know therefore that l must be even since -
there's a lot of ways to that too. You could say well since 2 doesn't divide…
depending on where you are in the course, since 2 doesn't divide 3,
and 2 is a prime number, 2 must divide l.
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 times l must be even,
3 is odd, so if l is odd, then 3 times l is odd.
That's not even, that's a contradiction. So therefore, l must be even.
So forward direction - 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 I have to say.
Thank you very much and hope this helped.