1
00:00:00,000 --> 00:00:03,600
So linear congruences, so this

2
00:00:03,600 --> 00:00:06,633
ties together the Linear 
Diophantine Equation stuff

3
00:00:06,633 --> 00:00:08,566
in a new language.

4
00:00:08,566 --> 00:00:11,333
That's what we're going to 
do here with linear congruences.

5
00:00:11,333 --> 00:00:15,066
So our question is to solve 
a x is congruent to c mod m

6
00:00:15,066 --> 00:00:17,533
where, again, m is a natural 
number, a and c are integers,

7
00:00:17,533 --> 00:00:20,000
and we want to solve 
this for an integer x

8
00:00:20,000 --> 00:00:21,833


9
00:00:21,833 --> 00:00:25,000
So note that if we weren't dealing with 
congruences and we're trying to solve

10
00:00:25,000 --> 00:00:27,533
a x equals c over the 
integers, well we know

11
00:00:27,533 --> 00:00:32,000
when we have a solution of that, 
that's true if and only if a divides c.

12
00:00:32,000 --> 00:00:34,266
That's exactly what
this means basically.

13
00:00:34,266 --> 00:00:36,000


14
00:00:36,000 --> 00:00:37,933
Now for this one, is it the 
same condition? Do we

15
00:00:37,933 --> 00:00:41,266
only have a solution if and only 
if a divides c and it turns out

16
00:00:41,266 --> 00:00:42,866


17
00:00:42,866 --> 00:00:44,266
it's not quite true.

18
00:00:44,266 --> 00:00:45,333


19
00:00:45,333 --> 00:00:49,500
We'll see a couple of examples
though. It’s not… It's a little bit…

20
00:00:49,500 --> 00:00:50,900
what's the word? Weaker?

21
00:00:50,900 --> 00:00:51,666


22
00:00:51,666 --> 00:00:54,366
You don't need to be this strong.

23
00:00:54,366 --> 00:00:57,766
So let's see an example: solve 
4x is congruent to 5 mod 8.

24
00:00:57,766 --> 00:00:59,666


25
00:00:59,666 --> 00:01:01,866
Again maybe worth thinking 
about. Pause the video,

26
00:01:01,866 --> 00:01:04,666
try it out. I'm going to show you 
three solutions to this problem,

27
00:01:04,666 --> 00:01:05,333


28
00:01:05,333 --> 00:01:07,433
and the three solutions
sort of outline

29
00:01:07,433 --> 00:01:09,800
what you should do 
in these situations,

30
00:01:09,800 --> 00:01:14,133
or give you some techniques 
to solve this type of problem.

31
00:01:14,133 --> 00:01:15,500


32
00:01:15,500 --> 00:01:19,633
Then after we show the techniques, we’ll talk
about the Linear Congruence Theorem.

33
00:01:19,633 --> 00:01:20,933


34
00:01:20,933 --> 00:01:23,133
So what's one solution to 
this? One solution is just

35
00:01:23,133 --> 00:01:26,200
translating this to a Linear
Diophantine Equation.

36
00:01:26,200 --> 00:01:29,300
So what do I mean? Well by 
definition, there exists an integer z

37
00:01:29,300 --> 00:01:32,000
such that 4x minus 5 equals 8z.

38
00:01:32,000 --> 00:01:35,833
Or I can rearrange that and I can 
write it as 4x minus 8z is equal to 5.

39
00:01:35,833 --> 00:01:39,533
Remember that's just the definition of
congruence, okay? So nothing fancy here.

40
00:01:39,533 --> 00:01:41,600
Now I'm going to do a 
little change of variables.

41
00:01:41,600 --> 00:01:44,866
Instead of calling this minus z, 
I'm going to let y equal minus z.

42
00:01:44,866 --> 00:01:46,166
 

43
00:01:46,166 --> 00:01:48,366
Again if you think about it, right, then…

44
00:01:48,366 --> 00:01:50,066


45
00:01:50,066 --> 00:01:52,100
well if minus z is an 
integer than so is y, right?

