1
00:00:00,000 --> 00:00:02,300
Hello everyone. So in this video,

2
00:00:02,300 --> 00:00:06,733
we're going to talk about the Euclidean 
Algorithm and back substitution.

3
00:00:06,733 --> 00:00:10,833
The problem that I have in mind is: "Find 
the gcd of 65 and 40 and find integers

4
00:00:10,833 --> 00:00:16,833
x and y such that 65x plus 40y is 
equal to the gcd of 65 and 40."

5
00:00:16,833 --> 00:00:18,666


6
00:00:18,666 --> 00:00:21,566
Alright, so

7
00:00:21,566 --> 00:00:24,766
how do we do this? Well the idea's, again, use

8
00:00:24,766 --> 00:00:27,866
repeated applications of the Division Algorithm

9
00:00:27,866 --> 00:00:31,266
to get a list of equations,

10
00:00:31,266 --> 00:00:33,300
for lack of a better word,

11
00:00:33,300 --> 00:00:34,633


12
00:00:34,633 --> 00:00:38,833
where each time you're reducing 
the gcd, step by step. Okay?

13
00:00:38,833 --> 00:00:39,700


14
00:00:39,700 --> 00:00:43,666
So I think it's probably just best 
to actually do an example. So...

15
00:00:43,666 --> 00:00:45,200


16
00:00:45,200 --> 00:00:47,633
We first divide 65 by 40.

17
00:00:47,633 --> 00:00:51,266
40 goes into 65 once, 
and the remainder is 25.

18
00:00:51,266 --> 00:00:55,000


19
00:00:55,000 --> 00:00:58,333
In line two, we're going to get...

20
00:00:58,333 --> 00:01:01,666
that - we're going to move the 40 down, so 40

21
00:01:01,666 --> 00:01:02,166


22
00:01:02,166 --> 00:01:06,466
is equal to 25 and 25 goes into 
40 how many times? Once,

23
00:01:06,466 --> 00:01:07,733


24
00:01:07,733 --> 00:01:09,500
plus 15.

25
00:01:09,500 --> 00:01:12,466
Let's do it again now. 25

26
00:01:12,466 --> 00:01:14,233
is equal to 15

27
00:01:14,233 --> 00:01:15,466


28
00:01:15,466 --> 00:01:19,566
plus 10. So again 15 goes into 25 
once - so a lot of these go in once - 

29
00:01:19,566 --> 00:01:21,233


30
00:01:21,233 --> 00:01:25,333
15, 10 once plus 5.

31
00:01:25,333 --> 00:01:27,266


32
00:01:27,266 --> 00:01:29,633
And then 10...

33
00:01:29,633 --> 00:01:30,700


34
00:01:30,700 --> 00:01:33,566
5 goes into 10 twice plus 0.

35
00:01:33,566 --> 00:01:37,366


36
00:01:37,366 --> 00:01:40,133
So here we are so let's look at...

37
00:01:40,133 --> 00:01:43,466


38
00:01:43,466 --> 00:01:46,966
So here are the equations 
65 equals 40 plus 25,

39
00:01:46,966 --> 00:01:50,633
then you divide 25 into 40 that 
goes in once, with a remainder 15,

40
00:01:50,633 --> 00:01:54,500
then you divide 15 into 25 that 
goes in once with remainder 10,

41
00:01:54,500 --> 00:01:58,266
then you divide 10 into 15 that 
goes in once, with remainder 5,

42
00:01:58,266 --> 00:02:00,466
and you do it one more
time with remainder 0.

43
00:02:00,466 --> 00:02:01,633


44
00:02:01,633 --> 00:02:06,700
The Euclidean Algorithm says the 
gcd is the last non-zero remainder,

45
00:02:06,700 --> 00:02:09,366
which is therefore 5, so thus

46
00:02:09,366 --> 00:02:11,666
the

47
00:02:11,666 --> 00:02:15,033
greatest common divisor

48
00:02:15,033 --> 00:02:19,266
of 65 and 40 is 5.

49
00:02:19,266 --> 00:02:21,966


50
00:02:21,966 --> 00:02:24,133
To find

51
00:02:24,133 --> 00:02:27,533
the integers x and y, we use back substitution.

52
00:02:27,533 --> 00:02:29,700
We're going to start with the last

53
00:02:29,700 --> 00:02:30,733


54
00:02:30,733 --> 00:02:32,933
equation here, so...

55
00:02:32,933 --> 00:02:36,000


