Hello everyone. Welcome to Week 6 of Carmen's Core Concepts. My name is Carmen Bruni, and this week, or in these video series, we'll be going through the videos for Math 135 week by week. These are meant to be like a review session, a supplement to going to lectures and other good forms of mathematical practice. In the end, nothing can compare to actually doing problems and practicing these concepts by yourself, preferably without your notes. Just pencil and paper and trying to recall what you remember from the week and how everything fits in together. This is the midway point of Math 135, which is fantastic if you made it this far. So without further ado, let’s begin.
So what did we talk about in Week 6? Week 6 we finished up our discussion of gcd type theorems. Then the last two days of this week, we talked about Linear Diophantine Equations and, what you see at the bottom, the most important definition in this course. This is of course a personal opinion, but I still do think that it is really important. So if you don't know what that is, stay tuned to the end.
So the first thing we want to talk about is the Extended Euclidean Algorithm. So the basic idea behind the Extended Euclidean Algorithm is that it gives you a fast way to compute the $gcd(a,b)$ and integers $x$ and $y$ such that $ax+by=gcd(a,b)$. That's the basis of it so, just as a quick example, we can try the following:
$\text{Find}\, x,y \in \mathbb{Z}\,\text{such that}\, 506x+391y=gcd(506,391)$
Pause the video at this point, and try this problem out. You should be able to do this. If you don't know the Extended Euclidean Algorithm you obviously can't do this, but if you do know it, pause the video and give it a try, okay? So let's see how to do this. I'm not going to do this step by step, I'm just going to kind of rip it off like a band-aid.
| $\textbf{x}$ | $\textbf{y}$ | $\textbf{r}$ | $\textbf{q}$ |
|---|---|---|---|
| $1$ | $0$ | $506$ | $0$ |
| $0$ | $1$ | $391$ | $0$ |
So here in our table, we have our headings $x$, $y$, $r$, $q$. $r$ for remainder and $q$ for quotient. We set up our first two rows as follows, we have $1, 0,$ and $506$, notice that $506$ is the bigger of $506$ and $391$, and we have $0, 1,$ and $391$. And here the first two quotients don't matter, you can leave them blank or put a $0$, that's fine.
Now to compute the quotient in every subsequent row, what we do is we take the previous two remainder terms, and divide them, and then take the floor of that.
| $\textbf{x}$ | $\textbf{y}$ | $\textbf{r}$ | $\textbf{q}$ |
|---|---|---|---|
| $1$ | $0$ | $506$ | $0$ |
| $0$ | $1$ | $391$ | $0$ |
| $115$ | $\left \lfloor \frac{506}{391} \right \rfloor =1$ | ||
| $46$ | $\left \lfloor \frac{391}{115} \right \rfloor =3$ | ||
| $23$ | $\left \lfloor \frac{115}{46} \right \rfloor =2$ | ||
| $0$ | $\left \lfloor \frac{46}{23} \right \rfloor =2$ |
We take $506$ and $391$, that gives us $1$. We take $391$ and $115$ that gives us $3$. We take $115$ and $46$, that gives us $2$. We take $46$ and $23$ and that gives us $2$. Remember the floor is the greatest integer less than or equal to the integer you're taking the floor of, so $\left \lfloor 1.5 \right \rfloor =1$, for example. All these are positive numbers, so you don't have to worry about any negative weird cases happening.
And then how do we figure out the $x$ and $y$ columns after this? So in the third row we have the quotient of $1$, and what we do with the quotient of $1$ is we're going to take the previous row, and subtract $q$ copies of the next row.
| $\textbf{x}$ | $\textbf{y}$ | $\textbf{r}$ | $\textbf{q}$ |
|---|---|---|---|
| $1$ | $0$ | $506$ | $0$ |
| $0$ | $1$ | $391$ | $0$ |
| $1$ | $-1$ | $115$ | $\left \lfloor \frac{506}{391} \right \rfloor =1$ |
| $-3$ | $4$ | $46$ | $\left \lfloor \frac{391}{115} \right \rfloor =3$ |
| $7$ | $-9$ | $23$ | $\left \lfloor \frac{115}{46} \right \rfloor =2$ |
| $-17$ | $22$ | $0$ | $\left \lfloor \frac{46}{23} \right \rfloor =2$ |
So in this case, we're going to take the first row and subtract $1$ copy of the second row. So $1-0=1$ and $0-1=-1$, and then we do the next one. The next quotient is $3$, so we're going to take $(0-3)(1)=-3$. $(1-3)(-1)=4$. And then we do it again, right, with $2$. So $(1-2)(-3)=7$. $(-1-2)(4)=-9$.
The last one doesn't matter, I did it but once you have the last non-zero remainder, in this case $23$ we know that the greatest common divisor between the two starting numbers, $506$ and $391$ is $23$. And we've determined our $x$ and $y$ it's $506(7)+391(-9)=23=gcd(506,391)$.
So now you can go through this algorithm and do it and it's not too hard. It's pretty easy. The thing that's maybe a little difficult is actually understanding why this algorithm computes what you want it to do. And if you think back to the Euclidean Algorithm, right, and think back to GCD With Remainders, what happening here is that these first two $r$ values are your $a$ and your $b$, and what you're doing is you're computing the $q$ and $r$ from the Division Algorithm, and then saying, well $gcd(506,391)=gcd(391,115)$.
Now once you've done that, instead of $506$ being your $a$, you make $391$ your $a$, and then instead of $391$ being your $b$, you make $115$ be your $b$, and then again you're going to compute the same remainder.
So as you can kind of hopefully see based on that description, we keep doing this and repeating this and it's going to give us all of the quotients from before and the remainders from before. So clearly the $gcd$ is going to be okay, and by following along with these $x$ and $y$ values, you can actually trace through it and compute the $x$ and $y$ values as you're going along, as opposed to doing back substitution.
If you want to see an example of like really explicitly where these come from, these equations, check out the lecture notes on the Extended Euclidean Algorithm.
So that's all I want to say about this for now. I guess I should also mention, as a theorem it's called Bézout’s Lemma, the fact that these integers exist. The notes call them the Extended Euclidean Algorithm, either way is fine. That’s the first point I have here.
Notice that in the previous example, $a \gt b$, so if you're doing this with $b \gt a$, then what you can do is you can just swap $a$ and $b$, that's not a big concern. You might have to swap the roles of $x$ and $y$ in your table, that's okay.
If $a \lt 0$ or $b \lt 0$, then what you can do is you can just make all the terms positive. So make the $a$ and the $b$ positive and we don't really care because the $gcd(a,b)=gcd(|a|,|b|)$. So in practice, one can often do these things by actually changing the headings in the EEA table and going from there.
So you can find examples again in the lecture notes, so for example if this was $506x-391y$, what I would do is instead of having a $y$ in the header, I would put a negative $y$, and then just run through the algorithm as normal and just remember that in the end, I got a $-y$ value at the end.
| $\textbf{x}$ | $\textbf{-y}$ | $\textbf{r}$ | $\textbf{q}$ |
|---|---|---|---|
| $1$ | $0$ | $506$ | $0$ |
| $0$ | $1$ | $391$ | $0$ |
| $1$ | $-1$ | $115$ | $\left \lfloor \frac{506}{391} \right \rfloor =1$ |
| $-3$ | $4$ | $46$ | $\left \lfloor \frac{391}{115} \right \rfloor =3$ |
| $7$ | $-9$ | $23$ | $\left \lfloor \frac{115}{46} \right \rfloor =2$ |
| $-17$ | $22$ | $0$ | $\left \lfloor \frac{46}{23} \right \rfloor =2$ |
So when I get the $x$ and $y$ integers, I would have $506(7)-391(-(-9))$ since my $y$ value was negative, and of course $506(7)-391(-(-9))=506(7)-391(9)=506(7)+391(-9)$ just as before. And that's what you would do. So again examples of this can be found in the notes. If you’d like some shortcuts for dealing with $+$ and $-$ and dealing with the sizes of these two values flipped.
So this is a reminder slide. So I spoke about this, I believe in the Week 4 video, the Fundamental Theorem of Arithmetic, but I'd like to revisit it at this point.
Fundamental Theorem of Arithmetic: Suppose that $n \gt 1$, then $n$ can be factored uniquely as a product of prime numbers up to reordering up the prime numbers.
UFT as the acronym is, is for Unique Factorization Theorem. Hopefully this will get changed to FTA1. You'll see why the FTA1 is useful, FTA2 is going to come later, but this is the acronym that we're using at this moment. We'll probably change it later.
Okay so suppose that $n \gt 1$ is an integer, then it can be factored uniquely. So every number has some prime factorization, as long as the number’s bigger than $1$. That's the summary of this. This is something you probably already knew before. The proof is pretty tricky, as you notice, it's very complicated, but it's useful. It's very useful. And it's good to do, it's good practice. It's good to do a couple of things that are hard.
Now let's talk about the uses of this, so why do I care about this? Well one thing that we can do is we can now take a number and factor it into its prime factorization. Why is that important? Well we have a couple of theorems now, talking about divisors and greatest common divisors, that come from the prime factorization of a number.
Theorem (DFPF): $\text{Let}\,n=\prod_{i=1}^k p_i^{\alpha_i}\, \text{where each}\,\alpha_i \geq 1\,\text{is an integer. Then}\, d\,\text{is a positive divisor of}\, n\\\\ \text{if and only if a prime factorization of d can be given by}$
$$d=\prod_{i=1}^k p_i^{\delta_i}\,\text{where}\, \delta_i \in \mathbb{Z},0 \leq \delta_i \leq \alpha_i\, \text{for}\, 1 \leq i \leq k$$The k value is just your stop index. So you have k prime factors and they’re raised to certain powers, okay? So for example, $12=2^2(3)$, right? There would be an example of a prime factorization in this form.
Also notice here that the deltas can be $0$. So some prime factors that appear in $n$ might not appear in the divisor of $n$.
So let's just see an example
Example: $\text{Positive divisors of}\,63=3^2\cdot 7\, \text{are given by}$
$$3^0 \cdot 7^0,3^0 \cdot 7^1,3^1 \cdot 7^0,3^1 \cdot 7^1,3^2 \cdot 7^0,3^2 \cdot 7^1$$$\text{or}$
$$1,7,3,21,9,63$$So again what is this saying? So this is saying positive divisors from a number can be given by the prime factorization by taking subsets of the total number of primes that we have. Just like as follows. The proof of this is technical, we didn't do it in class and I believe it's not done in the notes. Maybe it is done in the notes I don't actually know. I didn't do it in my class. It's just technical to make the symbols work out, and this is something that we kind of already believe before this course started, so I don't think the proof is going to add a lot to our understanding. This is Divisors From Prime Factorization.
Now that we know the type of divisors that can come from a prime factorization, what we can do is we can now determine when we have the greatest common divisor from prime factorization. And that's what the next theorem says.
Theorem (GCDPF): $\text{If}$
$$a=\prod_{i=1}^k p_i^{\alpha_i} \quad b=\prod_{i=1}^k p_i^{\beta_i}$$$\text{where}\,0\leq \alpha_i\,\text{and}\,0\leq \beta_i\,\text{are integers and the}\, p_i\,\text{are distinct primes, then}$
$$gcd(a,b)=\prod_{i=1}^k p_i^{m_i}$$$\text{where}\, m_i=min\{\alpha_i,\beta_i\}\,\text{for}\,1\leq i \leq k$
Notice that these two integers, $a$ and $b$, all we require is that they are positive. When we allow for the $0$ exponents, then we can actually get the number $1$ by just taking all $0’s$ as the exponents, okay? So this type of prime factorization gives us a way to write every single number in terms of prime factors.
Notice also that we have two different numbers but we've used the same prime factors. How can we do that? And the way to do that is to actually just allow for $0$ exponents. So for example I'm going to write $14$ and $15$ using the same prime divisors. Well $14=2^2 \cdot 3^0 \cdot 5^0 \cdot 7^1$, and $15=2^0 \cdot 3^1 \cdot 5^1 \cdot 7^0$. So there I’ve used the primes $2$, $3$, $5$, and $7$ to write those two numbers in their prime factorization.
So don't let the notation fool you, don't let the $k’s$ fool you. Some of the primes might not contribute to $a$ and $b$.
Again we knew from the previous theorem what the divisors of $a$ and $b$ are, so the greatest common divisor involves the largest possible exponent in the common divisors, and that value is going to be given by the minimum of the primes appearing in $a$ and $b$.
So let's just see a concrete example. Again this is a lot of abstract notation, but the idea is actually pretty simple.
$$gcd(20000,30000)=gcd(2^5 \cdot 3^0 \cdot 5^4, 2^4 \cdot 3^1 \cdot 5^4)$$So how do I get this prime factorization? Well I know that $10000$ divides both of these numbers, and $10000=2^4 \cdot 5^4$, so it's actually not too hard to factor these. Sometimes factoring is really difficult though. Actually, in general, factoring is very difficult. But here it's easy, when we have these nice forms we can factor no problem.
And now what do we do? Well we're going to use our GCDPF
$$\begin{align*} gcd(20000,30000)&=gcd(2^5 \cdot 3^0 \cdot 5^4, 2^4 \cdot 3^1 \cdot 5^4)\\\\ &=2^{min\{4,5\}} \cdot 3^{min\{0,1\}} \cdot 5^{min\{4,4\}}\\\\ &=2^4 \cdot 5^4\\\\ &=10000 \end{align*}$$And that's it for GCDPF. You do this computation, and this is the result that you're going to get in the end. I think it's a very powerful result, but you have to be careful when using it, which is what the next topic is going to be.
So tips for $gcd$ type problems. So when tackling a gcd type problem, we can try the following tips.
I have these 3 bullets, and I'll mention what the brackets are in a minute. These are a great analogy given to me by JP Pretti, but first I want to talk about the order.
So first thing you should try when you're looking at a $gcd$ problem is trying to use key theorems from the course, especially some of the following: so we have Bézout’s Theorem, or the Extended Euclidean Algorithm, and this is good when you're you're doing either a computation, or when the greatest common divisor condition is in the hypothesis, right? Once you have that, then you can get these integers $x$ and $y$ that do something, and then maybe you can manipulate them to get the results you want.GCDWR, this is good when terms in the greatest common divisor depend on each other. So if you're, let's say for example, looking for $gcd(n,n+1)$, for any integer $n$. Using GCDWR gives you a good way to simplify the problem and tackle it.
Lastly, GCDCT, this is good when the gcd is in the conclusion. So if you remember, the GCD Characterization Theorem tells us if you have a divisor, $d \gt 0$ of two numbers $a$ and $b$, and you can write $d=ax+by$, then you can conclude that $d=gcd(a,b)$. So that's why it's good when you have the $gcd$ in the conclusion because you get some results about the $gcd$.
Don't forget about your other theorems, right, your DBGCD, Divide By GCD, your GCD Of One, your Coprimeness and Divisibility, all these results are very important. We'll see Coprimeness and Divisibility in a moment.
So once you've tried all your your big hammers, your key theorems in this course, one thing to try is you can use the definition of $gcd$, and that'll usually… well that'll can always get you to the answer, but it might be difficult to write up. It's going to be very slow, you're going to need to take your time and be very careful about your argument.
Then the last sort of ditch effort technique is to use prime factorizations, so use GCDPF.
Driving by Highway 7, so this is like taking the backroads to go from Waterloo to Toronto. You're going to make it there, but it's going to take you a long time, and you're going to have to be careful. There's going to be lots of details that you're going to pick up, and you're going to have to be careful with. So that's the analogy of using the definition of the $gcd$. It's going to be slow, you're going to have to be meticulous, but you'll get there.
Flying is using the prime factorizations of numbers. And this seems like a really quick idea, right, you're flying so you should be going ten times as fast as a car, right? But the problem, of course while flying is that, you know, you have to go through the airport security, you have to pack your luggage, things like this. This can be often a very arduous and difficult chore. So here the write-up, what's the analogy here? So the write-up for using a prime factorization proof is actually really, really difficult. You have to quantify everything, you have to state what things are, I'm using primes, I'm using integers, I'm using exponents, that can be positive or $0$, and all of these things matter, right? So it's going to take time, as a summary of this.
So that's the analogy here. So again, using the key theorems should get you there the quickest if you can. Using the definition of $gcd$ gets you there, if the theorems don't seem to work or you don't have any other choices. Sometimes, you know, you'll pick up details along the way, and of course the last way, flying, so using GCPPF seems like a good idea at first, until you try to do it you're like, “Oh my gosh, there's so many details I have to remember and write up to make my proof look correct.” Okay so that's it for the $gcd$ type problems. This is what we're going to end with in $gcd’s$.
We've talked a little bit throughout the rest of the week on Linear Diophantine Equations. What’s the idea here? Well we want to solve equations of the form $ax+by=c$, where $a$, $b$, and $c \in \mathbb{Z}$, but there's a catch, right, and the catch is that we don't just want to solve these for real numbers $$ and $y$, we want to solve these for integers $x$ and $y$.
Now if you think about this, when $x$ and $y$ are real, we've actually already done this. Well by “we” I mean “you”, and also by “we” I mean “you did this in high school”. This is the equation of a line, so solving these for real values is the same as solving for the equation of a line, right? This is the same as:
$$y=\frac{-ax}{b}+\frac{c}{b}$$So you have your slope, your $\frac{-a}{b}$ in this case, and you have your y-intercept value, your $\frac{c}{b}$, and you could find points, right? You have $x’s$, then you can find $y’s$, right, so the solution set over the reals gives you the equation of a line.
Over the integers it gives you a subset of that line and it'll turn out as we'll see from LDET2, that the points on your line are equidistant from each other. They're equally spaced out, and they're spaced out by some factor depending on your slope. It's not exactly the slope $\frac{-a}{b}$, as you will see, what will happen is you'll go a little bit over and a little bit up, or a little bit over and a little bit down, depending on the slope of your line, and you're going to create these new points that will appear. We'll see that in a minute, I'm getting ahead of myself.
So two things we want to know when we're dealing with a Linear Diophantine Equation: one, does it have a solution at all? And two, what are all of the solutions to a Linear Diophantine Equation? These are answered in two theorems: LDET1 and LDET2.
So let's take a look at LDET1:
Theorem (LDET1): $\text{Let}\, d=gcd(a,b).\,\text{The LDE}$
$$ax+by=c$$$\text{has a solution if and only if}\, d \mid c$
So a couple of things to note here. Whenever we write the letters LDE, we mean a Linear Diophantine Equation, so by those three letters we mean, $a, b, c \in \mathbb{Z}$, and we're looking for solutions $x$ and $y$ as integers.
This is an “if and only if” proof so we have to divide this into two components. Part 1 is assuming that the LDE has a solution, and part 2 is assuming that $d \mid c$. So let's go through the proof. Again, just rip it off like a band- aid.
So here we're going to assume that $ax+by=c$, the LDE has an integer solution, and we're going to call it $x_0$ and $y_0$. Since $d \mid a$ and $d \mid b$, by DIC we have that:
$$d \mid ax_0+by_0=c$$We have that $d \mid c$. And that's it in that direction.
So in the opposite direction, we're going to assume that $d \mid c$. What does that give us? Well that means that there exists an integer $k$ such that $dk=c$. That's what $d \mid c$ means, okay?
So we have this and what does that mean? Well it doesn't look like it's helped us much, but we do have that we - well okay we've set $gcd(a,b)=d$. So we can use some of our hammers and, in this case Bézout’s Lemma, or the Extended Euclidean Algorithm, to get that there exists integers $u$ and $v$ such that $au+bv=gcd(a,b)=d$.
So if you multiply this equation by what value? Well we want to get $c$ on the right, so if we multiply everything by $k$, we're going to get:
$$a(uk)+b(vk)=dk=c$$We actually get a solution to our LDE given by $uk$ and $vk$. $\blacksquare$
So we use Bézout’s Lemma, and we use the definition of divisibility. So notice that this also gives you a way to find a solution, right? The Extended Euclidean Algorithm can be used to find a solution of a Linear Diophantine Equation, and that's the good news about this proof is that it actually is constructive. You can actually find the $u$ and $v$ by using the Extended Euclidean Algorithm, which is pretty cool.
So now that we have a solution, or we now have a criteria for when we have a solution, and it's really strong it’s an “if and only if” it's necessary and sufficient, what do we do? So we have this really strong criteria, how can we find all of the solutions? And that's given by LDET2. So LDET2, what does this say?
Theorem (LDET2): $\text{Let}\,d=gcd(a,b)\,\text{where}\,a \neq 0\,\text{and}\,b\neq 0., \text{If}\,(x,y)=(x_0,y_0)\\\\ \text{is a solution to the LDE}ax+by=c\,\text{then all solutions are given by}\\\\ \{(x_0+\frac{b}{d}n,y_0-\frac{a}{d}n):n\in \mathbb{Z}\}$
So as $n$ ranges over all the integers, this gives you an infinite pairing of integers, and it's formed by this pairing. Think back to that line analogy, right? So what we're doing essentially is we're taking some $x_0$ and we're incrementing it by some $\frac{b}{d}$ multiples of $n$, and so that's going I guess in the x-direction instead of going up, I'm just going to go in the x direction, and in the y direction, every time we go over $1$ we're going to go down by $\frac{a}{d}n$. This of course assumes that $a$ and $b$ are positive. If $a$ and $b$ are negative, the slope of the line is going to change. But that's the main idea.
So the proof. So there's two things we need to show: first we have to show that all of these are actually integer solutions to the Linear Diophantine Equation, that's easy. Just plug it in and check.
$$a\left(x_0+\frac{b}{d}n\right)+b\left(y_0-\frac{a}{d}n\right)=ax_0+\frac{ab}{d}n+by_0-\frac{ab}{d}n=ax_0+by_0$$The $(x_0,y_0)$ we've already started with as a solution to the LDE, therefore $\left(x_0+\frac{b}{d}n,y_0-\frac{a}{d}n\right)$ is an integer solution to the LDE.
So notice that because we have a solution, we know that $gcd(a,b) \mid c$. Turns out not to be useful for this proof, but that’s something to think about.
So now in the other direction, what do we need to show? We need to show that all solutions can written in this form $\left(x_0+\frac{b}{d}n,y_0-\frac{a}{d}n\right)$. So how are we going to start? We're going to start with another solution, some new $(x,y)$ as a different solution to our LDE.
Well what does that mean? Well we have these two equations:
$$ax+by=c \quad\text{and}\quad ax_0+by_0=c$$So if you look at these two equations, we notice there's a lot of similarities, and one way to get rid of them is to cancel the $c$. So let's subtract the two equations, and what does that give us?
$$a(x-x_0)=-b(y-y_0)$$Now what we'd like to do is we'd like to say something along lines of, “Well $a \mid (y-y_0)$,” but of course that's not true. And why isn't that true? Well it's not true because $a$ and $b$ could have common divisors, and that could be a problem. So what we can do is we can actually divide out by $d$, which is $gcd(a,b)$.
So if we divide out by $d$, what do we get? Well now we get that $gcd(a,d)=gcd(b,d)=1$, and that's by DBGCD, right? If we divide by the $gcd$, then these two things are co-prime. Remember co-prime means that their $gcd$ is $1$.
So now let's look at $\frac{b}{d}$.
$$\frac{b}{d} \mid \frac{-b}{d}(y-y_0)=\frac{a}{d}(x-x_0)$$So by Coprimeness and Divisibility, $\frac{b}{d} \mid (x-x_0)$. Again, $\frac{b}{d}$ and $\frac{a}{d}$ are co-prime, and $\frac{b}{d} \mid \frac{a}{d}(x-x_0)$, so it must divide the $(x-x_0)$.
Thus there exists an integer $n$ such that $x=x_0+\frac{b}{d}n$, that's just by definition and rearrangement.
Now, at this point, something to mention here, right, is that you kind of want to say, “Well similarly $(y-y_0)=\frac{a}{d}n$,” right? But the thing that's not clear is it's not clear why the $n$ here had to be the same as the $n$ when I do this with $a$. So you actually can't quite do the exact same argument, what you can actually do is use this information that $(x-x_0)=\frac{b}{d}n$ and plug it into the equation you got when you subtracted.
$$\begin{align*} \frac{a}{d}(x-x_0)&=\frac{-b}{d}(y-y_0)\\\\ \frac{a}{d}\frac{b}{d}&=\frac{-b}{d}(y-y_0)\\\\ \frac{a}{d}&=-(y-y_0)\\\\ y_0-\frac{a}{d}n=y\;\blacksquare \end{align*}$$And that's going to complete your proof.
So again summary of LDET2. Once you have one solution, you have them all, and you can find them by multiples as follows. So take $x_0+\frac{b}{d}n$, and take $y_0-\frac{a}{d}n$. So one solution gives you all the solutions.
This is a pretty cool feature of LDET, right? If you think about like quadratic equations and cubic equations, just because you have one solution to a quadratic equation or a cubic equation equals $0$, doesn't mean that you get both solutions. Sometimes there's more work to be done. Specifically in the cubic case. The quadratic case maybe you can argue that I can find the other one. But here you just get them all for free basically. You don't have to do any other work. Once you have one you have them all.
Let's see an example.
$\text{Solve the LDE}\, 20x+35y=15.$
So let's try to do this together, okay? So the first thing that I notice here is that I have $20$, $35$, and $15$. I can actually prime factor these very quickly in my head. $4 \cdot 5$, $7\cdot 5$, and $3\cdot 5$, and I quickly see that $5$ is a prime factor of all of these things, and it's the largest common factor of all these things.
So I can do that I can divide everything by $5$. What's that going to give me?
$$4x+7y=3$$So now when I have this equation, you have options, right? If you don't see a solution immediately, you can use the Extended Euclidean Algorithm to find a solution. There's no problem with that, right, we know that $gcd(4,7)=1$, so LDET1 will tell us that we will have a solution here. Just like LDET1 told us before, right? If I divide by $5$, it doesn't change whether or not I have a solution.
So that's excellent, so now I know I have a solution. So now I just have to find a solution. Well how do I find one? Here I can just do it by inspection. $7-4=3$, so if I make $x=-1$ and $y=1$, I get a solution.
Again if you don't see it, run through the Extended Euclidean Algorithm. It’ll take a couple of seconds, but it's better than not finding a solution. If you don't find one in ten seconds, just run through the algorithm, it's okay.
So to define all solutions we invoke LDET2, Linear Diophantine Equation Theorem 2, and how do we find all solutions? Well we have one, to find all the rest of them just take $x=x_0+\frac{b}{d}n$, where in this case, $b=7$, $d=gcd(4,7)=1$, and $x_0=-1$ and $y=y_0-\frac{a}{d}n$.
$$x=-1+\frac{7}{gcd(4,7)}n \qquad y=1-\frac{4}{gcd(4,7)}n$$So here $a$ and $b$ are both positive, so that's nice, and here $gcd(4,7)=1$. Why am I writing it like this with $gcd(4,7)$ on the bottom? I'm writing it like this just to emphasize that if you didn't find the $gcd$, you should make sure that you divide by it when you're invoking LDET2. And here $n$ is any integer, okay, so that's another big thing to note, right? Quantify your variables when you're using them. So here, n is an arbitrary integer, and $x$ and $y$ is our solution to this Diophantine Equation.
Notice that this is equivalent to the solution set:
$$x=-1-\frac{7}{gcd(4,7)}n \qquad y=1+\frac{4}{gcd(4,7)}n$$So notice here that I flipped the signs here. Why is that okay? So the reason why this is okay, it's just a technical thing, but it's not hard to understand so let's try to understand this. As $n$ varies over all integers, $n$ is going to take on positive and negative values. So in this solution set when I make $n=1$ in the original equations, I get $-1+7=6$ for $x$, and I get $1-4=-3$ for $y$.
Well if I make $n=1$ in the second set of equations, I don't get the same solutions, but if I make $n=-1$ what do I get? For $x$ I get $-1-7(-1)=-1+7=6$, which is the same solution that I had up at first for $x$. And if I do that for $y$ I'm going to get $1+4(-1)=1-4=-3$ which is the same solution I had over in the first one when I plugged in $n=1$.
So really what you're doing is a change of variables. You're sending $n$ to $-n$, and you're substituting in $-n$ instead of $n$. That doesn't matter because they're just arbitrary integers. So as $n$ ranges over the integers, then $-n$ also ranges over the integers, right? $1$ corresponds to $-1$, $-5$ corresponds to $5$ and so on and so forth, right, there's this matching that occurs. So there's multiple ways to write the solution set. Don't let the flipping of the signs bother you too much. That's all I want to say about that.
One more thing. The most important definition in this course. It’s weird that I'm ending a video with this, and it's weird that we ended a week with this definition, but seeing this definition several times and having even the weekend, or a couple of days, or if it's the reading week, having the reading week to practice this definition is invaluable to you. I can't stress this enough. You have to know this definition. The rest of this course is going to use this definition like it's child's play, like it would use an equal sign, okay? So make sure you understand this definition, I can't stress this enough, okay? Make sure you know this.
Definition (Congruence): $\text{Let}\, m \in \mathbb{N}. \text{We say that two integers}\, a\, \text{and}\, b\,\text{are congruent modulo}\, m\, \text{if and only if}\\\\m\mid(a-b)\,\text{and we write}$
$$a \equiv b \pmod m$$$\text{if}\,m\nmid(a-b),\,\text{we write}\,a \not\equiv b \mod m$
It's a very simple definition, but it has far-reaching consequences. This is the definition. Learn it, commit it to memory. If $a \equiv b \mod m, m\mid (a-b)$. You have to just look at that and know that. It needs to be obvious, it needs to be quick.
So when you're doing things like the following: $3 \equiv 7 \pmod 4$, you just need to look at this and be like, “oh yeah $3\equiv 7 \mod 4$ because $4\mid (7-3).$” $10 \equiv -8 \pmod 9$, of course, right? $10-(-8)=18$ and $9 \mid 18$. Also $4 \equiv 4 \pmod {anything}$. $\bmod 6, \bmod 10, \bmod 15$.
It needs to be quick, okay? Even for larger numbers after a little bit of practice, you'll be able to say, “Oh I know that $3 \equiv 43 \pmod 4,$” and that won't seem like anything to you. I'll know that, you know, $10 \equiv 9001 \mod 9$. These are things that you'll know, and after a little bit of practice, you'll get used to why these things are true, okay?
But you do need to know this definition. Spend some time with it, play around with it, try to come up with some examples. Make sure you memorize it, make sure that like once this video is over, which will be in about a minute or so, that you can sit down and write down the definition. It's good to practice your recall. Again, this is important. It's just important. Learn this definition. For the next 3, 4 weeks possibly to the end of the course, this definition will appear in many ways, and we’ll expect students to be comfortable with this. It's a very important definition in Number Theory.
So that's all I have to say about Week 6. Again just a quick summary: we talked about gcd concepts, we talked about Linear Diophantine Equations, and we introduced congruence. Again, in this video, I didn't talk about exactly why this is important or what we need this for. We'll see that in Week 7, I'm going to save that until later. The real most important part of this week is learning this definition, and making sure that you understand at least some basic examples. That's it. Thank you very much for your attention and best of luck.