1
00:00:00,000 --> 00:00:02,500
Hello everyone. In this video, we're 
going to continue our exam review.

2
00:00:02,500 --> 00:00:04,900
So we have here question 
4. If a, b, c are integers

3
00:00:04,900 --> 00:00:08,766
with c dividing a b and the gcd 
of a and c is 1, then c divides b.

4
00:00:08,766 --> 00:00:10,966


5
00:00:10,966 --> 00:00:14,666
So with a question like this, 
since the gcd condition is

6
00:00:14,666 --> 00:00:19,000
in the hypotheses, I'm going to try to use Bézout’s
Lemma and kind of get through this, okay?

7
00:00:19,000 --> 00:00:19,700


8
00:00:19,700 --> 00:00:22,433
This is the condition that I'm going to
start with, you could use divisibility

9
00:00:22,433 --> 00:00:25,633
and try to manipulate it, but I feel like

10
00:00:25,633 --> 00:00:29,366
this condition is the easiest to
start with by using Bézout’s Lemma,

11
00:00:29,366 --> 00:00:31,833
or the Extended Euclidean 
Algorithm, whatever you call it.

12
00:00:31,833 --> 00:00:32,600


13
00:00:32,600 --> 00:00:35,266
So because of that, let's go through 
it. So since the gcd of a and c is 1,

14
00:00:35,266 --> 00:00:39,000
we may apply Bézout’s Lemma, or the
Extended Euclidean Algorithm, to see that

15
00:00:39,000 --> 00:00:43,200
there are integers x and y such 
that a x plus c y equals 1.

16
00:00:43,200 --> 00:00:46,700
So let me maybe write it in. See that

17
00:00:46,700 --> 00:00:48,900
there exist

18
00:00:48,900 --> 00:00:50,000


19
00:00:50,000 --> 00:00:52,233
integers x and y 

20
00:00:52,233 --> 00:00:54,133


21
00:00:54,133 --> 00:00:56,300
such that…

22
00:00:56,300 --> 00:00:58,366
let's fix that up.

23
00:00:58,366 --> 00:00:59,766


24
00:00:59,766 --> 00:01:02,333
So a x plus c y equals 1, okay?

25
00:01:02,333 --> 00:01:05,300
Now I want to show that c divides 
b, and I know that c divides a b,

26
00:01:05,300 --> 00:01:06,900
so I got to get a b to appear in here.

27
00:01:06,900 --> 00:01:09,100
So in order to do that, I'm going 
to multiply everything by b.

28
00:01:09,100 --> 00:01:13,200
So multiply through by b gives 
a b x plus c b y equals b.

29
00:01:13,200 --> 00:01:16,000
So now c divides a b, and c divides

30
00:01:16,000 --> 00:01:18,400
c, so it divides c b y,

31
00:01:18,400 --> 00:01:20,966
and so by Divisibility of 
Integer Combinations, well

32
00:01:20,966 --> 00:01:24,433
c divides this, c divides 
this therefore c divides b. 

33
00:01:24,433 --> 00:01:26,366
And that completes the proof.

34
00:01:26,366 --> 00:01:29,033
So that's good, that was not too, too bad.

35
00:01:29,033 --> 00:01:31,400
For part 2, prove for integers a, b, c

36
00:01:31,400 --> 00:01:35,366
such that the gcd of a and b is 1, if

37
00:01:35,366 --> 00:01:39,000
a divides c and b divides 
c, then a b divides c.

38
00:01:39,000 --> 00:01:43,200
So the way - when I look at this, 
intuitively I think of GCDPF because it is

39
00:01:43,200 --> 00:01:45,433
probably the most natural
way to do it, right? So clearly,

40
00:01:45,433 --> 00:01:48,533
a and b must not share any prime factors,

41
00:01:48,533 --> 00:01:51,366
so if a divides c and b divides c, and

42
00:01:51,366 --> 00:01:54,766
a and b don't share any prime factors, 
then the product should divide c.

43
00:01:54,766 --> 00:01:59,166
So intuitively that's what I do, but I know that it's a
nightmare to write down a GCDPF argument correctly.

44
00:01:59,166 --> 00:02:01,033
So I'm going to try to avoid that,

45
00:02:01,033 --> 00:02:03,700
and the way I'm going to do that is I'm
going to try to get a little bit creative.

46
00:02:03,700 --> 00:02:07,266
So again I know that the gcd 
of a and b is 1, so I'm going to

47
00:02:07,266 --> 00:02:11,233
throw it into the EEA, or Bézout’s 
Lemma whatever you want to call it.

48
00:02:11,233 --> 00:02:13,366
So a x plus b y

49
00:02:13,366 --> 00:02:14,300


50
00:02:14,300 --> 00:02:16,100
equals 1. 

51
00:02:16,100 --> 00:02:20,600
So I guess I skipped a step, so that's sort 
of my starting point is taking this. Now

52
00:02:20,600 --> 00:02:21,900


53
00:02:21,900 --> 00:02:26,433
once I have that a x plus b y equals 1, I’m in sort 
of a pickle, right, I don't really know what to do.

54
00:02:26,433 --> 00:02:29,433
So maybe I should read my 
first sentence which I wrote

55
00:02:29,433 --> 00:02:31,633
by definition there exist
integers m and n such that

56
00:02:31,633 --> 00:02:34,300
a m equals c and b n equals c.

57
00:02:34,300 --> 00:02:36,733
So I'm going to unwind 
the definition of divisibility,

58
00:02:36,733 --> 00:02:40,166
and try to use that with the 
combination of a x plus b y equals 1.

59
00:02:40,166 --> 00:02:43,133
So the combination of those two 
facts should get me somewhere.

