1
00:00:00,000 --> 00:00:03,633
Hello everyone. In this video, 
we're going to talk about

2
00:00:03,633 --> 00:00:06,400
solving a congruence equation.

3
00:00:06,400 --> 00:00:07,866
Now...

4
00:00:07,866 --> 00:00:09,500


5
00:00:09,500 --> 00:00:11,133
this time I've actually 
written out the solution,

6
00:00:11,133 --> 00:00:14,833
so we'll just talk about the 
solution as a change of pace.

7
00:00:14,833 --> 00:00:17,133
This is actually not

8
00:00:17,133 --> 00:00:18,933
an extremely…

9
00:00:18,933 --> 00:00:23,033
it's actually something that you know, and I 
want to put it like this. It's pretty straightforward,

10
00:00:23,033 --> 00:00:26,500
you're going to do sort of the 
things that you already suspected

11
00:00:26,500 --> 00:00:30,533
from high school sort of
solving linear equations.

12
00:00:30,533 --> 00:00:32,300
It's the same techniques that will apply here.

13
00:00:32,300 --> 00:00:36,533
So solve the congruence equations in Z 11 
given by the following two equations, okay?

14
00:00:36,533 --> 00:00:40,566
So by the way, something to keep 
in mind, this is different from

15
00:00:40,566 --> 00:00:43,766
Chinese Remainder type 
problems, if you've seen these,

16
00:00:43,766 --> 00:00:46,600
because we have two 
variables here. Two variables

17
00:00:46,600 --> 00:00:51,166
and two equations, so two unknowns two 
equations, we should be able to solve this.

18
00:00:51,166 --> 00:00:56,700
It holds true over just integers and 
it's still going to hold true over

19
00:00:56,700 --> 00:00:59,533
the integers modulo m.

20
00:00:59,533 --> 00:01:02,700
So because I prefer to deal with 
congruences, I'm going to immediately

21
00:01:02,700 --> 00:01:07,300
swap this into a congruence…
congruence equations.

22
00:01:07,300 --> 00:01:10,033
So the congruence equations 
are 3x plus 4y equals 5 mod 11,

23
00:01:10,033 --> 00:01:13,333
and 5x plus 2y is congruent to 1 mod 11.

24
00:01:13,333 --> 00:01:14,400


25
00:01:14,400 --> 00:01:17,433
Now when you get to this
point, you can use any

26
00:01:17,433 --> 00:01:21,100
technique you want. Isolating for one 
of the variables is going to be tricky

27
00:01:21,100 --> 00:01:24,733
because then you have to find an inverse 
and it's usually just easier to eliminate.

28
00:01:24,733 --> 00:01:28,233
So here we're going to use 
elimination. We're going to take - 

29
00:01:28,233 --> 00:01:32,433
notice that 4 and 2 - so 2 times 
2 is 4, so we're going to take

30
00:01:32,433 --> 00:01:35,700
double the second equation 
away from the first,

31
00:01:35,700 --> 00:01:38,000
and what is that going to give us? 
So we're going to eliminate the y’s,

32
00:01:38,000 --> 00:01:41,500
so that's going to be 5 minus 2 that's 3,

33
00:01:41,500 --> 00:01:44,233
and 3 minus 2 times 5 which is 10

34
00:01:44,233 --> 00:01:46,866
so 3 minus 10 and that's negative 7.

35
00:01:46,866 --> 00:01:48,066


36
00:01:48,066 --> 00:01:52,866
Now we could make the negative 7 
positive 4 and deal with that, but

37
00:01:52,866 --> 00:01:57,033
I'm just going to leave it as minus 7 and we're 
going to try to find the inverse of minus 7,

38
00:01:57,033 --> 00:02:01,300
right, this is our goal now. Our goal now is to 
isolate for x and we'd like to divide by negative 7,

39
00:02:01,300 --> 00:02:04,000
but that doesn't really make 
sense. We need to take…

40
00:02:04,000 --> 00:02:06,866
we can't just divide, right? We've
already talked about division

41
00:02:06,866 --> 00:02:09,233
in these linear congruences.

42
00:02:09,233 --> 00:02:12,000
But what we can do instead 
of dividing is we can

43
00:02:12,000 --> 00:02:16,000
find the inverse and multiply by the 
inverse, which is basically dividing.

44
00:02:16,000 --> 00:02:16,966


45
00:02:16,966 --> 00:02:18,833
So here we want to find
the inverse of minus 7.

46
00:02:18,833 --> 00:02:21,833
Now there's two ways we can do this, 
well there's lots of ways we can do this.

47
00:02:21,833 --> 00:02:23,700


48
00:02:23,700 --> 00:02:26,200
We could either…we could guess,

49
00:02:26,200 --> 00:02:29,766
we can use the Extended Euclidean
Algorithm, we could also compute - 

50
00:02:29,766 --> 00:02:33,966
because 11 happens to be prime, we 
can compute minus 7 to the power of

51
00:02:33,966 --> 00:02:37,400
9, right, p minus 2, that we saw in class,

52
00:02:37,400 --> 00:02:39,466
and if we compute that,
that's also the inverse.

53
00:02:39,466 --> 00:02:41,866
However, that might not be any easier than

54
00:02:41,866 --> 00:02:43,833
doing the other things that I've suggested.

55
00:02:43,833 --> 00:02:44,500


56
00:02:44,500 --> 00:02:48,433
Since we only have ten numbers to try, let's just 
guess. That sounds like the easiest way to do this.

