1
00:00:00,000 --> 00:00:04,200
Hello everyone. So in this video, I'd like
to prove the following proposition.

2
00:00:04,200 --> 00:00:08,733
I didn't prove this in class, 
but I alluded to its truth.

3
00:00:08,733 --> 00:00:11,466
Now I'll actually 
demonstrate it.

4
00:00:11,466 --> 00:00:17,366
So d divides a and d divides b
then d divides the gcd of a and b

5
00:00:17,366 --> 00:00:17,933


6
00:00:17,933 --> 00:00:21,933
It's perhaps kind of tough to 
know where to start; it really is.

7
00:00:21,933 --> 00:00:25,200
d divides a and d divides b 
doesn't really tell us too much,

8
00:00:25,200 --> 00:00:27,366
Right? We need to use 
something about the gcd here

9
00:00:27,366 --> 00:00:31,100
in order to get the last division. 
So we're gonna start with the gcd.

10
00:00:31,100 --> 00:00:33,466


11
00:00:33,466 --> 00:00:38,500
I usually write a letter for the 
gcd, just to make my life easier,

12
00:00:38,500 --> 00:00:41,400
and so that I don't have to 
write gcd a hundred times.

13
00:00:41,400 --> 00:00:45,800
So let e equal the 
gcd of a and b.

14
00:00:45,800 --> 00:00:47,266
Now what am I gonna do? Well, 

15
00:00:47,266 --> 00:00:49,766
we have some hammers from 
class, so let's try to use one,

16
00:00:49,766 --> 00:00:53,166
and the one I'm going to use is 
Bezout's Lemma, so the back
             substitution.

17
00:00:53,166 --> 00:00:56,666
"By Bezout's Lemma,

18
00:00:56,666 --> 00:01:03,633
we know there exist
integers x and y

19
00:01:03,633 --> 00:01:09,633
such that:

20
00:01:09,633 --> 00:01:12,966
e is equal to a x plus b y."

21
00:01:12,966 --> 00:01:13,000


22
00:01:13,000 --> 00:01:15,033
Alright so that's what 
Bezout's Lemma says.

23
00:01:15,033 --> 00:01:17,900
It says that you can write the gcd 
as a linear combination of a and b.

24
00:01:17,900 --> 00:01:22,400
Okay, so now with this hammer in 
place, the proof is in good shape.

25
00:01:22,400 --> 00:01:24,166
So now, let's actually use the hypothesis, 

26
00:01:24,166 --> 00:01:26,400
which is d divides a and d divides b.

27
00:01:26,400 --> 00:01:33,900
Since d divides a and d divides b,

28
00:01:33,900 --> 00:01:40,100
by divisibility of 
integer combinations,

29
00:01:40,100 --> 00:01:42,333
we have... 

30
00:01:42,333 --> 00:01:47,833
d divides...let's take a good linear
combination of a and b,

31
00:01:47,833 --> 00:01:50,966
and the ones that we should do 
is the x and y linear combination

32
00:01:50,966 --> 00:01:53,833
a x plus b y and
that's equal to e.

33
00:01:53,833 --> 00:01:57,833
Since e was equal to 
the gcd of a and b,

34
00:01:57,833 --> 00:02:00,833
we're actually done.

35
00:02:00,833 --> 00:02:04,833
Thus... let's see 
this in action…

36
00:02:04,833 --> 00:02:09,566
so, d divides a x plus b y and a x plus 
b y is e which is the gcd of a and b.

37
00:02:09,566 --> 00:02:14,533
So thus, d divides

38
00:02:14,533 --> 00:02:17,633
the gcd of 
a and b.

39
00:02:17,633 --> 00:02:20,833
And that's it.

40
00:02:20,833 --> 00:02:24,833
A quick little
theorem here.

41
00:02:24,833 --> 00:02:26,666
So here we didn't have to
use too too much but,

42
00:02:26,666 --> 00:02:29,400
we did use a combination of some 
of the hammers that we have:

43
00:02:29,400 --> 00:02:32,366
Bezout's Lemma and
divisibility of integer combinations.

44
00:02:32,366 --> 00:02:34,933
Those two things combined, 
take us home in this problem.

45
00:02:34,933 --> 00:02:37,633
So again, it's tough to know where 
to start in a problem like this.

46
00:02:37,633 --> 00:02:40,733
Again sometimes it helps to 
look at the conclusion,

47
00:02:40,733 --> 00:02:42,533
sometimes it doesn't, it
really just depends.

48
00:02:42,533 --> 00:02:45,433
But here since we want d 
divides the gcd of a and b,

49
00:02:45,433 --> 00:02:48,366
it makes sense to try to do 
something with the gcd of a and b,

50
00:02:48,366 --> 00:02:50,733
and what can we do?
Well, back substitution

51
00:02:50,733 --> 00:02:52,366
or Bezout's Lemma or
whatever you want to call it,

52
00:02:52,366 --> 00:02:56,366
that gives us integers x and y; we 
can get the ball rolling with that.

53
00:02:56,366 --> 00:03:00,033
Hopefully this has 
been enlightening.

54
00:03:00,033 --> 00:03:02,533
Thank you very much
for your time. Good luck.