Congruences and Division. So a couple more theorems from this week.
Congruences and Division, you should put this…
you should draw the parallels to Congruences and Division, and
Coprimeness and Divisibility, which we denoted by the acronym CAD,
and there actually is a similarity between them,
which we'll get to in a minute.
The other thing I want to bring to your attention is the word “division”, right?
So up to this point with congruences, we talked about adding, subtracting, and multiplying,
and even exponentiation to some extent,
but haven't spoken at all about division, and you might
ask yourself, “Well why have we not spoken about division?”
And the answer is well division is actually a little bit complicated.
So let a, b, c be integers and let n be a natural number.
If a c is congruent to b c mod n,
and c and n are co-prime, the gcd of c and n is 1,
then a is congruent to b mod n.
So in this setting…so when you have a c is congruent to b c mod n
and c is co-prime to n,
you can divide by c, is what this is saying.
We'll learn later that this means that c is invertible mod n,
which again means the same sort of thing,
but we'll talk about that probably next week.
Again the proof of this is actually not bad, it's a “follow your nose” kind of proof.
You're going to unwind the definition, n divides a c minus b c,
and then because c and n are co-prime and
n divides c times a minus b,
we can use Coprimeness and Divisibility to get the result that we want.
So let's actually see this.
So as I said, n divides c times a minus b.
Since the gcd of c and n is 1,
by Coprimeness and Divisibility, n must divide…
well n and c don't share any prime factors, so n
must divide a minus b, is what's happening there.
That's Coprimeness and Divisibility.
And hence what do we have? Well we have that a is congruent to b mod n, and that's it.
So, great.
And that ends this proof. So
a fun little result. This tells us how we can actually divide mod n.
On to the next one. Congruent if and only if Same Remainder.
So this is one of the ways that I like to think about
mod n computations as well. So we talked about
like how I think of n as being 0 mod n, it's one way
that I think about it, and this is the other way.
So let a and b be integers, and n a natural number,
then a is congruent to b mod n if and only if a and b have
the same remainder after division by n.
So when you read the statement, the proof
doesn't quite write itself. It's not immediately obvious, but
not too, too far-fetched, right, you want to talk about division by n,
so you probably want to use the Division Algorithm somewhere on a and b,
and then it's just a matter of making the symbols work out.
This turns out to be exactly the proof. The Division Algorithm
and a little bit of manipulating. So there is a lot of text here,
but it's actually not too bad. It's what you think, right?
By the Division Algorithm, we’ll write a as n times it's quotient plus the remainder.
We’ll denote the quotient of a as q sub a, and r sub a and similarly for b,
and these values these r a and r b are less than n.
So if we subtract these two things, what do we get?
We get a minus b is equal to
n times q a minus q b,
plus the difference of their remainders.
So this is true for both cases. Now what we're going to do is
we're actually going to break it up into the “if and only if” part. So sometimes
when you're writing an “if and only if” proof, you can write general things that are true,
and then try to prove each direction, which is what I did here.
So first, we're going to assume that a is congruent to b mod n,
that is that n divides a minus b.
So n divides a minus b, and clearly divides this term that
is a product of n and something else,
so therefore by Divisibility of Integer Combinations, n must divide
r sub a minus r sub b, so the difference of the remainders.
That's what it says there
So by a restriction on the remainders, we know that - well...
how big and how small can r a minus r b be. We saw this
a while ago back with uniqueness, this type of argument.
So n divides r a minus r b, but
the two remainders are between 0 and n, not including n.
So if I take their difference, the smallest it can be is minus n plus 1,
and the largest it can be is n minus 1.
What does that mean? Well again, when is this smallest and largest? It's
largest when the remainder with respect to a is biggest, so n minus 1,
and when the remainder with respect to b
is smallest, which is 0.
However - so if you look at this range,
there's only one number that's divisible by n, right?
There's only one multiple of n in this range, and that's 0.
And since n divides the difference of the remainders, we must have that
the difference the remainders must be 0, and hence r a equals r b.
So their remainders are the same.
So if a is congruent to b mod n, then the two remainders must be the same.
If the two remainders are the same, then if we go back to this statement here
what do we have? Well the two remainders are the same, so that goes away,
so then we have a minus b is equal to some multiple of n.
Well that just means that n divides a minus b
and so by definition, a is congruent to b mod n,
and that's it. So again a little bit of a “follow your nose” kind of proof.
Maybe not so obvious the first time you see it, but what once you've seen it once,
hopefully the arguments are not too, too bad. It just
uses sort of the major theorems from this course,
Division Algorithm, Divisibility of Integer Combinations.
These are things that you're probably quite familiar with by now.
And if not, I recommend getting familiar with these two theorems.
They're very, very powerful and they're very -
they're used a lot in mathematics.
Okay, where to now? Let's actually look at a problem.
So again, example 2, let’s…so,
what is the remainder when 77 to the 100 times 999
minus 6 to the 83 is divided by 4?
Pause the video, try this out.
It's not too hard…
well okay maybe I shouldn't say that.
[laughs]
It's not too hard once you know what you're doing.
If you don't know what you're doing, this question looks really difficult.
But once you really think about what congruent means
and things like that, this question actually
is relatively straightforward.
Maybe not obvious, but relatively straightforward.
So hopefully you've attempted it.
Given that this came after Congruent if and only if Same Remainder,
we probably have to use that theorem, CISR.
So given that we have this 77, the 999, and the 6,
which we can all reduce mod 4, right?
So what are these numbers? So
77, so let's think.
80 is a multiple of 4,
76 is a multiple of 4, so 77 should give you remainder 1,
when I divide by 4. 999 is close to 1000,
so it's close to 996, and so if I divide this by
4, my remainder is going to be 3,
and 6 is the same as 2 mod 4, so let's actually
plug in those values.
So that's what the first line is saying, just that same computation.
I actually explicitly wrote it out with a Division Algorithm.
You don't have to do this when you're using it.
You can just write down 6 is congruent to 2 mod 4,
77 is congruent to 1 mod 4, and 999 is congruent to 3 mod 4.
Again, do you have to show this? No you don’t.
I just thought I would do it to explicitly show you by CISR.
But again, you can just write this down. If you just see that
77 is the same as 1 mod 4, just do it. Don't
waste too much time explaining it.
So now combining this with Properties of Congruences, what we have?
Well 77 is the same as 1, 999 is the same as 3,
and minus 6 [to the 83] is same as 2 to the 83.
1 to the 100, that's easy, times 3, that's 3.
2 to the 83, now if you don't see this…
I've actually broken it down in a couple of steps, but
2 to the 83 is divisible by 4, right? Why? Well
2 to the 83 is 2 squared, times 2 to the 81.
2 squared is 4, and 4 is 0 mod 4.
Again I missed a mod 4 here. But that's it.
So again, 4 divides 6 to the 83, that's
not too, too hard to see,
and you're left with just 3.
So once again, by CISR, 3 is the remainder when this big number is divided by 4.
How do we know that? Well we saw that this number is equivalent to 3 mod 4,
and so they must have the same remainder when divided by 4,
and the remainder of 3 when I divide by 4 is 3.
So there we go.