1
00:00:00,000 --> 00:00:02,066
Hello everyone.

2
00:00:02,066 --> 00:00:03,600
In this video, I'd like to talk about

3
00:00:03,600 --> 00:00:06,533
a couple of problems involving 
the greatest common divisor.

4
00:00:06,533 --> 00:00:07,700


5
00:00:07,700 --> 00:00:10,700
So for our first example, I'd 
like to talk about this problem:

6
00:00:10,700 --> 00:00:14,533
show that the gcd of n factorial plus 1

7
00:00:14,533 --> 00:00:17,533
and n plus 1 factorial plus 1 is 1. 

8
00:00:17,533 --> 00:00:18,800


9
00:00:18,800 --> 00:00:21,400
So...

10
00:00:21,400 --> 00:00:24,000
we're showing that these 
two numbers are co-prime.

11
00:00:24,000 --> 00:00:24,400


12
00:00:24,400 --> 00:00:28,000
Now when you see a gcd 
problem, again we've been

13
00:00:28,000 --> 00:00:32,733
instructing our students to go through 
the theorems that they know in their mind

14
00:00:32,733 --> 00:00:33,400


15
00:00:33,400 --> 00:00:35,366
and seeing if any one

16
00:00:35,366 --> 00:00:38,533
applies to this situation.

17
00:00:38,533 --> 00:00:42,300
I'll go one step further here and notice 
here how there's the n factorial over here,

18
00:00:42,300 --> 00:00:47,300
and then n plus 1 factorial, so this is 
n plus 1 times n factorial on the right.

19
00:00:47,300 --> 00:00:47,966


20
00:00:47,966 --> 00:00:52,733
Now when you have the two terms that kind 
of depend on each other in some weird way,

21
00:00:52,733 --> 00:00:55,600
using the greatest common 
divisor theorem called

22
00:00:55,600 --> 00:00:59,000
GCDWR, Greatest Common 
Divisor With Remainder,

23
00:00:59,000 --> 00:01:01,500
that's sort of your best bet,

24
00:01:01,500 --> 00:01:02,200


25
00:01:02,200 --> 00:01:04,066
but it's a type of…yeah.

26
00:01:04,066 --> 00:01:06,866
I mean it's your best bet.
So let's try to do that here.

27
00:01:06,866 --> 00:01:07,900


28
00:01:07,900 --> 00:01:11,266
So using GCDWR, we see that…

29
00:01:11,266 --> 00:01:15,766


30
00:01:15,766 --> 00:01:18,966
So what are we going to 
have? Let's put the big term

31
00:01:18,966 --> 00:01:20,200


32
00:01:20,200 --> 00:01:22,100
on the left.

33
00:01:22,100 --> 00:01:22,600


34
00:01:22,600 --> 00:01:26,166
So let's see what we have 
here. So n plus 1 factorial, well

35
00:01:26,166 --> 00:01:29,900
n factorial plus 1 that goes in there, into

36
00:01:29,900 --> 00:01:30,666


37
00:01:30,666 --> 00:01:34,266
n plus 1 factorial, that 
definitely goes in at least

38
00:01:34,266 --> 00:01:37,166
n times. In fact, if we do n plus 1 here,

39
00:01:37,166 --> 00:01:43,033


40
00:01:43,033 --> 00:01:46,333
what do we have? Well we 
have n plus 1 times n factorial,

41
00:01:46,333 --> 00:01:49,333
that’s n plus 1 factorial, and then 
we get the extra n plus 1 term.

42
00:01:49,333 --> 00:01:52,233
So we have to account for that, 
so we're going to subtract n.

43
00:01:52,233 --> 00:01:56,300


44
00:01:56,300 --> 00:01:58,700
This is a true statement. Now notice here

45
00:01:58,700 --> 00:01:59,466


46
00:01:59,466 --> 00:02:03,566
that this isn't using the Division Algorithm, 
right? This is a negative remainder,

47
00:02:03,566 --> 00:02:05,533
right? So GCDWR,

48
00:02:05,533 --> 00:02:07,933
we think about it in terms of 
the Division Algorithm, but

49
00:02:07,933 --> 00:02:10,033
it can be used outside of that scope.

50
00:02:10,033 --> 00:02:11,033


51
00:02:11,033 --> 00:02:13,100
So with this,

52
00:02:13,100 --> 00:02:17,566
we see that - let's write this properly - 
we see that since this is true, then…

