Hello everyone. Welcome to Week 7 of Carmen's Core Concepts, my name is Carmen Bruni, and in this video series, specifically for Math 135, we talk about what we did in week 7 of this week's content for the first-year algebra course at the University of Waterloo. Let's just get straight to it.
Week 7 had a lot about congruences. This is one of these key concepts in this course, and in general. I mean you'll find congruences are used in a lot of spots. Once you know what it is, you'll start to see it in different areas, not just in mathematic but in other areas of your studies at university, and once you understand it, you'll be able to make connections and it'll help you in the long term.
So this week, we have a couple more named theorems. Again congruence are at the core of all of these. I think the word “congruent” is in each of these theorems. We have a couple of examples, and then we talked, at the end of the week, we talked about linear congruences, and I actually broke this video up into two parts. So there is a second part on the integers modulo $m$. So if you're looking for that concept and don’t see it here, check out the second video.
What I'd like you to do now is actually take out a piece of paper and a pencil and try to write down the definition of congruence. This needs to be something that you know. What does it mean for two integers to be congruent modulo $n$ for some $n \in \mathbb{N}$? This is a definition that you need to have down, just like you do with an equal sign. You don't really think when you write down, you know, $x=2$. You know what that means, you don't have to pause and parse the statement, you just know. In the same sort of way, congruences have to fall into that feeling. They have to just be something that you're very comfortable with manipulating.
So now hopefully you've written down the definition. If not, here it is.
Recall (Definition of Congruence): Let $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$. Then $a$ is congruent to $b$ modulo $n$ if and only if $n \mid (a-b)$ and we write $a \equiv b \pmod n$.This is equivalent to saying there's an integer $k$ such that $a-b=kn$, or $a=b+kn$.
Again this is just unwinding the definition of divisibility, so there's nothing new there.
One way I like to think of of moduli like this, is that I like to think of the $6$ and the $20$ as being $0$, and we'll see more of this, or why that's true, or how that's true in a couple of the following theorems, but in that sense well because - so in that sense thinking of $6$ as being $0$, well I can always add and subtract $0$. So for example, $11$ is the same as $11-6=5$, or it's the same as $11+6=17$, and so on and so forth. So that's what I mean by I like to think of $6$ as being $0$ in these cases, and $20$ as being $0$. I find that it helps me out a lot when doing computations and things like that, so it's something, if it helps you out, go with it, and if not then forget I ever said it.
Congruence is an equivalence relation. So this is the first theorem that we have with congruences, and it's actually a more general thing. An equivalence relation is a relation that satisfies these 3 properties:
Congruence satisfies all these properties
Theorem (CER): $\text{Let}\, n \in \mathbb{N}. \text{Let} $a,b,c \in \mathbb{Z}$. \text{Then}$
Now something to note, or to recall, right, remember we had Transitivity of Divisibility: if $a \mid b$ and $b \mid c$, then $a \mid c$, and this has that same feeling. $a \equiv b$, $b \equiv c$ implies that $a \equiv c$.
Notice that the equal sign, =, is also an equivalence relation, that's where this name comes from. And these are the 3 properties that an equivalence relation must satisfy. These properties emulate equals in the way that you want it to basically is what this is trying to say.
So great, so Congruence is an Equivalence Relation. Again these proofs are actually relatively straightforward, and you should be able to do them without me showing you. I'm actually not going to show you. That's something that you can do, it's not hard and I encourage you to do it.
Next we have Properties of Congruences. Again, same sort of idea with the fact that like these proofs are not too hard, but, again, I won't show them to you here. Again you can check the notes if you'd like to see them.
Theorem (PC): $\text{Let}\,a,a',b,b' \in \mathbb{Z}. \text{If}\,a\equiv a' \pmod m\,\text{and}\,b\equiv b' \pmod m,\,\text{then}$
Again, it's not hard, you can actually prove all of these by using some combination of DIC. So again I recommend you do it, but I'm not going to do it here. It's a good exercise to do.
Corollary: $\text{If}\, a\equiv b \pmod m\,\text{then}\, a^k \equiv b^k \pmod m \,\text{for}\,k \in \mathbb{N}$
This corollary is the one that I actually use the most. Follows immediately from $3$, you just take $a$ and $b$ to be the same, and $a'$ and $b'$ to be the same, and if you really want to be pedantic, you would prove this by using induction on the natural numbers. Not going to do it. So the corollary is the thing that I use the most. I think I like this the most of the Properties of Congruences that we have here.
Okay that's great, and again so what is this saying? This is saying that congruence basically behaves the way you want it to. In the sense of like all these things you could do with equal signs, you can also do them with congruences, and that's sort of the idea here, right, is to make congruences feel as much as equals as we possibly can. Again it's not the same as equals, remember that $a \equiv a' \pmod m$ if and only if $m \mid (a-a')$. That's what it means. But again we have that same feeling. You want to put congruence in that same class of things as you have with your equal sign, okay? You want to be that familiar with it.
$\text{Is}\, 5^9+62^{2000} -14\,\text{divisible by}\,7?$
So again, actually give this a shot. It's not too hard. hopefully you can make some progress on it on your own. But do try it.
Let's talk about this. What does it mean to be divisible by $7$? Well it means that you’re congruent to $0$ $\bmod 7$. So that's what we're going to do. We're going to look at this $\bmod 7$.
When you see these numbers, the exponents look big and scary, but usually there's ways to simplify the computations, which we'll see in a second. And one of the ways that I like to do this is actually instead of using the $5$ and the $62$, sometimes I like to go to the negative number that's equivalent to it. So for example, $5 \equiv -2 \pmod 7$, and $(-2)^9=-512$, that's actually not too hard.
Then from there I can try to figure out the remainder when I try to reduce it $\bmod 7$. That's something you can do and we'll see a couple of other tricks in a minute of how to deal with $(-2)^9$, but that usually is an easier computation because $2 < 5$.
Same with $62$, $62$ is actually really close to a multiple of $7$, namely $63$, so $62 \equiv 6 \pmod 7$, and if you think about it, $6$ is a little bit big to deal with, but if you take one more $7$ away from it, you get $-1$, so $62 \equiv -1 \pmod 7$, so $62^{2000} \equiv (-1)^{2000} \pmod 7$. That's really easy to deal with.
So let's take a look at the computation based on all that.
$$\begin{align*} 5^9+62^{2000}-14&\equiv (-2)^9+(-1)^{2000}-0 \pmod 7\\\\ &\equiv(-2)^9+1 \pmod 7 \end{align*}$$Another way to see this, by the way, of course is just directly using the definition. $62 \equiv -1 \pmod 7$, since $7 \mid 62-(-1)=63$. So that’s one way to see it. And $14 \equiv 0 \pmod 7$ because $7 \mid 14$, so those two things are equal.
$(-2)^9=-2^9$, right, I can pull the negative out because $(-1)^9=-1$. Now $2^9$, again we can just evaluate it and simplify it, or we can do this little trick and write it as $(2^3)^3$. I love to find these little arithmetic tricks when solving these types of problems. I encourage you to do it too. There's lots of room to be creative in Number Theory when writing a proof and I encourage students to actually be creative and to try to find multiple ways to solve a problem. That often shows that you've actually mastered the material if you can solve it in $3$ or $4$ different ways.
So here I have $(2^3)^3$, $2^3=8 \equiv 1 \pmod 7$. Again, why? Because $7 \mid (8-1)=7$, right? So if $8 \equiv 1 \pmod 7$, then $8^3 \equiv 1^3 \pmod 7$. That's the corollary to Properties of Congruences.
$$\begin{align*} 5^9+62^{2000}-14&\equiv (-2)^9+(-1)^{2000}-0 \pmod 7\\\\ &\equiv(-2)^9+1 \pmod 7\\\\ &\equiv-(2^3)^3+1 \pmod 7\\\\ &\equiv-(8)^3+1 \pmod 7\\\\ &\equiv-(1)^3+1 \pmod 7\\\\ &\equiv 0 \pmod 7 \end{align*}$$So notice that I don't have Properties of Congruences written at every step, I just wrote it at the beginning. Usually with computations, we don't write every single time we use Property of Congruences, or equivalence relations and things like that. I mean if you think about it, like with the equal sign, you don't write them all down, so why would you write them down with congruence that I'm trying to convince you to put in that same class as equal signs, right? So something to think about.
So we do the computation, we eventually get $-1+1=0$. So it's congruent to $0 \bmod 7$. And so what does that mean? So I have this number, did a bunch of computation, I show that it's congruent to $0 \bmod 7$. By definition, that means that this number must be divisible by $7$, and that's it.
So here's a way to use congruences to solve a divisibility problem fairly neatly and fairly quickly, and notice that we didn't actually need to compute what this gigantic number was. We just needed to evaluate it $\bmod 7$, which is pretty neat.
So a couple more theorems from this week. Congruences and Division, 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.
Theorem (CD): $\text{Let}\, a, b, c \in \mathbb{Z}\,\text{and let}\, n \in \mathbb{N}. \text{If}\,ac \equiv bc \pmod n\,\text{and}\,\gcd(c,n)=1,\,\text{then}\, a \equiv b \pmod n$
So in other words, when you have $ac \equiv bc \pmod 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 $\bmod 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. So $n \mid (ac-bc)$ so $n \mid c(a-b)$. Since $\gcd(c,n)=1$, by Coprimeness and Divisibility, $n \mid (a-b)$, is what's happening there. That's Coprimeness and Divisibility. And hence what do we have? Well we have that $a \equiv b \pmod n$ $\blacksquare$
And that's it. So, great. And that ends this proof. So a fun little result. This tells us how we can actually divide $\bmod n$.
This is one of the ways that I like to think about $\bmod n$ computations as well. So we talked about like how I think of $n$ as being $0 \bmod n$, it's one way that I think about it, and this is the other way.
Theorem (CISR): $\text{Let}\,a,b \in \mathbb{Z}.\,\text{Then}\, a \equiv b \pmod n\,\text{if and only if}\,a\,\text{and}\,b\, \text{have the same remainder after}\\\\ \text{division by}\,n.$
So when you read the statement, the proof doesn't quite write itself. It's not immediately obvious, but it's 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.
By the Division Algorithm, we’ll write $a=nq_a+r_a$, where $q_a$ is the quotient of $a$ and $r_a$ is the remainder of $a$. Similarly, $b=nq_b+r_b$. For both $a$ and $b$, $0 \leq r_a,r_b < n$.
So if we subtract these two things, what do we get?
$$a-b=n(q_a-q_b)+r_a-r_b$$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 \equiv b \pmod n$, that is $n \mid (a-b)$. So $n \mid (a-b)$, and clearly $n \mid n(q_a-q_b)$ since it's a product of $n$ and something else, so therefore by Divisibility of Integer Combinations,
$$n \mid (a-b)+n(q_a-q_b)=r_a-r_b$$By a restriction on the remainders, we know that well how big and how small $r_a-r_b$ can be. We saw this a while ago back with uniqueness, this type of argument.
So $n \mid r_a-r_b$, but $0 \leq r_a,r_b < n$. So if I take their difference, the smallest it can be is $-n+1$, and the largest it can be is $n-1$. What does that mean? Well again, when is this smallest and largest? It’s largest when $r_a$ is biggest, so $n-1$, and when $r_b$, which is $0$.
However, 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 \mid r_a-r_b$, it must have that $r_a-r_b=0$, and hence $r_a=r_b$. So their remainders are the same. So if $a \equiv b \pmod n$, then the two remainders must be the same.
If the two remainders are the same, then if we go back to this statement $a-b=n(q_a-q_b)+r_a-r_b$, what do we have?
$$a-b=n(q_a-q_b)+r_a-r_b=n(q_a-q_b)$$The two remainders are the same, so that goes away, so then we have $(a-b)$ is equal to some multiple of $n$. Well that just means that $n \mid (a-b)$ and so by definition, $a \equiv b \pmod n$, and that's it. $\blacksquare$
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 used a lot in mathematics.
Let's actually look at a problem.
$\text{What is the remainder when}\,77^{100}(999)-6^{83}\,\text{is divided by}\,4?$
Take a minute, try this out. It's not too hard…well okay maybe I shouldn't say that. 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 $\bmod 4$, right? So what are these numbers?
$$\begin{align*}&6=4(1)+2 &77=19(4)+1\quad\quad &999=249(4)+3 \end{align*}$$So let's actually plug in those values.
$$\begin{align*} 77^{100}(999)-6^{83}&\equiv (1)^{100}(3)-2^{83} \pmod 4 \end{align*}$$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 \equiv 2 \pmod 4$, $77 \equiv 1 \pmod 4$, and $999 \equiv 3 \pmod 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 \bmod 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^{100}$ is the same as $1^{100}$, $999$ is the same as $3$, and $-6^{83}$ is same as $2^{83}$.
$$\begin{align*} 77^{100}(999)-6^{83}&\equiv (1)^{100}(3)-2^{83} \pmod 4\\\\ &\equiv 3-2^2\cdot 2^{81} \pmod 4\\\\ &\equiv 3-4\cdot 2^{81} \pmod 4\\\\ &\equiv 3-0(2^{81}) \pmod 4\\\\ &\equiv 3 \pmod 4 \end{align*}$$The last step, if you don't see this, I've actually broken it down in a couple of steps, but $2^{83}$ is divisible by $4$, right? Why? Well $2^{83}=2^2\cdot 2^{81}$. $2^2=4 \equiv 0 \pmod 4$. But that's it.
So again, $4 \mid 6^{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 \bmod 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.
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.
$\text{Solve}\,ax \equiv c \pmod m\,\text{where}\,a,c \in \mathbb{Z}\, \text{and}\,m \in \mathbb{N}\,\text{for}\,x \in \mathbb{Z}$
So note that if we weren't dealing with congruences and we're trying to solve $ax=c$ over the integers, well we know when we have a solution of that, that's true if and only if $a \mid 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 \mid c$ and it turns out it's not quite true. We'll see a couple of examples though. It's a little bit… what's the word? Weaker? You don't need to be this strong.
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 $z \in \mathbb{Z}$ such that $4x-5=8z$. Or I can rearrange that and I can write it as $4x-8z=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 $-z$, I'm going to let $y=-z$. Again if you think about it well if $-z$ is an integer than so is $y$, right?
So if I rewrite it, I can rewrite it like this:
$$4x+8y=5$$Now if I solve this as a Linear Diophantine Equation, then I've solved my original equation. So I find the solution to this Linear Diophantine Equation, then I 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+8y=5$.
If you look at the solutions to this, how do we find them? Well we know that the $\gcd(4,8)=4$, and $4 \nmid 5$ So because $4 \nmid 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-5=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? I should mention before I go to this, you don't have to write down all these steps when going to a Linear Diophantine Equation. If you see “solve $4x \equiv 5 \pmod 8$” and you just immediately write "it suffices to solve the Linear Diophantine Equation $4x+8y=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 $\bmod 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 $x=8q+r$, for $0 \leq r \leq 7$, and $q,r \in \mathbb{Z}$.
By CISR, Congruent If and Only If Same Remainders, $4x \equiv 5 \pmod 8$ holds if and only if $4r \equiv 5 \pmod 8$. If I plug in $x=8q+r$ into the equation, then the $8q$ is going to go away $\bmod 8$, because again, if you're thinking $\bmod 8$, $8$ is the same as $0$, that's one way to look at it, and so you have $4r \equiv 4 \pmod 8$, and you know that $0\leq r < 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.
$$\begin{align*} 4(0) &\equiv 0 \pmod 8\\\\ 4(1) &\equiv 4 \pmod 8\\\\ 4(2) &\equiv 0 \pmod 8\\\\ 4(3) &\equiv 4 \pmod 8\\\\ 4(4) &\equiv 0 \pmod 8\\\\ 4(5) &\equiv 4 \pmod 8\\\\ 4(6) &\equiv 0 \pmod 8\\\\ 4(7) &\equiv 4 \pmod 8 \end{align*}$$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 \bmod 8$. $0 \neq 5$ and $4 \neq 5$ so then $4x \equiv 5 \pmod 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 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 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 \equiv 5 \pmod 8$, and if we multiply both sides by $2$, what do we get?
$$0\equiv 0x \equiv 8x \equiv 10 \pmod 8$$So that means that $8 \mid 10$, but of course $8 \nmid 10$ and that's a contradiction.
So what have we proven? Well there must not be any integer solution to $4x \equiv 5 \pmod 8$. Again, just a nice little neat twist of 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 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, the Linear Congruence Theorem 1.
Theorem (LCT1): $\text{Let}\,a,c \in \mathbb{Z}\,\text{and}\, m \in \mathbb{N}\,\text{and}\,\gcd(a,m)=d.\,\text{Then}\, ax \equiv b \pmod m\, \text{has a solution if and}\\\\ \text{only if}\, d\mid c.\,\text{Further, we have}\,d\, \text{solutions modulo}\,m\, \text{and}\,1\,\text{solution modulo}\,\frac{m}{d}.\\\\ \text{Moreover, if}\, x=x_0\,\text{is a solution, then}\,x\equiv x_0 \pmod {\frac{m}{d}}\, \text{forms the complete solution set or}\\\\ \text{alternatively}\,x=x_0+\frac{m}{d}n\,\text{for all}\, n \in \mathbb{Z}\, \text{or for another alternative way to write the solution:}$
$$x\equiv x_0,x_0+\frac{m}{d},x_0+2\frac{m}{d},...,x_0+(d-1)\frac{m}{d} \pmod m$$So the key is that it's not that $a \mid c$, it's that $\gcd(a,m) \mid c$. So it's a little bit different than just plain equals case. Remember $ax=c$ as a solution if only if $a \mid c$. $ax\equiv c \pmod m$ has a solution if and only if $\gcd(a,m)\mid c$. So that's where the condition’s a little bit different. I guess it's a little bit more…lax? I don't know how to word it. Anyways this is the way it is.
The important thing to notice here, I'm not going to prove this. This is in the notes, I believe page $180$ish 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 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 $\gcd(a,m)$ many solutions $\bmod m$, or $1$ solution $\bmod {\frac{m}{\gcd(a,m)}}.$
But that's the key here. The key here is that $\gcd(a,m)$ is really 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.
Simplifying congruences is the last thing I want to mention now. This is something that I found myself just doing haphazardly, because to me, it seems very clear but the first time you see it, it might not be so clear. Let's take a look at this:
$\text{If}\, x \equiv 2,5 \pmod 6,\text{then}\, x \equiv 2 \pmod 3\, \text{gives the same solution set.}$
So the integers that satisfy $x \equiv 2,5 \pmod 6$, is the same as the integers that satisfy $x \equiv 2 \pmod 3$. Take a minute, think about this, give this a shot.
Let's actually think about why this might be the case. It turns out it's not too bad, but it's something that you should think about once, and try to reason to yourself why this actually holds.
Let's kind of go through the proof. I mean that's probably the best way to see is just to stumble through the proof here. So let's look at if $x \equiv 2,5 \pmod 6$, then $x=2+6k$ or $x=5+6k$ for some integer $k$. That's one of the ways we can interpret a congruence.
So in either case, let's think about it. So if I bring the $2$ over, then I'm going to get $x-2=6k$ and $3 \mid 6k=(x-2)$. And by similar logic, $3 \mid (x-5)$, whichever one of these cases is true.
So either $x \equiv 2 \pmod 3$, or $x \equiv 5 \equiv 2 \pmod 3$. So that's maybe the easy direction, right? So if you see $2$ and $5 \bmod 6$ and I reduced it $\bmod 3$, well $5$ is the same as $2 \bmod 3$, so $x \equiv 2 \pmod 3$ gives the same solution sets.
Going the other way, it's almost like you're lifting now. So now you have a solution $\bmod 3$, and you want to know what happens $\bmod 6$. And it turns out, you get one of two cases: $x \equiv 2$ or $x \equiv 5$.
One way to see this quickly, right, take $2$ and just keep adding $3$. So $2$, $5$, $5$ is different than $2 \bmod 6$, if I add $3$ again, I get $8$, but $8$ is the same as $2 \bmod 6$. If I add $3$ again I get $11$, well $11$ is the same as $5 \bmod 6$, and you keep going in this like cyclical pattern.
But how does this really work formally? So if $x \equiv 2 \pmod 3$, then $x=2+3k$ for some integer $k$. Now if you look at $6 \div 3=2$, so if you look at the remainder of $k$ when I divide by $2$, we're going to get some information that we want. If the remainder is $0$, then $k=2l$ for some integer $l$, and hence $x=2+6l$, which is the same as $x \equiv 2 \pmod 6$.
If the remainder is $1$, then I'm going to write $k=2l+1$, for some integer $l$, and plug it in I'm going to get $x=2+3(2l+1)$, and what does that give you? Well if I expand this out, it's going to be $x=5+6l$, which means $x \equiv 5 \pmod 6$.
So hopefully, once you've seen this once, you'll be able to go back and forth. If I change the $6$ and the $3$ to other numbers, you should be able to go very quickly. Something to try out, what if I have $x \equiv 6 \pmod 7$, then what are my solutions $\bmod 28$? Maybe that's something you might want to try and test yourself, make sure that you can quickly come up with the answer.
You shouldn't need to do this argument here. I'm only including it once just so that, you know, because this is your first time seeing congruences, this stuff might be coming at you fast and furious, and you might want to take a minute to ground yourself and be like, “Okay, why is this true?” Make sure you know the basics before you start building, remember you don't want to build like a house on a weak foundation, right, that doesn't work. If your foundation’s weak, your house is going to collapse on itself. So make sure that your foundation is strong, that you know these little facts, so that if you do need to prove them in a pinch, you actually can justify them to yourself.
So that's all I really want to say in part 1. Again I do have part 2 separate just because it's a bigger topic. I do a couple more abstract things in the other video that I wanted to isolate from this video. So I left that on the side.
But that's basically it. So thank you very much for listening, hopefully this gave you some insight into congruences and helped summarize the thickness that is becoming Math 135. There's a lot of stuff in the course now, so it's very easy to get overwhelmed. Just, you know, relax, take a couple of minutes. Try to practice memorizing, or maybe not memorizing the right word, but make sure that you know these things. Recall these theorems to yourself. You're on the bus, try to think, “Okay what did we do this week? What theorems are there? What do they mean? When can I use them?” These are things that you should be constantly reminding yourself as you, you know, as you go about your day. Just little, you know, little tests. Test yourself along the day, make sure you know where we are in the course and what we're doing. That'll help you out in the long term and it'll make studying and things and learning this course a lot easier. So that's it. Thank you very much your time.