So linear congruences, so this
ties together the Linear Diophantine Equation stuff
in a new language.
That's what we're going to do here with linear congruences.
So our question is to solve a x is congruent to c mod m
where, again, m is a natural number, a and c are integers,
and we want to solve this for an integer x
So note that if we weren't dealing with congruences and we're trying to solve
a x equals c over the integers, well we know
when we have a solution of that, that's true if and only if a divides c.
That's exactly what this means basically.
Now for this one, is it the same condition? Do we
only have a solution if and only if a divides c and it turns out
it's not quite true.
We'll see a couple of examples though. It’s not… It's a little bit…
what's the word? Weaker?
You don't need to be this strong.
So let's see an example: solve 4x is congruent to 5 mod 8.
Again maybe worth thinking about. Pause the video,
try it out. I'm going to show you three solutions to this problem,
and the three solutions sort of outline
what you should do in these situations,
or give you some techniques to solve this type of problem.
Then after we show the techniques, we’ll talk about the Linear Congruence Theorem.
So what's one solution to this? One solution is just
translating this to a Linear Diophantine Equation.
So what do I mean? Well by definition, there exists an integer z
such that 4x minus 5 equals 8z.
Or I can rearrange that and I can write it as 4x minus 8z is equal to 5.
Remember that's just the definition of congruence, okay? So nothing fancy here.
Now I'm going to do a little change of variables.
Instead of calling this minus z, I'm going to let y equal minus z.
Again if you think about it, right, then…
well if minus z is an integer than so is y, right?
That's really all I'm saying here. So if I rewrite it,
I can rewrite it like this: 4x plus 8y is equal to 5.
Now if I solve this as a Linear Diophantine Equation,
then I've solved my original equation. Right?
So I find the solution to this Linear Diophantine Equation,
thenI have solutions to my original equation.
And that's the idea there.
So solving a more general thing, so this Linear Diophantine Equation
is, strictly speaking, a bigger class of problems, in some sense.
I mean it turns out they're equivalent, maybe I shouldn't over complicate things.
But again, solving this original question
is equivalent to solving the Linear Diophantine Equation 4x plus 8y equals 5,
and if you look at the solutions to this,
how do we find them?
Well we know that the gcd of 4 and 8, that's 4, and 4 doesn't divide 5.
So because 4 doesn't divide 5, we can use Linear Diophantine Equation Theorem 1
to see that this LDE has no solutions.
So hence my original congruence has no solutions.
This has no solutions, then how can I possibly have a solution to 4x minus 5 equals 8z?
So again, this bigger class of problem says that
well okay if I can't solve this, then I certainly can't
have some z that satisfies this equation.
And that's it.
Let's go to the next one. What's another solution of this? Well
another way to solve this - oh I should mention
before I go to this. You don't have to write down all these steps
when going to Linear Diophantine Equation. If you see
“solve 4x is congruent to 5 mod 8” and you just immediately write this is…
it suffices to solve the Linear Diophantine Equation
4x plus 8y equals 5, that's perfectly fine.
I just wanted to show you the derivation once.
So let’s look at this. Now, let's look at this from a different viewpoint, okay,
and what's the viewpoint here? What's the idea here? Well the idea is that
mod 8, there's not too many integers. There's really only 8 integers,
the numbers 0 to 7.
Well what do I mean by that? If I take any arbitrary integer x,
then I can write it as 8q plus r,
for some r between 0 and 7 inclusive,
and q and r are integers.
By CISR, Congruent If and Only If Same Remainders,
4x is congruent to 5 mod 8 holds if and only if
4r is congruent to 5 mod 8, right?
If I plug in x is equal to 8q plus r into here,
then the 8q is going to go away mod 8, because again,
if you're thinking mod 8, 8 is the same as 0, that's one way to look at it,
and so you have 4r is congruent to 5 mod 8,
and you know that r must be between 0 and 7.
So if you just look at all the possible values for r,
or, rewording, if I look at all the possibilities of x between 0 and 7,
if none of those work, then no integer can work, period.
Because otherwise, you just run through the CISR argument
and show that well the remainder has to also satisfy the
linear equation, and that can't work
because none of the numbers between 0 and 7 work.
So you just try them all. You can make a table, you can just list them all
like I've done here, and it turns out you always get 0 or 4 mod 8.
0 and 4 do not equal 5
[shows] that 4x is congruent to 5 mod 8 has no solution.
And that's it. So again, you can run this through whenever you have a small modulus.
8 is relatively small. I mean again, what does relatively small mean?
You be the judge. Just remember that you don’t…
for this course we don't get calculators on our
exams, so you do have to, you know,
balance out how many computations you want to do by hand on an exam.
If you were doing this on an exam, and even if you're not doing it on an exam,
you might want to balance out how many computations is a lot
to try by hand.
Let's look at a third way to solve this, okay?
A third way to solve this is to…
well...
you do something clever. This isn't really
a global technique. You can just kind of
play around with it and notice something cool,
and then you get something - this is the creative side of
the Number Theory portion of this course.
So what do we do here? Well we're going to assume towards a contradiction
that there exists an integer x such that 4x is congruent to 5 mod 8,
and if we multiply both sides by 2, what do we get? Well
2 times 4x that's 8x,
and 2 times 5 is 10, and 8x is the same as 0 mod 8.
So now you get that 0 is congruent to 10 mod 8,
so that means that 8 divides 10,
but of course 8 doesn't divide 10 and that's a contradiction.
So what have we proven? Well there must not be any integer solution
to 4x is congruent to 5 mod 8.
Again, just a nice little neat twist to this problem.
Lots of ways to see this. You could even try to do like a parity argument
would work too. There's lots of ways to come up with a solution.
Be creative that's sort of the moral of this.
Unless a problem tells you to specifically use method, you know, X, Y, Z.
If it doesn't say that, you use whatever you want.
And I do encourage you to be creative.
I think there's lots of cool solutions to this problem…
or to these types of problems. So have fun with it for sure.
Don't just try to be a robot, it's not fun.
Okay so what's the summary of this?
Summary of this is Linear Congruence Theorem 1.
Again, I just showed you one example with three different proofs.
If you want to check out a couple more to maybe
give you a better feeling for this theorem,
I say go ahead.
But LCT1, Linear Congruence Theorem 1.
Let a and c be integers, and m a natural number
and the gcd of a and m to be d.
Then the big statement is: then a x is congruent to c mod m
has a solution if and only if d divides c.
So that's the key. It's not that a needs to divide c it's that the
gcd of a and m needs to divide c.
So it's a little bit different than just plain equals case.
Remember a x equals c has a solution if only if a divides c.
a x is congruent to c mod m has a solution if and only if the gcd of a and m divides c.
So that's where the condition’s a little bit different. A little bit…
I guess it's a little bit more…lax? I don't know
how to word it. Anyways this is the way it is.
So further we have d solutions modulo m, and
1 solution modulo m over d.
So how do we find these solutions? Well if we have a solution x equals x naught,
then x is congruent to x naught mod m over d forms all solutions.
How do ways can we write this? Well I'm going to give you a couple.
Well we can write it as x is equal to x naught plus m over d times n
for all integers n,
or another way to write the solution you can write x is congruent to x naught,
or x naught plus m over d, or x naught plus 2 times m over d,
all the way up to x naught plus d minus 1 times m over d mod m.
The important thing to notice here, I'm not going to prove this.
This is in the notes, I believe page 180ish
in version 0.5,
but really what is this? This is really just a restatement
of Linear Diophantine Equation Theorem 1.
There's nothing crazy going on here. The solution…
the proof of this is really just get it down to a Linear Diophantine Equation,
solve that, and reword it in congruence language.
Again, maybe some things to note: when does it have a solution?
That's one thing to remember from here. How many solutions does it have?
It has the gcd of a and m many solutions
mod m, or one solution mod m over the gcd of a and m.
But that's the key here. The key here is that the gcd of a and m is
really - the gcd of a and m dividing c is what's controlling
the solutions and how many there are.
So it's something to think about. That's the big picture sort of idea for this theorem.