46
00:01:52,100 --> 00:01:55,566
That's really all I'm saying 
here. So if I rewrite it,

47
00:01:55,566 --> 00:01:59,566
I can rewrite it like this: 
4x plus 8y is equal to 5.

48
00:01:59,566 --> 00:02:02,500
Now if I solve this as a 
Linear Diophantine Equation,

49
00:02:02,500 --> 00:02:05,666
then I've solved my 
original equation. Right?

50
00:02:05,666 --> 00:02:07,900
So I find the solution to this 
Linear Diophantine Equation,

51
00:02:07,900 --> 00:02:10,500
thenI have solutions to 
my original equation.

52
00:02:10,500 --> 00:02:12,033


53
00:02:12,033 --> 00:02:13,933
And that's the idea there.

54
00:02:13,933 --> 00:02:16,800
So solving a more general thing, so 
this Linear Diophantine Equation

55
00:02:16,800 --> 00:02:20,566
is, strictly speaking, a bigger class 
of problems, in some sense.

56
00:02:20,566 --> 00:02:24,000
I mean it turns out they're equivalent, 
maybe I shouldn't over complicate things.

57
00:02:24,000 --> 00:02:25,700


58
00:02:25,700 --> 00:02:28,333
But again, solving this original question

59
00:02:28,333 --> 00:02:32,400
is equivalent to solving the Linear 
Diophantine Equation 4x plus 8y equals 5,

60
00:02:32,400 --> 00:02:34,500
and if you look at 
the solutions to this,

61
00:02:34,500 --> 00:02:36,100
how do we find them?

62
00:02:36,100 --> 00:02:39,800
Well we know that the gcd of 4 and 
8, that's 4, and 4 doesn't divide 5.

63
00:02:39,800 --> 00:02:43,666
So because 4 doesn't divide 5, we can use 
Linear Diophantine Equation Theorem 1

64
00:02:43,666 --> 00:02:45,833
to see that this LDE has no solutions.

65
00:02:45,833 --> 00:02:48,033
So hence my original 
congruence has no solutions.

66
00:02:48,033 --> 00:02:52,733
This has no solutions, then how can I possibly
have a solution to 4x minus 5 equals 8z?

67
00:02:52,733 --> 00:02:54,200


68
00:02:54,200 --> 00:02:56,833
So again, this bigger class 
of problem says that

69
00:02:56,833 --> 00:02:59,666
well okay if I can't solve 
this, then I certainly can't

70
00:02:59,666 --> 00:03:03,033
have some z that 
satisfies this equation.

71
00:03:03,033 --> 00:03:04,633
And that's it.

72
00:03:04,633 --> 00:03:05,966


73
00:03:05,966 --> 00:03:08,766
Let's go to the next one. What's 
another solution of this? Well

74
00:03:08,766 --> 00:03:09,966


75
00:03:09,966 --> 00:03:12,000
another way to solve 
this - oh I should mention

76
00:03:12,000 --> 00:03:15,533
before I go to this. You don't have 
to write down all these steps

77
00:03:15,533 --> 00:03:18,066
when going to Linear Diophantine 
Equation. If you see

78
00:03:18,066 --> 00:03:22,833
“solve 4x is congruent to 5 mod 8” and 
you just immediately write this is…

79
00:03:22,833 --> 00:03:25,033
it suffices to solve the Linear
Diophantine Equation

80
00:03:25,033 --> 00:03:27,266
4x plus 8y equals 5,
that's perfectly fine.

81
00:03:27,266 --> 00:03:30,133
I just wanted to show 
you the derivation once.

82
00:03:30,133 --> 00:03:31,333


83
00:03:31,333 --> 00:03:35,100
So let’s look at this. Now, let's look 
at this from a different viewpoint, okay,

84
00:03:35,100 --> 00:03:36,133


85
00:03:36,133 --> 00:03:38,900
and what's the viewpoint here? What's 
the idea here? Well the idea is that

