1
00:00:00,000 --> 00:00:03,466
Hello everyone. Welcome to Week 
8 of Carmen's Core Concepts.

2
00:00:03,466 --> 00:00:05,733
My name is Carmen Bruni. 
In these video series, I go

3
00:00:05,733 --> 00:00:09,366
through the content of the 
current week in Math 135,

4
00:00:09,366 --> 00:00:12,433
and try to give you a brief
overview of what we covered.

5
00:00:12,433 --> 00:00:15,166
Again this isn't a substitute for 
lectures or anything like that,

6
00:00:15,166 --> 00:00:16,733
it's going to be very quick.

7
00:00:16,733 --> 00:00:20,000
The idea is to try to highlight
the main points from the week,

8
00:00:20,000 --> 00:00:23,066
and to help you remember everything.

9
00:00:23,066 --> 00:00:26,066
I mean recalling things is very
important in mathematics. So

10
00:00:26,066 --> 00:00:29,600
hopefully these videos give you a 
good recall of what we did this week.

11
00:00:29,600 --> 00:00:32,700
Let's start with the 
following proposition. So,

12
00:00:32,700 --> 00:00:34,633
we haven't seen this
acronym yet, TFAE:

13
00:00:34,633 --> 00:00:36,400
"the following are equivalent".

14
00:00:36,400 --> 00:00:36,966


15
00:00:36,966 --> 00:00:39,766
So here we have a laundry
list of things that are equivalent,

16
00:00:39,766 --> 00:00:42,666
so a is congruent to b mod 
m, m divides a minus b,

17
00:00:42,666 --> 00:00:45,800
there exists an integer k such 
that a minus b is equal to k m,

18
00:00:45,800 --> 00:00:48,766
there exists an integer k such 
that a equals k m plus b,

19
00:00:48,766 --> 00:00:50,766
a and b have the same 
remainder when divided by m,

20
00:00:50,766 --> 00:00:55,400
(remember that this followed by Congruent 
If and Only If Same Remainder, CISR),

21
00:00:55,400 --> 00:00:59,533
and then we have the equivalence class of a is 
equal to the equivalence class of b in Z mod m.

22
00:00:59,533 --> 00:01:01,700
Again, all of these are equivalent.

23
00:01:01,700 --> 00:01:02,333


24
00:01:02,333 --> 00:01:05,333
One way to prove that 
things are equivalent

25
00:01:05,333 --> 00:01:08,000
is to, let's say we number 
these, and you can prove that

26
00:01:08,000 --> 00:01:12,000
so for example 1 implies 
2, 2 implies 3, 3 implies 4,

27
00:01:12,000 --> 00:01:14,800
4 implies 5, 5 implies 
6, and 6 implies 1.

28
00:01:14,800 --> 00:01:18,033
It's a very common way to do it, just
prove everything is equal in a cycle.

29
00:01:18,033 --> 00:01:20,266
Sometimes if certain ones are harder,

30
00:01:20,266 --> 00:01:24,000
you might use if and only if statements 
so like 1 if and only if 2, and then

31
00:01:24,000 --> 00:01:27,333
you prove that 1 implies 3, and 
3 implies 4, and 4 implies 1,

32
00:01:27,333 --> 00:01:29,466
something like that 
is also possible too.

33
00:01:29,466 --> 00:01:30,933
Most of these are pretty 
straightforward though

34
00:01:30,933 --> 00:01:33,033
so you don't need to do 
anything fancy to prove this.

35
00:01:33,033 --> 00:01:34,633


36
00:01:34,633 --> 00:01:37,300
And let me just give you a quick 
example, so for example solving

37
00:01:37,300 --> 00:01:40,333
the equivalence class of 10
times the equivalence class of x

38
00:01:40,333 --> 00:01:42,833
is equal to the equivalence 
class of 1 in Z mod m,

39
00:01:42,833 --> 00:01:46,466
is the exact same as solving that 
10x is congruent to 1 mod m.

40
00:01:46,466 --> 00:01:49,633
So these two are related. So for 
example if you have difficulties

41
00:01:49,633 --> 00:01:52,733
with this notation, bring it back down 
to 10x is congruent to 1 mod m,

42
00:01:52,733 --> 00:01:55,700
bring it to this notation, and it 
should be a little bit easier.

43
00:01:55,700 --> 00:01:57,666


44
00:01:57,666 --> 00:01:58,933
Okay.