57
00:02:48,433 --> 00:02:49,600


58
00:02:49,600 --> 00:02:51,566
So when we guess, what do we get? Well

59
00:02:51,566 --> 00:02:54,600
negative 7 times 3, that's minus 21.

60
00:02:54,600 --> 00:02:58,400
So by the way, why did I use 3?
Well okay 1 and 2 didn't work,

61
00:02:58,400 --> 00:03:01,133
So let's try 3. 7 times 3 is minus 21,

62
00:03:01,133 --> 00:03:03,833
and if I add 22, which is 
the same as 0 mod 11,

63
00:03:03,833 --> 00:03:06,533
that's going to give us the 1.

64
00:03:06,533 --> 00:03:08,866
So it turns out that 3 is 
the inverse of minus 7.

65
00:03:08,866 --> 00:03:12,533
So if I multiply both sides 
of this congruence by 3,

66
00:03:12,533 --> 00:03:16,966
the left-hand side becomes just x, and the 
right-hand side becomes 3 times 3 which is 9.

67
00:03:16,966 --> 00:03:18,366


68
00:03:18,366 --> 00:03:21,366
So that gives us our x
value. The solution for x

69
00:03:21,366 --> 00:03:24,433
is x is congruent to 9 mod 11, we plug that in,

70
00:03:24,433 --> 00:03:26,633
and we can get our y value from this.

71
00:03:26,633 --> 00:03:27,566


72
00:03:27,566 --> 00:03:31,466
So let's do that, so we're going to 
have 3 times 9 plus 4y is equal to 5.

73
00:03:31,466 --> 00:03:33,733
Plug it in, reduce,

74
00:03:33,733 --> 00:03:35,133


75
00:03:35,133 --> 00:03:38,133
the 5’s actually cancel and we're 
actually left with 4y is congruent to 0,

76
00:03:38,133 --> 00:03:40,466
that's easy to solve. Whatever 
the inverse - so by the way,

77
00:03:40,466 --> 00:03:42,433
4 is invertible because it's co-prime to 11,

78
00:03:42,433 --> 00:03:46,266
same with minus 7 up 
there. Minus 7 and 11 are…

79
00:03:46,266 --> 00:03:48,800
the gcd between minus 7 and 11 is 1.

80
00:03:48,800 --> 00:03:51,900
Here the gcd between 4 and 11 
is also 1, they’re co-prime, so

81
00:03:51,900 --> 00:03:53,700
4 has an inverse whatever it is,

82
00:03:53,700 --> 00:03:57,533
so multiply both sides by the 
inverse and I get y equals 0. 

83
00:03:57,533 --> 00:04:00,133
You know what? Maybe
I'll even put in that extra step,

84
00:04:00,133 --> 00:04:02,933
just to show what happened here.

85
00:04:02,933 --> 00:04:03,866


86
00:04:03,866 --> 00:04:03,933


87
00:04:03,933 --> 00:04:05,766
So there we go. So what happened here?

88
00:04:05,766 --> 00:04:08,966
Well I multiply both sides by the
inverse, which I know exists,

89
00:04:08,966 --> 00:04:09,733


90
00:04:09,733 --> 00:04:12,833
and that's going to give me y equals 0.

91
00:04:12,833 --> 00:04:15,533


92
00:04:15,533 --> 00:04:19,933
Maybe I should make a note 
here that the inverse exists.

93
00:04:19,933 --> 00:04:23,500


94
00:04:23,500 --> 00:04:27,133
Inverse exists since

95
00:04:27,133 --> 00:04:29,833
gcd of 4 and 11 is equal to 1.

96
00:04:29,833 --> 00:04:34,033


97
00:04:34,033 --> 00:04:36,000
Let's see how that looks.

98
00:04:36,000 --> 00:04:37,800


99
00:04:37,800 --> 00:04:38,666


100
00:04:38,666 --> 00:04:41,700
And hence the solution is given by - 
well remember we started our

101
00:04:41,700 --> 00:04:45,400
question with the square bracket 
notation, the equivalence class notation,

102
00:04:45,400 --> 00:04:49,366
so we should probably finish the question 
with the equivalence class notation. So

103
00:04:49,366 --> 00:04:53,300
x is equal to 9 and y is equal 
to 0 is the set of solutions.

104
00:04:53,300 --> 00:04:54,033


105
00:04:54,033 --> 00:04:55,900
And that's it.

106
00:04:55,900 --> 00:04:57,033


107
00:04:57,033 --> 00:04:59,933
So again sort of a “follow your nose” proof. 
Once you change to congruence land,

108
00:04:59,933 --> 00:05:04,700
you can just treat it like equality and 
deal with it like you normally would.

109
00:05:04,700 --> 00:05:08,100
Everything passes through, you're allowed to 
add and subtract and multiply equalities,

110
00:05:08,100 --> 00:05:09,833
those are all the Properties of Congruences,

111
00:05:09,833 --> 00:05:13,566
and you're allowed to simplify and 
get to sort of a final answer.

112
00:05:13,566 --> 00:05:16,233
Well you're allowed to get to the final answer.

113
00:05:16,233 --> 00:05:18,066
That's all I have to say for this. So

114
00:05:18,066 --> 00:05:20,900
thank you very much for 
tuning in, and hopefully this

115
00:05:20,900 --> 00:05:23,000
gives you a little bit of a boost.