86
00:03:38,900 --> 00:03:42,233
mod 8, there's not too many integers. 
There's really only 8 integers,

87
00:03:42,233 --> 00:03:43,933
the numbers 0 to 7.

88
00:03:43,933 --> 00:03:47,833
Well what do I mean by that? 
If I take any arbitrary integer x,

89
00:03:47,833 --> 00:03:50,166
then I can write
it as 8q plus r,

90
00:03:50,166 --> 00:03:53,233
for some r between
0 and 7 inclusive,

91
00:03:53,233 --> 00:03:55,266
and q and r are integers.

92
00:03:55,266 --> 00:03:58,233
By CISR, Congruent If and 
Only If Same Remainders,

93
00:03:58,233 --> 00:04:01,100
4x is congruent to 5 mod 
8 holds if and only if

94
00:04:01,100 --> 00:04:03,300
4r is congruent
to 5 mod 8, right?

95
00:04:03,300 --> 00:04:07,666
If I plug in x is equal
to 8q plus r into here,

96
00:04:07,666 --> 00:04:10,533
then the 8q is going to go 
away mod 8, because again,

97
00:04:10,533 --> 00:04:14,000
if you're thinking mod 8, 8 is the same 
as 0, that's one way to look at it,

98
00:04:14,000 --> 00:04:16,900
and so you have 4r is 
congruent to 5 mod 8,

99
00:04:16,900 --> 00:04:19,333
and you know that r must 
be between 0 and 7.

100
00:04:19,333 --> 00:04:22,733
So if you just look at all 
the possible values for r,

101
00:04:22,733 --> 00:04:26,700
or, rewording, if I look at all the 
possibilities of x between 0 and 7,

102
00:04:26,700 --> 00:04:29,666
if none of those work, then 
no integer can work, period.

103
00:04:29,666 --> 00:04:33,000
Because otherwise, you just run 
through the CISR argument

104
00:04:33,000 --> 00:04:35,766
and show that well the remainder 
has to also satisfy the

105
00:04:35,766 --> 00:04:37,766
linear equation, and that can't work

106
00:04:37,766 --> 00:04:40,066
because none of the numbers 
between 0 and 7 work.

107
00:04:40,066 --> 00:04:41,066


108
00:04:41,066 --> 00:04:43,933
So you just try them all. You can make 
a table, you can just list them all

109
00:04:43,933 --> 00:04:48,066
like I've done here, and it turns 
out you always get 0 or 4 mod 8.

110
00:04:48,066 --> 00:04:50,033
0 and 4 do not equal 5

111
00:04:50,033 --> 00:04:53,766
[shows] that 4x is congruent 
to 5 mod 8 has no solution.

112
00:04:53,766 --> 00:04:54,700


113
00:04:54,700 --> 00:04:58,666
And that's it. So again, you can run this 
through whenever you have a small modulus.

114
00:04:58,666 --> 00:05:02,633
8 is relatively small. I mean again, 
what does relatively small mean?

115
00:05:02,633 --> 00:05:05,633
You be the judge. Just
remember that you don’t…

116
00:05:05,633 --> 00:05:07,933
for this course we don't 
get calculators on our

117
00:05:07,933 --> 00:05:10,300
exams, so you do have to, you know,

118
00:05:10,300 --> 00:05:14,133
balance out how many computations 
you want to do by hand on an exam.

119
00:05:14,133 --> 00:05:17,266
If you were doing this on an exam, and 
even if you're not doing it on an exam,

120
00:05:17,266 --> 00:05:20,400
you might want to balance out 
how many computations is a lot

121
00:05:20,400 --> 00:05:21,933
to try by hand.

122
00:05:21,933 --> 00:05:22,833


123
00:05:22,833 --> 00:05:25,066
Let's look at a third way 
to solve this, okay?

124
00:05:25,066 --> 00:05:28,000
A third way to solve this is to…

125
00:05:28,000 --> 00:05:30,233


126
00:05:30,233 --> 00:05:31,733
well...

127
00:05:31,733 --> 00:05:33,266