53
00:02:17,566 --> 00:02:19,433


54
00:02:19,433 --> 00:02:21,466
So the gcd

55
00:02:21,466 --> 00:02:22,866


56
00:02:22,866 --> 00:02:26,200
of a and b, which a is the
left-hand side, and b is this

57
00:02:26,200 --> 00:02:28,700
term n factorial plus 1, is 
the same as the gcd of

58
00:02:28,700 --> 00:02:31,400
n factorial plus 1 and n.

59
00:02:31,400 --> 00:02:37,633


60
00:02:37,633 --> 00:02:38,600


61
00:02:38,600 --> 00:02:41,966
Well okay, I'll write it as 
negative n just to be precise.

62
00:02:41,966 --> 00:02:44,566
That's what GCD With
Remainder tells us.

63
00:02:44,566 --> 00:02:47,600


64
00:02:47,600 --> 00:02:50,133
Now let's look at this, right?

65
00:02:50,133 --> 00:02:54,166


66
00:02:54,166 --> 00:02:56,500
Let d be a divisor of n, right?

67
00:02:56,500 --> 00:03:00,900


68
00:03:00,900 --> 00:03:05,066
Then what do we know about - 
so if we take a divisor of n,

69
00:03:05,066 --> 00:03:08,400
then we know that d
must divide n factorial.

70
00:03:08,400 --> 00:03:08,666


71
00:03:08,666 --> 00:03:09,233


72
00:03:09,233 --> 00:03:13,833
So let's actually clarify this, instead of d being 
a divisor n, let d be a divisor of the whole thing.

73
00:03:13,833 --> 00:03:15,200


74
00:03:15,200 --> 00:03:17,733
That’ll make my life a little bit easier.

75
00:03:17,733 --> 00:03:20,466


76
00:03:20,466 --> 00:03:23,133
So let d be a divisor of the whole thing,

77
00:03:23,133 --> 00:03:25,000


78
00:03:25,000 --> 00:03:27,133
then what do we know?

79
00:03:27,133 --> 00:03:28,366


80
00:03:28,366 --> 00:03:30,700
Then d divides n factorial plus 1,

81
00:03:30,700 --> 00:03:33,433
let's be a little more correct now, and…

82
00:03:33,433 --> 00:03:35,433


83
00:03:35,433 --> 00:03:38,066
and d divides negative n

84
00:03:38,066 --> 00:03:39,400


85
00:03:39,400 --> 00:03:41,733
hence d divides n.

86
00:03:41,733 --> 00:03:45,533


87
00:03:45,533 --> 00:03:48,566
This implies that d 
divides n factorial, right,

88
00:03:48,566 --> 00:03:51,600
d divides n, then clearly
d divides n factorial.

89
00:03:51,600 --> 00:03:54,133


90
00:03:54,133 --> 00:03:56,966
Since n is one of the factors of n factorial.

91
00:03:56,966 --> 00:04:00,000


92
00:04:00,000 --> 00:04:03,600
Now what have we showed? So we 
have d is a factor of n factorial plus 1,

93
00:04:03,600 --> 00:04:06,933
d is a factor of n factorial,

94
00:04:06,933 --> 00:04:10,066
or divisor, so thus

95
00:04:10,066 --> 00:04:11,766
by

96
00:04:11,766 --> 00:04:12,400


97
00:04:12,400 --> 00:04:16,000
Divisibility of Integer Combinations,

98
00:04:16,000 --> 00:04:17,500


99
00:04:17,500 --> 00:04:20,233
d divides n factorial plus 1

100
00:04:20,233 --> 00:04:21,200


101
00:04:21,200 --> 00:04:24,100
minus n factorial, and that's equal to 1.

102
00:04:24,100 --> 00:04:27,366


103
00:04:27,366 --> 00:04:29,500
And hence d is equal to 1.

104
00:04:29,500 --> 00:04:32,500


105
00:04:32,500 --> 00:04:35,266
Well d is equal to plus minus 1.

106
00:04:35,266 --> 00:04:39,566


107
00:04:39,566 --> 00:04:43,100
So in fact let me word this a little bit differently. 
Instead of saying d is a divisor of here,

108
00:04:43,100 --> 00:04:46,533
let me fix this up and tidy this 
up, make it look real nice,