56
00:02:36,000 --> 00:02:40,033
the last non-zero remainder equation 
so we're going to say 5 is equal to

57
00:02:40,033 --> 00:02:43,666
15 plus 10 times minus 1.

58
00:02:43,666 --> 00:02:44,600


59
00:02:44,600 --> 00:02:46,566
Okay so I'm going to take

60
00:02:46,566 --> 00:02:49,366
the 5, which is the 15 plus 
10 times minus 1, right?

61
00:02:49,366 --> 00:02:53,833
If I bring it over, it's going to be minus 10 and I'm 
just going to put the minus 10 inside with the 1.

62
00:02:53,833 --> 00:02:54,633


63
00:02:54,633 --> 00:02:57,300
And now I'm going to do the 
same thing with the equation 3.

64
00:02:57,300 --> 00:03:00,900
So I'm going to say 10 is equal 
to 25 plus 15 times minus 1,

65
00:03:00,900 --> 00:03:02,900
and I'm going to replace that 10.

66
00:03:02,900 --> 00:03:06,933


67
00:03:06,933 --> 00:03:09,866
15 plus 25

68
00:03:09,866 --> 00:03:10,833


69
00:03:10,833 --> 00:03:13,600
plus 15 minus 1,

70
00:03:13,600 --> 00:03:15,500
minus 1.

71
00:03:15,500 --> 00:03:16,366


72
00:03:16,366 --> 00:03:16,966


73
00:03:16,966 --> 00:03:19,333
If I simplify...

74
00:03:19,333 --> 00:03:19,966


75
00:03:19,966 --> 00:03:22,400
let's display it first... so again,

76
00:03:22,400 --> 00:03:23,433


77
00:03:23,433 --> 00:03:28,166
by number 3, I get 10 is equal 
to 25 plus 15 times minus 1.

78
00:03:28,166 --> 00:03:29,433


79
00:03:29,433 --> 00:03:32,466
It's exactly what I have here. By the way, this 
makes sense. Again you can check it, right?

80
00:03:32,466 --> 00:03:35,600
25 minus 15 is 10, so it's okay.

81
00:03:35,600 --> 00:03:38,466
Bring the negative 1 into everything,

82
00:03:38,466 --> 00:03:42,166
so it's going to give me 25 times minus 1,

83
00:03:42,166 --> 00:03:45,533
plus I have one 15 here, 
negative 1 times negative 1 is 1,

84
00:03:45,533 --> 00:03:48,700
so I get one more 15, so 15 times 2.

85
00:03:48,700 --> 00:03:51,166


86
00:03:51,166 --> 00:03:53,766


87
00:03:53,766 --> 00:03:58,433
Again, sanity check: 15 times 
2 is 30, minus 25 is 5, still good.

88
00:03:58,433 --> 00:04:01,300


89
00:04:01,300 --> 00:04:04,466
Do the same thing now with 
15 from equation 2. So 15 is

90
00:04:04,466 --> 00:04:07,166
40 plus 25 times minus 1.

91
00:04:07,166 --> 00:04:07,800


92
00:04:07,800 --> 00:04:07,866


93
00:04:07,866 --> 00:04:11,766
So now we've replaced 15 by
the 40 plus 25 times minus 1,

94
00:04:11,766 --> 00:04:12,600


95
00:04:12,600 --> 00:04:14,866
and now we're multiplying by 2,

96
00:04:14,866 --> 00:04:15,400


97
00:04:15,400 --> 00:04:19,866
right, because that was the 2 from down there. So 
take him over here, and this 15 changed to 40 plus

98
00:04:19,866 --> 00:04:20,600


99
00:04:20,600 --> 00:04:22,233
25 times minus 1.

100
00:04:22,233 --> 00:04:25,300
Again, sanity check: 40
minus 25 is 15, it's still good.

101
00:04:25,300 --> 00:04:27,866


102
00:04:27,866 --> 00:04:29,400


103
00:04:29,400 --> 00:04:31,166
We expand it out so I'm going to get

104
00:04:31,166 --> 00:04:34,566
40 times 2, that's the bigger 
one, so I'm going to put it first.

105
00:04:34,566 --> 00:04:37,200
You don't have to, it's
just a matter of preference.

106
00:04:37,200 --> 00:04:38,400


107
00:04:38,400 --> 00:04:42,000
Now I have minus 1 times 2, 
so it's negative two 25's

108
00:04:42,000 --> 00:04:44,200
another minus 1 so that's going to give me