128
00:05:33,266 --> 00:05:36,366
you do something 
clever. This isn't really 

129
00:05:36,366 --> 00:05:39,733
a global technique. You can just kind of 

130
00:05:39,733 --> 00:05:42,100
play around with it and 
notice something cool,

131
00:05:42,100 --> 00:05:44,900
and then you get something - 
this is the creative side of

132
00:05:44,900 --> 00:05:47,133
the Number Theory portion of this course.

133
00:05:47,133 --> 00:05:49,733
So what do we do here? Well we're 
going to assume towards a contradiction

134
00:05:49,733 --> 00:05:53,133
that there exists an integer x such 
that 4x is congruent to 5 mod 8,

135
00:05:53,133 --> 00:05:56,000
and if we multiply both sides
by 2, what do we get? Well

136
00:05:56,000 --> 00:05:56,766


137
00:05:56,766 --> 00:06:00,366
2 times 4x that's 8x,

138
00:06:00,366 --> 00:06:04,333
and 2 times 5 is 10, and 8x 
is the same as 0 mod 8.

139
00:06:04,333 --> 00:06:06,933
So now you get that 0 is
congruent to 10 mod 8,

140
00:06:06,933 --> 00:06:08,600
so that means that 8 divides 10,

141
00:06:08,600 --> 00:06:11,466
but of course 8 doesn't divide 
10 and that's a contradiction.

142
00:06:11,466 --> 00:06:14,166
So what have we proven? Well there 
must not be any integer solution

143
00:06:14,166 --> 00:06:16,233
to 4x is congruent to 5 mod 8.

144
00:06:16,233 --> 00:06:20,000
Again, just a nice little
neat twist to this problem.

145
00:06:20,000 --> 00:06:22,333


146
00:06:22,333 --> 00:06:25,866
Lots of ways to see this. You could 
even try to do like a parity argument

147
00:06:25,866 --> 00:06:29,466
would work too. There's lots of 
ways to come up with a solution.

148
00:06:29,466 --> 00:06:32,000
Be creative that's sort 
of the moral of this.

149
00:06:32,000 --> 00:06:36,766
Unless a problem tells you to specifically 
use method, you know, X, Y, Z.

150
00:06:36,766 --> 00:06:39,266
If it doesn't say that, you 
use whatever you want.

151
00:06:39,266 --> 00:06:41,033
And I do encourage 
you to be creative.

152
00:06:41,033 --> 00:06:43,500
I think there's lots of cool 
solutions to this problem…

153
00:06:43,500 --> 00:06:46,666
or to these types of problems. 
So have fun with it for sure.

154
00:06:46,666 --> 00:06:49,700
Don't just try to be a robot, it's not fun.

155
00:06:49,700 --> 00:06:50,600


156
00:06:50,600 --> 00:06:52,500
Okay so what's the summary of this?

157
00:06:52,500 --> 00:06:54,933
Summary of this is Linear 
Congruence Theorem 1.

158
00:06:54,933 --> 00:06:55,800


159
00:06:55,800 --> 00:06:58,300
Again, I just showed you one
example with three different proofs.

160
00:06:58,300 --> 00:07:00,400
If you want to check out 
a couple more to maybe

161
00:07:00,400 --> 00:07:02,333
give you a better feeling for this theorem,

162
00:07:02,333 --> 00:07:04,666
I say go ahead.

163
00:07:04,666 --> 00:07:07,500
But LCT1, Linear 
Congruence Theorem 1.

164
00:07:07,500 --> 00:07:09,933
Let a and c be integers, 
and m a natural number

165
00:07:09,933 --> 00:07:12,000
and the gcd of a and m to be d.

166
00:07:12,000 --> 00:07:13,100


167
00:07:13,100 --> 00:07:16,300
Then the big statement is: then 
a x is congruent to c mod m

168
00:07:16,300 --> 00:07:20,000
has a solution if and 
only if d divides c.

169
00:07:20,000 --> 00:07:21,766


