1
00:00:00,000 --> 00:00:00,600


2
00:00:00,600 --> 00:00:04,000
So some mixed examples. So

3
00:00:04,000 --> 00:00:06,200
we did a bunch of 
examples in class…

4
00:00:06,200 --> 00:00:10,166
well okay I should say that hopefully 
you did a bunch of examples in class.

5
00:00:10,166 --> 00:00:11,700


6
00:00:11,700 --> 00:00:13,933
And here are some, 
and I decided to

7
00:00:13,933 --> 00:00:16,233
mix them up instead of doing 
them right after the theorems.

8
00:00:16,233 --> 00:00:20,466
So “prove that the gcd of 3s plus t 
and s is equal to the gcd of s and t.”

9
00:00:20,466 --> 00:00:22,233
So s and t here 
are integers. Again

10
00:00:22,233 --> 00:00:24,700
if we don't say, you take them 
to be as big as possible.

11
00:00:24,700 --> 00:00:27,100
You take s and t to 
belong to the domain

12
00:00:27,100 --> 00:00:29,100
as big as possible 
where this makes sense.

13
00:00:29,100 --> 00:00:30,533
That you know of course.

14
00:00:30,533 --> 00:00:33,566
Using GCDWR, so I
gave you a little hint here

15
00:00:33,566 --> 00:00:35,566
and said, “Use GCDWR.”

16
00:00:35,566 --> 00:00:36,266


17
00:00:36,266 --> 00:00:38,033
Again if you're 
solving this at home,

18
00:00:38,033 --> 00:00:40,233
or if you're practicing - by the 
way at this point in the video,

19
00:00:40,233 --> 00:00:42,800
you should stop it and 
actually try to do this, okay?

20
00:00:42,800 --> 00:00:46,733
It's a good practice to even redo this
even if you have done this before.

21
00:00:46,733 --> 00:00:47,700


22
00:00:47,700 --> 00:00:49,600
So if you look at
this and, again,

23
00:00:49,600 --> 00:00:51,733
if you don't know 
what GCDWR is,

24
00:00:51,733 --> 00:00:53,466
the first thing you 
should do is look it up.

25
00:00:53,466 --> 00:00:57,033
I've been generous and I'm 
actually going to copy it here,

26
00:00:57,033 --> 00:01:00,100
but that's a good skill to have, 
okay? So if a, b, q, r are integers

27
00:01:00,100 --> 00:01:04,400
and a equals b q plus r, then the gcd of 
a and b is equal to the gcd of b and r.

28
00:01:04,400 --> 00:01:05,700
Well okay,

29
00:01:05,700 --> 00:01:07,666
so I need to somehow

30
00:01:07,666 --> 00:01:10,766
get an a equal to a, b q plus r

31
00:01:10,766 --> 00:01:14,133
and assuming that my b and r are 
going to somehow be s and t,

32
00:01:14,133 --> 00:01:18,000
that means that a should probably be
something from here, well s is my b then

33
00:01:18,000 --> 00:01:20,266
maybe 3s plus t 
should be my a,

34
00:01:20,266 --> 00:01:22,366
and I'm going to try 
to make the q work.

35
00:01:22,366 --> 00:01:23,100


36
00:01:23,100 --> 00:01:26,266
How do we do that? Well plug those in, 
and just figure out what's going to work.

37
00:01:26,266 --> 00:01:28,000


38
00:01:28,000 --> 00:01:33,066
So if 3s plus t is equal to, here I've written 
it as q b instead of b q I apologize,

39
00:01:33,066 --> 00:01:36,433
but 3s plus t is equal 
to 3 times s plus t.

40
00:01:36,433 --> 00:01:38,066
That doesn't look like much,

41
00:01:38,066 --> 00:01:42,133
but that's basically gcd with 
remainders, right? I mean

42
00:01:42,133 --> 00:01:45,500
gcd with remainders states that, “The 
gcd of 3s plus t comma s is equal to

43
00:01:45,500 --> 00:01:48,566
the gcd of s and t by setting 
a equals to 3s plus t,

44
00:01:48,566 --> 00:01:52,466
b equals to s, q equals 
to 3, and r equals to t.