45
00:01:58,933 --> 00:01:59,566


46
00:01:59,566 --> 00:02:02,966
Inverses, so we spent 
a lot of time in the last

47
00:02:02,966 --> 00:02:05,766
two weeks talking 
about rings and fields,

48
00:02:05,766 --> 00:02:07,966
at least the general 
picture. We didn't talk

49
00:02:07,966 --> 00:02:10,900
anything too, too specific
but I wanted to give you a big

50
00:02:10,900 --> 00:02:13,233
overview idea of what 
abstract algebra…

51
00:02:13,233 --> 00:02:16,600
some of the objects in abstract 
algebra: rings and fields.

52
00:02:16,600 --> 00:02:18,366


53
00:02:18,366 --> 00:02:22,700
And so we saw that in a ring, we have 
to have additive inverses of elements, okay

54
00:02:22,700 --> 00:02:23,533


55
00:02:23,533 --> 00:02:26,333
and in the case of Z mod m, the 
additive inverse is very simple.

56
00:02:26,333 --> 00:02:30,500
If you're dealing with the element 5 in Z 
mod m, the additive inverse is minus 5.

57
00:02:30,500 --> 00:02:33,766
Now you might want to shift that, for 
example, to make it positive by adding m.

58
00:02:33,766 --> 00:02:36,400
So you would have the equivalence 
class of m minus 5, which is the same 

59
00:02:36,400 --> 00:02:38,766
as the equivalence 
class of minus 5,

60
00:02:38,766 --> 00:02:41,466
but either way is fine, and again remember 
that the additive inverse satisfies

61
00:02:41,466 --> 00:02:44,566
the property that a plus 
minus a must be 0.

62
00:02:44,566 --> 00:02:46,766
So whatever element this is

63
00:02:46,766 --> 00:02:49,733
when I add it to a gives me 0,
that's the additive inverse.

64
00:02:49,733 --> 00:02:50,433


65
00:02:50,433 --> 00:02:52,766
Now multiplicative inverses we saw,

66
00:02:52,766 --> 00:02:55,300
and we'll deal with this in 
the next couple slides,

67
00:02:55,300 --> 00:02:59,466
we saw that not all Z mod m
have multiplicative inverses,

68
00:02:59,466 --> 00:03:02,866
but when we do have it… so 
what is a multiplicative inverse?

69
00:03:02,866 --> 00:03:06,433
Well if I multiply a by b, I get 
the multiplicative identity, 1,

70
00:03:06,433 --> 00:03:10,200
just like when I added a and minus 
a I got the additive identity, 0.

71
00:03:10,200 --> 00:03:11,600


72
00:03:11,600 --> 00:03:13,766
So if there is an element 
b such that a times b is 1

73
00:03:13,766 --> 00:03:16,166
and I've written down b 
times a here just in case,

74
00:03:16,166 --> 00:03:19,100
in future courses, your 
ring might not be…

75
00:03:19,100 --> 00:03:21,066


76
00:03:21,066 --> 00:03:24,166
commutative. So you would have 
to at least examine both cases

77
00:03:24,166 --> 00:03:27,266
until you show that inverses 
are unique and things like that.

78
00:03:27,266 --> 00:03:29,866
Here these are the 
same thing but anyways,

79
00:03:29,866 --> 00:03:32,933
a times b gives you 1, we call 
b the multiplicative inverse of a

80
00:03:32,933 --> 00:03:36,166
and we write b is equal to a 
inverse, or sometimes we denote

81
00:03:36,166 --> 00:03:38,866
b is congruent to a 
inverse mod m, okay? So

82
00:03:38,866 --> 00:03:42,566
something to think about here. 
a inverse, when you look at this,

83
00:03:42,566 --> 00:03:47,000
I don't - you should try to get away 
from thinking that this is 1 over a.

84
00:03:47,000 --> 00:03:49,500
That’s going to take a little bit 
of time to used to because you've

85
00:03:49,500 --> 00:03:51,466
thought about this as 1 
over a your whole life,

86
00:03:51,466 --> 00:03:53,733
but you should really be 
thinking of this as the

87
00:03:53,733 --> 00:03:57,400
element when I multiply 
it to a, it gives me 1.

88
00:03:57,400 --> 00:03:59,533
Now over the rational
numbers let's say, that's

89
00:03:59,533 --> 00:04:01,200
equivalent to 1 over a.