109
00:04:44,200 --> 00:04:46,100
minus 3 25's.

110
00:04:46,100 --> 00:04:47,733


111
00:04:47,733 --> 00:04:51,700
Sanity check: 40 times 2 is
80, 25 times minus 3 is 75,

112
00:04:51,700 --> 00:04:53,866
80 minus 75

113
00:04:53,866 --> 00:04:56,000
is 5, still good.

114
00:04:56,000 --> 00:04:57,366


115
00:04:57,366 --> 00:04:59,166
Now let's use the last one.

116
00:04:59,166 --> 00:05:00,100


117
00:05:00,100 --> 00:05:04,200
So 25 is equal to 65 plus 40 times minus 1.

118
00:05:04,200 --> 00:05:04,900


119
00:05:04,900 --> 00:05:08,166
Alright, now I've used all 
those equations, just one last

120
00:05:08,166 --> 00:05:09,333


121
00:05:09,333 --> 00:05:11,766
distributive property.

122
00:05:11,766 --> 00:05:12,533


123
00:05:12,533 --> 00:05:15,633
So minus 3 times minus 1 is 3, 

124
00:05:15,633 --> 00:05:17,966
3 plus 2 so there's 5 there,

125
00:05:17,966 --> 00:05:20,833


126
00:05:20,833 --> 00:05:23,400
and there's minus 3 65's.

127
00:05:23,400 --> 00:05:24,133


128
00:05:24,133 --> 00:05:26,666
Alright, so one last sanity check here:

129
00:05:26,666 --> 00:05:27,600


130
00:05:27,600 --> 00:05:29,600
so, 65 times

131
00:05:29,600 --> 00:05:32,733
minus 3 that should be negative 195,

132
00:05:32,733 --> 00:05:37,466
40 times 5 is 200, 200 minus
195, that's going to be 5. Okay?

133
00:05:37,466 --> 00:05:38,166


134
00:05:38,166 --> 00:05:41,400
So integers that work are 
x equals minus 3, so...

135
00:05:41,400 --> 00:05:46,733


136
00:05:46,733 --> 00:05:49,066
so integers satisfying the original equation

137
00:05:49,066 --> 00:05:49,533


138
00:05:49,533 --> 00:05:53,800
are x equals minus 3 and y equals 5.

139
00:05:53,800 --> 00:05:55,666


140
00:05:55,666 --> 00:06:00,000
You should always write a concluding sentence like 
this, right, make sure you actually answer the question.

141
00:06:00,000 --> 00:06:01,833


142
00:06:01,833 --> 00:06:05,400
Well that's great. So there's a 
solution that gives you the gcd of 5.

143
00:06:05,400 --> 00:06:09,366
This part is called back substitution, and 
the first part is called the Euclidean Algorithm.

144
00:06:09,366 --> 00:06:10,000


145
00:06:10,000 --> 00:06:12,633
Key takeaways from this: 
the Euclidean Algorithm

146
00:06:12,633 --> 00:06:15,533
states that when you repeatedly 
apply the Division Algorithm,

147
00:06:15,533 --> 00:06:18,600
the last non-zero remainder is the gcd,

148
00:06:18,600 --> 00:06:19,633


149
00:06:19,633 --> 00:06:22,033
and the back substitution part says

150
00:06:22,033 --> 00:06:26,366
you can write down the gcd 
as a linear combination

151
00:06:26,366 --> 00:06:29,900
of the two terms you're taking the gcd 
of. This is sometimes called Bézout's 

152
00:06:29,900 --> 00:06:32,066
Lemma or Bézout's Identity

153
00:06:32,066 --> 00:06:34,233


154
00:06:34,233 --> 00:06:36,133
depends on what you read.

155
00:06:36,133 --> 00:06:38,333


156
00:06:38,333 --> 00:06:39,733
So...

157
00:06:39,733 --> 00:06:41,800
that solves that problem,

158
00:06:41,800 --> 00:06:43,533
and...

159
00:06:43,533 --> 00:06:44,766


160
00:06:44,766 --> 00:06:48,200
I think that's all I want to say. I don't think 
I have anything else to say about this.

161
00:06:48,200 --> 00:06:51,566
So hopefully, this example 
gives you an idea of how to

162
00:06:51,566 --> 00:06:55,766
approach this if you saw it on 
an exam or on an assignment,

163
00:06:55,766 --> 00:06:58,733
and I hope this has been enlightening.

164
00:06:58,733 --> 00:07:01,233
Thank you very much for 
your time and good luck.