45
00:01:52,466 --> 00:01:54,933
That's exactly a direct
use of this theorem.

46
00:01:54,933 --> 00:01:56,000


47
00:01:56,000 --> 00:01:57,900
So I have 4 integers,

48
00:01:57,900 --> 00:01:59,766
3s plus t, s,

49
00:01:59,766 --> 00:02:01,866
t, and the number 3,

50
00:02:01,866 --> 00:02:05,100
and I've related them in some 
"a equals b q plus r" way.

51
00:02:05,100 --> 00:02:06,766
That was done right here.

52
00:02:06,766 --> 00:02:07,433


53
00:02:07,433 --> 00:02:10,633
Then I get the conclusion for 
free. That's using a theorem.

54
00:02:10,633 --> 00:02:13,166
Just a reminder of 
that fact at this point.

55
00:02:13,166 --> 00:02:14,666


56
00:02:14,666 --> 00:02:17,100
Let's do another one, 
another mixed example.

57
00:02:17,100 --> 00:02:20,000
Oh this time I just show 
you the answer, I apologize.

58
00:02:20,000 --> 00:02:20,800


59
00:02:20,800 --> 00:02:23,600
You should just try to copy the question 
down and try not to look at proof,

60
00:02:23,600 --> 00:02:25,366
so hide it! No okay I'm sorry…

61
00:02:25,366 --> 00:02:26,000


62
00:02:26,000 --> 00:02:28,333
”Prove that if a, b, x, y 
are integers such that

63
00:02:28,333 --> 00:02:30,333
the gcd of a and b is not 0,

64
00:02:30,333 --> 00:02:32,733
and a x plus b y is equal 
to the gcd of a and b,

65
00:02:32,733 --> 00:02:35,000
then the gcd of x 
and y must be 1.

66
00:02:35,000 --> 00:02:38,600
This is something that's important, we'll 
see this actually later in this video as well.

67
00:02:38,600 --> 00:02:39,400


68
00:02:39,400 --> 00:02:40,900
So what's the idea here? So

69
00:02:40,900 --> 00:02:44,133
since the greatest common divisor 
of a and b divides a and b,

70
00:02:44,133 --> 00:02:45,233


71
00:02:45,233 --> 00:02:49,100
we divide by the non-zero number, the greatest 
common divisor of a and b, to see that

72
00:02:49,100 --> 00:02:50,266


73
00:02:50,266 --> 00:02:52,000
we get the following expression.

74
00:02:52,000 --> 00:02:55,766
So here I took the hypothesis, a x plus 
b y is equal to the gcd of a and b,

75
00:02:55,766 --> 00:02:58,733
and simplified it to get
1 on one side, okay?

76
00:02:58,733 --> 00:03:02,033
Why am I doing this? So maybe I 
should have mentioned this before...

77
00:03:02,033 --> 00:03:02,866


78
00:03:02,866 --> 00:03:04,166
before I went through the proof,

79
00:03:04,166 --> 00:03:07,433
but the gcd of x and y equals 
1, that's in the conclusion.

80
00:03:07,433 --> 00:03:11,633
When a greatest common divisor condition 
is in the conclusion, it's usually good to use

81
00:03:11,633 --> 00:03:13,833
the GCD Characterization Theorem.

82
00:03:13,833 --> 00:03:15,166
Why do we do that?

83
00:03:15,166 --> 00:03:16,066


84
00:03:16,066 --> 00:03:19,133
Well the reason why you do it is
because, well, it will usually work,

85
00:03:19,133 --> 00:03:22,200
but perhaps answering the 
question, “why will it work?”

86
00:03:22,200 --> 00:03:26,166
GCDCT has the gcd 
condition in the conclusion.

87
00:03:26,166 --> 00:03:28,833
So if you want to conclude something 
about a greatest common divisor, it's

88
00:03:28,833 --> 00:03:30,966
probably good to use a
theorem that allows you to

89
00:03:30,966 --> 00:03:32,933
conclude something about 
the greatest common divisor.

90
00:03:32,933 --> 00:03:34,166
So that's the idea,

91
00:03:34,166 --> 00:03:37,133
but in order to use 
GCDCT I need 1

92
00:03:37,133 --> 00:03:38,966
isolated on its own.