90
00:04:01,200 --> 00:04:04,266
But in other rings like Z mod m where 
we don't really have a notion of

91
00:04:04,266 --> 00:04:06,833
1 over a, you have to 
be a little bit careful.

92
00:04:06,833 --> 00:04:07,900


93
00:04:07,900 --> 00:04:10,700
So try to get yourself into that habit 
of rewiring your brain and saying,

94
00:04:10,700 --> 00:04:14,866
“Hey okay, a inverse, that's this number 
when I multiply it by a gives me 1.”

95
00:04:14,866 --> 00:04:16,433


96
00:04:16,433 --> 00:04:17,733
Alright.

97
00:04:17,733 --> 00:04:21,100
So again, multiplicative inverses. 
Multiplicative inverses don't always exist;

98
00:04:21,100 --> 00:04:24,733
depends on the b, it depends
on the m, and let's talk about that.

99
00:04:24,733 --> 00:04:27,000


100
00:04:27,000 --> 00:04:30,066
So a proposition, let a be an
integer and m be a natural number.

101
00:04:30,066 --> 00:04:32,600
Then the inverse of a 
exists in Z m if and only if

102
00:04:32,600 --> 00:04:34,700
the gcd of a and m is 1,

103
00:04:34,700 --> 00:04:37,966
and we'll see very quickly this follows 
from our Linear Congruence Theorem

104
00:04:37,966 --> 00:04:38,733


105
00:04:38,733 --> 00:04:40,066
work.

106
00:04:40,066 --> 00:04:43,100
a inverse is unique if it exists

107
00:04:43,100 --> 00:04:45,533
the last part of our 
proposition, okay?

108
00:04:45,533 --> 00:04:49,033
So let's talk about this. So the multiplicative 
inverse of a exists if and only if

109
00:04:49,033 --> 00:04:52,166
a times x equals 1, as
equivalence classes,

110
00:04:52,166 --> 00:04:54,133
is solvable in Z mod m.

111
00:04:54,133 --> 00:04:54,900


112
00:04:54,900 --> 00:04:57,933
But we can use the
following…well we can - 

113
00:04:57,933 --> 00:05:00,166
I guess it's not really from 
“the following are equivalent”,

114
00:05:00,166 --> 00:05:01,533


115
00:05:01,533 --> 00:05:04,166
but when we do? We can translate 
this, I guess using a couple of things,

116
00:05:04,166 --> 00:05:06,566
to the Linear Diophantine Equation that

117
00:05:06,566 --> 00:05:08,466
a x plus m y equals 1 is solvable.

118
00:05:08,466 --> 00:05:12,166
So here a and m are fixed and 
x and y vary over the integers.

119
00:05:12,166 --> 00:05:15,800
So this has the solution if and 
only if a x is equal to 1 is solvable

120
00:05:15,800 --> 00:05:17,033
in Z mod m.

121
00:05:17,033 --> 00:05:18,100


122
00:05:18,100 --> 00:05:21,166
This is from, this is
actually from LCT, not LDE.

123
00:05:21,166 --> 00:05:22,066


124
00:05:22,066 --> 00:05:25,033
So LCT gives us that

125
00:05:25,033 --> 00:05:28,000
this is solvable if and 
only if this is solvable.

126
00:05:28,000 --> 00:05:32,500
Actually LCT1 and LDET2 are really the 
two things that are happening here

127
00:05:32,500 --> 00:05:33,866


128
00:05:33,866 --> 00:05:36,333
And then once we have this Linear
Diophantine Equation, well we know

129
00:05:36,333 --> 00:05:38,933
this has a solution if and only 
if the gcd of a and m is 1,

130
00:05:38,933 --> 00:05:43,933
you can say by LDET1 or 2, or 
GCD Of One, all of these work.

131
00:05:43,933 --> 00:05:45,733
This is going to
complete the proof. 

132
00:05:45,733 --> 00:05:46,633


133
00:05:46,633 --> 00:05:48,833
So what's the idea here? The idea 
here is that the inverse exists

134
00:05:48,833 --> 00:05:51,100
if and only if this linear 
congruence is solvable,

135
00:05:51,100 --> 00:05:53,966
and the linear congruence corresponds 
to a Linear Diophantine Equation,

136
00:05:53,966 --> 00:05:56,700
and that we've done a couple of 
theorems of earlier in the course.