170
00:07:21,766 --> 00:07:24,833
So that's the key. It's not that a 
needs to divide c it's that the

171
00:07:24,833 --> 00:07:27,666
gcd of a and m 
needs to divide c.

172
00:07:27,666 --> 00:07:31,233
So it's a little bit different
than just plain equals case.

173
00:07:31,233 --> 00:07:34,900
Remember a x equals c has a 
solution if only if a divides c.

174
00:07:34,900 --> 00:07:40,800
a x is congruent to c mod m has a solution 
if and only if the gcd of a and m divides c.

175
00:07:40,800 --> 00:07:44,000
So that's where the condition’s 
a little bit different. A little bit…

176
00:07:44,000 --> 00:07:45,933


177
00:07:45,933 --> 00:07:48,966
I guess it's a little bit
more…lax? I don't know

178
00:07:48,966 --> 00:07:52,000
how to word it. Anyways 
this is the way it is.

179
00:07:52,000 --> 00:07:53,400


180
00:07:53,400 --> 00:07:56,400
So further we have d
solutions modulo m, and

181
00:07:56,400 --> 00:07:58,533
1 solution modulo m over d.

182
00:07:58,533 --> 00:08:03,266
So how do we find these solutions? Well 
if we have a solution x equals x naught,

183
00:08:03,266 --> 00:08:07,466
then x is congruent to x naught 
mod m over d forms all solutions.

184
00:08:07,466 --> 00:08:08,166


185
00:08:08,166 --> 00:08:10,566
How do ways can we write this? 
Well I'm going to give you a couple.

186
00:08:10,566 --> 00:08:14,100
Well we can write it as x is equal 
to x naught plus m over d times n

187
00:08:14,100 --> 00:08:16,466
for all integers n,

188
00:08:16,466 --> 00:08:20,166
or another way to write the solution you 
can write x is congruent to x naught,

189
00:08:20,166 --> 00:08:23,866
or x naught plus m over d, or x
naught plus 2 times m over d,

190
00:08:23,866 --> 00:08:28,233
all the way up to x naught plus d 
minus 1 times m over d mod m.

191
00:08:28,233 --> 00:08:29,433


192
00:08:29,433 --> 00:08:31,466
The important thing to notice 
here, I'm not going to prove this.

193
00:08:31,466 --> 00:08:34,800
This is in the notes, 
I believe page 180ish

194
00:08:34,800 --> 00:08:37,033
in version 0.5,

195
00:08:37,033 --> 00:08:37,966


196
00:08:37,966 --> 00:08:40,400
but really what is this? This 
is really just a restatement

197
00:08:40,400 --> 00:08:43,000
of Linear Diophantine 
Equation Theorem 1.

198
00:08:43,000 --> 00:08:47,066
There's nothing crazy 
going on here. The solution…

199
00:08:47,066 --> 00:08:51,200
the proof of this is really just get it 
down to a Linear Diophantine Equation,

200
00:08:51,200 --> 00:08:54,933
solve that, and reword it 
in congruence language.

201
00:08:54,933 --> 00:08:57,633


202
00:08:57,633 --> 00:09:00,566
Again, maybe some things to 
note: when does it have a solution?

203
00:09:00,566 --> 00:09:03,600
That's one thing to remember from here. 
How many solutions does it have?

204
00:09:03,600 --> 00:09:06,800
It has the gcd of a 
and m many solutions

205
00:09:06,800 --> 00:09:11,800
mod m, or one solution mod 
m over the gcd of a and m.

206
00:09:11,800 --> 00:09:14,400
But that's the key here. The key
here is that the gcd of a and m is

207
00:09:14,400 --> 00:09:18,700
really - the gcd of a and m 
dividing c is what's controlling

208
00:09:18,700 --> 00:09:20,766
the solutions and 
how many there are.

209
00:09:20,766 --> 00:09:21,433


210
00:09:21,433 --> 00:09:24,600
So it's something to think about. That's 
the big picture sort of idea for this theorem.

211
00:09:24,600 --> 00:09:24,700