93
00:03:38,966 --> 00:03:42,466
And the only equation I'm given is a x plus b y is 
equal to the greatest common divisor of a and b.

94
00:03:42,466 --> 00:03:46,566
So how do I get the 1 on its own? Well I 
probably want to divide by the gcd of a and b.

95
00:03:46,566 --> 00:03:49,633
So I'm going a little bit backwards 
and a little bit forward,

96
00:03:49,633 --> 00:03:51,766
but doing that helps you 
to formulate the proof

97
00:03:51,766 --> 00:03:53,366
and then you just have 
to write it up formally.

98
00:03:53,366 --> 00:03:54,966


99
00:03:54,966 --> 00:03:56,866
With all this in place,

100
00:03:56,866 --> 00:03:59,466
Now we just look at what we have 
and now we say, “well okay 1 divides

101
00:03:59,466 --> 00:04:02,133
x, 1 divides y, and 
1 is greater than 0,

102
00:04:02,133 --> 00:04:05,300
so GCDCT implies that the
gcd of x and y equals 1.”

103
00:04:05,300 --> 00:04:06,166


104
00:04:06,166 --> 00:04:09,933
Now if you have the GCD Characterization 
Theorem in front of you, this might be confusing,

105
00:04:09,933 --> 00:04:12,966
because here x is playing the 
role as a in that theorem and

106
00:04:12,966 --> 00:04:15,800
y is playing the role 
of b in that theorem,

107
00:04:15,800 --> 00:04:18,733
and a over the gcd of a and 
b that's going to be like your x

108
00:04:18,733 --> 00:04:21,500
and b over the gcd of a and 
b is going to be like your y

109
00:04:21,500 --> 00:04:23,300
in the GCD Characterization Theorem.

110
00:04:23,300 --> 00:04:25,633
So it can be confusing, just make 
sure that you remember that

111
00:04:25,633 --> 00:04:28,033
okay these a, b, x, y are
different than the a, b, x, y

112
00:04:28,033 --> 00:04:30,133
possibly in the GCD 
Characterization Theorem.

113
00:04:30,133 --> 00:04:32,166
Well when you 
use it. Okay?

114
00:04:32,166 --> 00:04:35,300
Just because things are the same letter, 
doesn't mean that they have the same use.

115
00:04:35,300 --> 00:04:38,466


116
00:04:38,466 --> 00:04:40,233
That's all I should about that.

117
00:04:40,233 --> 00:04:42,100


118
00:04:42,100 --> 00:04:44,000
Good tip, so just a 
reminder of this tip,

119
00:04:44,000 --> 00:04:46,000
it's good enough that I've 
given it its own slide,

120
00:04:46,000 --> 00:04:49,633
“If the greatest common divisor 
condition appears in the hypothesis,

121
00:04:49,633 --> 00:04:52,766
then Bézout’s Lemma or the Extended 
Euclidean Algorithm might be useful.

122
00:04:52,766 --> 00:04:53,400


123
00:04:53,400 --> 00:04:57,100
If the gcd, the greatest common divisor, 
condition appears in the conclusion,

124
00:04:57,100 --> 00:05:00,500
then GCD Characterization
Theorem might be useful.”

125
00:05:00,500 --> 00:05:01,833


126
00:05:01,833 --> 00:05:03,900
Just a good tip, okay?

127
00:05:03,900 --> 00:05:04,400


128
00:05:04,400 --> 00:05:07,433
If it's in the hypothesis, then you can 
use Bézout’s lemma to get somewhere,

129
00:05:07,433 --> 00:05:10,900
and if it's in the conclusion then you might 
want to use GCDCT to get somewhere.

130
00:05:10,900 --> 00:05:13,433
We're going to see a lot 
of examples of using

131
00:05:13,433 --> 00:05:16,333
Bézout’s Lemma a little 
bit later on in this

132
00:05:16,333 --> 00:05:16,800
Bézout’s Lemma a little 
bit later on in this

133
00:05:16,800 --> 00:05:17,966
slideshow.

134
00:05:17,966 --> 00:05:18,966


135
00:05:18,966 --> 00:05:20,566
So again a good 
tip, keep it in mind.

136
00:05:20,566 --> 00:05:20,666