109
00:04:46,533 --> 00:04:48,233
and make d equal [to the gcd] and
then I don't have to worry about the

110
00:04:48,233 --> 00:04:50,733
plus minus 1 because d 
is going to be positive.

111
00:04:50,733 --> 00:04:52,800


112
00:04:52,800 --> 00:04:57,200
So there we go. Let d equal the gcd
of n factorial plus 1 and minus n,

113
00:04:57,200 --> 00:05:00,300
then d divides n factorial plus 
1, and d divides minus n,

114
00:05:00,300 --> 00:05:01,900


115
00:05:01,900 --> 00:05:06,100
so this implies that d divides n factorial.

116
00:05:06,100 --> 00:05:06,300


117
00:05:06,300 --> 00:05:09,100
Thus, Divisibility of Integer Combination says -

118
00:05:09,100 --> 00:05:11,133
or gives us…

119
00:05:11,133 --> 00:05:13,200


120
00:05:13,200 --> 00:05:18,566
gives us that d divides n factorial plus 1 
minus n factorial, and that equals 1.

121
00:05:18,566 --> 00:05:19,666


122
00:05:19,666 --> 00:05:23,266
d is a positive divisor of 1 
that must mean that d is 1,

123
00:05:23,266 --> 00:05:25,033


124
00:05:25,033 --> 00:05:26,733
and this completes the proof.

125
00:05:26,733 --> 00:05:31,566
Since we've shown that d is equal to this gcd 
and that gcd was equal to the expression…

126
00:05:31,566 --> 00:05:33,633


127
00:05:33,633 --> 00:05:37,933
and d equals the gcd in question. So 
maybe I'll put the concluding sentence

128
00:05:37,933 --> 00:05:38,800
 

129
00:05:38,800 --> 00:05:39,166


130
00:05:39,166 --> 00:05:41,833
And that's it. Okay?

131
00:05:41,833 --> 00:05:45,000
So one more time through the question.

132
00:05:45,000 --> 00:05:47,833
So my claim was that these two terms

133
00:05:47,833 --> 00:05:50,333
look similar to each other.

134
00:05:50,333 --> 00:05:55,300
They have elements in common so GCDWR 
seems like a natural choice to use, so we use it.

135
00:05:55,300 --> 00:05:57,000


136
00:05:57,000 --> 00:05:59,133
Once we use it, it tells us the gcd of the

137
00:05:59,133 --> 00:06:01,100
leftmost term and this

138
00:06:01,100 --> 00:06:04,500
right-hand term, this is going to 
be my a and my b in the theorem.

139
00:06:04,500 --> 00:06:05,466


140
00:06:05,466 --> 00:06:10,533
So that gcd must be equal to the gcd of n factorial 
plus 1 and negative n, that's my remainder.

141
00:06:10,533 --> 00:06:11,200


142
00:06:11,200 --> 00:06:14,633
So letting d equal this
greatest common divisor term

143
00:06:14,633 --> 00:06:15,633


144
00:06:15,633 --> 00:06:17,733
and d is a factor of both terms,

145
00:06:17,733 --> 00:06:19,566


146
00:06:19,566 --> 00:06:22,466
and hence must be a
factor of n factorial.

147
00:06:22,466 --> 00:06:24,933
Let me put this in brackets,

148
00:06:24,933 --> 00:06:27,433


149
00:06:27,433 --> 00:06:30,866
just that you don't have to deal with the exclamation 
point and the period beside each other.

150
00:06:30,866 --> 00:06:33,633
Thus by Divisibility of 
Integer Combinations…

151
00:06:33,633 --> 00:06:36,100


152
00:06:36,100 --> 00:06:39,200
thus - maybe I'll remove the 
word “by” so that it's a little clearer. 

153
00:06:39,200 --> 00:06:42,266
Thus Divisibility of Integer 
Combinations gives us that d divides

154
00:06:42,266 --> 00:06:46,733
n factorial plus 1 minus 
n factorial, that's just 1.

155
00:06:46,733 --> 00:06:49,933
Hence d equals 1, and thus 
the gcd must be equal to 1.

156
00:06:49,933 --> 00:06:50,800


157
00:06:50,800 --> 00:06:53,300
Okay, so that’s great. Thank 
you very much for your time

158
00:06:53,300 --> 00:06:56,166
and hopefully this helps you
out on your assignments.

159
00:06:56,166 --> 00:06:56,299