137
00:05:56,700 --> 00:05:58,033


138
00:05:58,033 --> 00:05:59,866
Now to prove that it's
unique, remember that

139
00:05:59,866 --> 00:06:01,533
if we want to prove
that something is unique,

140
00:06:01,533 --> 00:06:05,100
pretend that you have two elements 
that have the same property,

141
00:06:05,100 --> 00:06:07,466
and then show that 
they must be equal.

142
00:06:07,466 --> 00:06:09,800
So in this case, we have

143
00:06:09,800 --> 00:06:12,233
that a inverse exists and we're 
going to suppose there's some

144
00:06:12,233 --> 00:06:15,900
imposter element b that 
satisfies the same criteria.

145
00:06:15,900 --> 00:06:18,766
Then what can we do? Well let's look 
at…what are we going to look at…

146
00:06:18,766 --> 00:06:21,400
we're going to look at a b is equal to 1, 
and we're going to multiply both sides

147
00:06:21,400 --> 00:06:23,600
by this inverse element, a inverse.

148
00:06:23,600 --> 00:06:26,700
And if we do that, what do we notice? 
Well a inverse times 1, that's a inverse,

149
00:06:26,700 --> 00:06:28,633
and a inverse times a well that's 1,

150
00:06:28,633 --> 00:06:31,833
and 1 times anything 
is just the anything.

151
00:06:31,833 --> 00:06:35,000
So here we see that b is 
equal to a inverse in Z mod m.

152
00:06:35,000 --> 00:06:37,800
So the inverse is unique if it exists.

153
00:06:37,800 --> 00:06:38,766


154
00:06:38,766 --> 00:06:40,900
Okay so, key summary 
from this slide:

155
00:06:40,900 --> 00:06:42,900
inverse is unique, so this 
notation makes sense.

156
00:06:42,900 --> 00:06:45,266
I probably should've done
2 before 1, but that's okay.

157
00:06:45,266 --> 00:06:47,900
The other thing that's important 
here is that the inverse exists

158
00:06:47,900 --> 00:06:51,633
if and only if the gcd of my 
number and the modulus is 1.

159
00:06:51,633 --> 00:06:52,266


160
00:06:52,266 --> 00:06:55,700
So something to keep in mind. 
For example, if m were prime,

161
00:06:55,700 --> 00:07:00,366
then all elements not divisible 
by p, would be invertible.

162
00:07:00,366 --> 00:07:04,200
We actually call such things fields. 
So we say that Z mod p is a field.

163
00:07:04,200 --> 00:07:08,000
We'll get to that in a couple of weeks again,
but something to keep in mind for now.

164
00:07:08,000 --> 00:07:10,066


165
00:07:10,066 --> 00:07:13,900
So just rewording, so Linear Congruence 
Theorem 2, so this is just a quick slide.

166
00:07:13,900 --> 00:07:16,033
We already have Linear 
Congruence Theorem 1,

167
00:07:16,033 --> 00:07:18,566
and this is just the statement of 
Linear Congruence Theorem 1,

168
00:07:18,566 --> 00:07:21,266
except in equivalence class notation.

169
00:07:21,266 --> 00:07:24,266
Let a and c be integers 
and m a natural number.

170
00:07:24,266 --> 00:07:27,866
Let the gcd of a and m 
be d, then the equation…

171
00:07:27,866 --> 00:07:29,933
the equivalence class of a
times the equivalence class of x

172
00:07:29,933 --> 00:07:32,866
is equal to the equivalence class 
of c in Z mod m has a solution

173
00:07:32,866 --> 00:07:34,333
if and only if

174
00:07:34,333 --> 00:07:36,700
the gcd of a and m divides c,

175
00:07:36,700 --> 00:07:39,066
and if you have one solution 
then you can find all solutions

176
00:07:39,066 --> 00:07:41,300
by adding multiples of m over d.

177
00:07:41,300 --> 00:07:43,400
How many multiples can we 
add to get unique elements?

178
00:07:43,400 --> 00:07:45,566
Well we can add up 
to d minus 1 of them. 

179
00:07:45,566 --> 00:07:46,233


180
00:07:46,233 --> 00:07:49,100
So we have x naught, x naught plus 
m over d, x naught plus 2m over d

181
00:07:49,100 --> 00:07:53,000
and all the way up to x naught 
plus d minus 1 times m over d.

182
00:07:53,000 --> 00:07:53,100