60
00:02:43,133 --> 00:02:48,000
Now I want a m and b n to appear, so I should 
probably multiply everything by m n, okay?

61
00:02:48,000 --> 00:02:50,366
So I'm going to do that, and I don't know 
where this is going at this point, okay,

62
00:02:50,366 --> 00:02:52,633
so I'm actually taking this at blind faith and

63
00:02:52,633 --> 00:02:54,800
hoping that I'm going to get to an answer.

64
00:02:54,800 --> 00:02:57,400
Turns out that I'm going to, hopefully,

65
00:02:57,400 --> 00:02:58,333


66
00:02:58,333 --> 00:03:01,166
but when I started writing the 
solution of this, I didn't know that.

67
00:03:01,166 --> 00:03:04,700
I just kind of said okay well 
I have these two things and

68
00:03:04,700 --> 00:03:07,166
I know that I'm going to multiply it, and

69
00:03:07,166 --> 00:03:10,733
hopefully something good is going to happen.
That's sort of my thought process at this point.

70
00:03:10,733 --> 00:03:11,700


71
00:03:11,700 --> 00:03:14,566
So when a m is c, I’m going 
to substitute that in, and

72
00:03:14,566 --> 00:03:17,666
b n is c, so I'm going to substitute that in. 

73
00:03:17,666 --> 00:03:23,033
So I know c divides this and c divides the 
second term, so c should divide m n.

74
00:03:23,033 --> 00:03:27,366
So again by definition, 
there exists a k such that

75
00:03:27,366 --> 00:03:29,100
c k is equal to m n.

76
00:03:29,100 --> 00:03:31,900
So maybe I should write
down for some integer k.

77
00:03:31,900 --> 00:03:33,733


78
00:03:33,733 --> 00:03:36,033
So let's do that. Okay. 

79
00:03:36,033 --> 00:03:37,366


80
00:03:37,366 --> 00:03:41,033
Now what do we know? Okay, 
so c k equals m n, okay? So

81
00:03:41,033 --> 00:03:41,966


82
00:03:41,966 --> 00:03:45,166
where do I go? Let's go 
back to a m equals c.

83
00:03:45,166 --> 00:03:47,966
Now I know that I have c k is equal to m n,

84
00:03:47,966 --> 00:03:50,666
so maybe if I multiply this by 
k, I'm going to get somewhere.

85
00:03:50,666 --> 00:03:52,900
So a m equals c, let’s multiply by k,

86
00:03:52,900 --> 00:03:56,300
I get a m k, which is c k, which is m n.

87
00:03:56,300 --> 00:03:57,233


88
00:03:57,233 --> 00:04:00,166
Now I have an m on both sides,

89
00:04:00,166 --> 00:04:04,000
so either m is 0 and in which case…

90
00:04:04,000 --> 00:04:04,533


91
00:04:04,533 --> 00:04:08,000
if m is 0, then c is 0, and life is good.

92
00:04:08,000 --> 00:04:10,000
So maybe I should mention that.

93
00:04:10,000 --> 00:04:10,866


94
00:04:10,866 --> 00:04:11,433


95
00:04:11,433 --> 00:04:16,066
So in the case where a m k is 
equal to m n, well either m is 0,

96
00:04:16,066 --> 00:04:16,833


97
00:04:16,833 --> 00:04:20,933
and if m is 0 then a
times m is c, so c is 0,

98
00:04:20,933 --> 00:04:24,566
and the claim is true because 
every number divides 0, that's okay,

99
00:04:24,566 --> 00:04:28,833
right, 0 times any number is equal 
to 0, so any number divides 0. 

100
00:04:28,833 --> 00:04:33,133
Or the alternative is that a k is equal to
n, which is the more interesting case.

101
00:04:33,133 --> 00:04:35,266
So when a k equals n, well what can I do?

102
00:04:35,266 --> 00:04:39,333
Well let me multiply both sides by 
b, so I get a b k is equal to b n,

103
00:04:39,333 --> 00:04:41,633
and lo and behold, b n is actually equal to c,

104
00:04:41,633 --> 00:04:42,500


105
00:04:42,500 --> 00:04:45,633
and that actually gives me my result. 
Why do I know to multiply by b?

106
00:04:45,633 --> 00:04:47,966
Again because I'm trying 
to show a b divides c,

107
00:04:47,966 --> 00:04:50,800
so if I multiply both sides by 
b, at least I get the a b term 

108
00:04:50,800 --> 00:04:53,866
and I get lucky in that
the other side should equal c

109
00:04:53,866 --> 00:04:57,533
because I need to reintroduce c at some 
point and that's how I'm going to do that.

110
00:04:57,533 --> 00:05:00,933
And hence a b divides c. So again, I think
there's another way to do this question,

111
00:05:00,933 --> 00:05:02,533
but this is the way that I chose to do it.

112
00:05:02,533 --> 00:05:05,633
Again you could use GCDPF 
and if you want to you can, but

113
00:05:05,633 --> 00:05:08,500
the argument takes a little bit 
to write out and flush out

114
00:05:08,500 --> 00:05:10,966
so I'm not going to do it. 
I'm going to be a little bit…

115
00:05:10,966 --> 00:05:13,733
I'm going to use my head and 
try to be a little bit clever and

116
00:05:13,733 --> 00:05:16,600
try to avoid using GCDPF.

117
00:05:16,600 --> 00:05:18,000
Okay, but that's it.

118
00:05:18,000 --> 00:05:19,966
So here's a couple of examples of

119
00:05:19,966 --> 00:05:22,599
gcd problems and hopefully this 
gives you a little bit of a boost.