Hello everyone. Welcome to Week 5 of Carmen's Core Concepts. My name is Carmen Bruni, and this week we're going to talk about Math 135 Week 5. This had a lot to do with greatest common divisors. There were a couple of other topics scattered about, but that's the main topic of this week. Again I just want to remind everyone that this isn't meant to replace lectures. I mean if you use these in lieu of lectures, you're probably not going to get as much out of the course as you would have you've done both. The idea behind these videos is to give you some sort of spaced repetition where you go to the lectures during the week, and then maybe later on you go back and you review them. And that should help you reinforce your learning about these concepts.
So this week, we have a lot of topics. Instead of going through each of these bullets on this table of contents, what I'd like to do is just sort of briefly talk about it. Again, there's a lot of named theorems here. $1, 2, 3, 4, 5, 6,$ there's at least $8$. I think there's actually more I didn't actually cover them all in this video. But there's a lot of them. This can get overwhelming. Don't get overwhelmed. You're trying to use your toolbox now from the first $4$ weeks of the course, which was all proof techniques to prove different theorems in mathematics. And in this week, we're going to use Number Theory as our basis and specifically we're going to talk about the greatest common divisor. Again instead of going through all the bullets, let's just head right through it, okay? That's the main overview of this week, a lot of topics related to the greatest common divisor.
Okay so Euclid’s Theorem, this is one of my favorite theorems in mathematics.
Euclid's Theorem: $\text{There exists infinitely many primes.}$
The reason why I like it, it's very simple and it's just very creative. It's a cool little argument that we're going to talk about briefly here.
This isn't a full sketch, but the idea is that you argue by contradiction. It's tough to say that there exists infinitely many primes, but it's easier to argue that if you have finitely many, and then you reach a contradiction.
So beginning with that, we start with finitely many primes, let’s call them $p_1, p_2,...,p_n$, and then we're going to create the following number:
$$N=1+ \prod_{i=1}^n p_i$$Now why can we do this topic now? Well we talked earlier about the Fundamental Theorem of Arithmetic; Unique Factorization, right? So $N$ can be factored uniquely as a product of primes. So that means that one of these primes must divide $N$, at least one of them. One of the primes must also divide this product. That's also by Euclid’s Lemma, or the Generalized Euclid’s Lemma. So we have that a prime divides N and a prime divides this product, so by Divisibility of Integer Combinations:
$$p \left| \left(N- \prod_{i=1}^n p_i\right)=1\right.$$That's a contradiction. Again, this is just shorthand. This is just a very brief sketch, right? You shouldn't write $p$ divides something equals something else. You should write $p \left| \left(N- \prod_{i=1}^n p_i\right)\right.$and hence $p \mid 1$, but for a proof sketch I'm just going to write the shorthand. Okay so that's the idea.
I think this is a cool little proof. It doesn't require too much heavy duty mathematics. The Fundamental Theorem of Arithmetic is used, some sort of unique factorization thing, but again it's not too, too bad. I like this argument. I think it's one of these arguments that every math major should know.
Greatest common divisor. So this is something that we spent a lot of the week talking about. So let's just go over the definition again:
Definition: The greatest common divisor of $a$ and $b$ with $a \neq 0$ or $b \neq 0$ is an integer $d \gt 0$ such that
$$\begin{align*} &1)\,d \mid a \,\text{and}\,d \mid b\\\\ &2)\,\text{If}\,c \mid a\,\text{and}\,c \mid b,\,\text{then}\,c \leq d \end{align*}$$We write $d=gcd(a,b)$
The second condition is the greatest condition of a greatest common divisor. So the greatest common divisor is a common divisor, and it is the largest such common divisor. The maximal such.
Some examples: so the $gcd(120,84)=12$ that was one we saw in class. Again $12 \mid 120$ and $12 \mid 84$, and it happens to be the largest such number that has that property. $gcd(0,0)$ we define that to be $0$. It just works out a lot easier in many proofs. Works out a lot easier in many ways, so we just define $gcd(0,0)=0$.
$gcd(a,b)=gcd(b,a)$. That holds in all cases. I'll leave that as an exercise. $gcd(a,a)=|a|$. Don't forget that $a$ can be negative, so it's important to use the absolute values here, and same with $gcd(a,0)=|a|$.
The last thing, $gcd(a,b)$ exists and is unique. Perhaps not surprising. There's only one greatest common divisor, and it does exist. I mean, we know that $1$ is a common divisor of $a$ and $b$, and the biggest the common divisor could be is $min\{|a|,|b|\}$. So that proves that it exists and that it’s unique. That's all I want to say about the greatest common divisor definition. Well maybe I'll say one last thing: there are other definitions of the greatest common divisor. This is the one that we used in in our notes and that's the one that we used in class.
Okay. So let's start our theorem montage, I guess. So GCD With Remainder is our first one.
Theorem: If $a, b, q, r \in \mathbb{Z}$ and $a=bq+r$, then the $gcd(a,b)=gcd(b,r)$
So something to be careful of when you're going through these proofs; you always want to make sure you watch the $a=b=0$ case. Sometimes it'll fall through with your proof and sometimes it won’t. You have to isolate that case. I believe this one just falls through. You can double check this as you're reading this or as you're listening to this.
For the proof, whenever you're trying to prove something about a $gcd$ equalling some other object, it's usually easier, I find it easier, to write:
$$\text{Let}\, d=gcd(a,b)\,\text{and}\,e=gcd(b,r)$$Then I'm arguing about $d$ and $e$. I just find it easier to argue like this. I don't have to write the letters $gcd(a,b)$ everywhere. It just makes it easier.
The general proof technique when you're using the definition of the greatest common divisor, it's usually good to show something - well in this case - that $d \leq e$ and $e\leq d$. Just turns out to be easier that way, and then because of that, we know they must be equal.
So how do we go? So with this, we're going to start by showing that $d \leq e$ and $e \leq d$. So what connects $a, b,$ and $r$? Well $a=bq+r$. So that's the thing that we're going to have to use a lot. That's the only thing we're really given.
So since $a=bq+r$, and we know that $d =gcd(a,b)$, so it is a common divisor of $a$ and $b$. Thus by DIC, Divisibility of Integer Combinations, we have that $d \mid a+b(-q)$. But $a-bq$ that's just $r$. So hence, $d \mid r$. So $d \mid b$ and $d \mid r$, so by the maximality of $e$, so $e=gcd(b,r)$, we see that $d \leq e$.
Alright, now in reverse, it's the same sort of idea. $e \mid b$ and $e \mid r$, so once again, by DIC, $e \mid bq+r=a$, so therefore $e \mid a$. Since $d=gcd(a,b)$, we see that $e \leq d$ and hence $d=e$. $\blacksquare$
So again, this is a very typical argument of what you would do if you're trying to argue by the definition of gcd. Arguing by this definition usually works, I can almost say “always” here and be very safe. You can always go back to the definition, but it usually helps to use the tools that we've given you in this course to help prove different or new theorems. Just know that it is possible to go straight back to the definition.
What can we use GCDWR for? Remember I said it was kind of like a Division Algorithm statement, $a=bq+r$. This looks like the Division Algorithm, right, except we don't have any restriction on $r$. Usually we bound $r$. But here we don't have that restriction. $r$ can be positive, negative, it can be very big, it can be very small. Again it turns out that if we use this in sort of the context of the Division Algorithm, we actually can get this algorithm called the Euclidean Algorithm, which helps us to compute the greatest common divisor of very large numbers very, very quickly. So that's what we're going to talk about next.
Again, this is the heart of the Euclidean Algorithm. So let's see an example of the Euclidean Algorithm here.
Compute $gcd(1239,735)$
So the idea here is repeated use of GCD With Remainders.
$$1239=735(1)+504 \quad \text{Eqn 1} \quad \qquad gcd(1239,745)=gcd(735,504)$$That's basically the Division Algorithm, but on the right hand side, this is GCD With Remainders, so the $gcd(1239,735)$, think of $1239$ as my $a$ and think of $735$ as my $b$, is the same as the $gcd$ of $b$, $735$, and $r$, $504$. So with that, you can kind of see oh okay well we've gotten from the greatest common divisor of a $4$ digit number and a $3$ digit number, to the greatest common divisor of a $3$ digit number and a $3$ digit number. So we're slowly getting smaller and each of these numbers is strictly less than the previous examples, and we can keep going through this, okay?
$$\begin{align*} 1239&=735(1)+504 \quad \text{Eqn 1} \quad \qquad gcd(1239,735)&&=gcd(735,504)\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad \qquad &&=gcd(504,231)\\\\ 504&=231(2)+42 \quad \text{Eqn 3} \quad \qquad &&=gcd(231,42)\\\\ 231&=42(5)+21 \quad \text{Eqn 4} \quad \qquad &&=gcd(42,21)\\\\ 42&=21(1)+0 \quad \text{Eqn 5} \quad \qquad &&=gcd(21,0)\\\\ &&&=21 \end{align*}$$We keep going through this with the Division Algorithm, and we see by doing this, our numbers are getting smaller and smaller and smaller and eventually we're going hit $gcd(21,0)$. So eventually $0$ will appear. I'll leave that as something to think about. Why does $0$ have to always appear? That comes from the Division Algorithm though.
When we get to there, we know what the $gcd$ is, right? It's just the non-zero number, which is $21$. That was on the previous slide. And that's basically the Euclidean Algorithm.
Now the second part of the Euclidean Algorithm that we talked about was back substitution. Now back substitution answers this other question. So this slide’s very, very hectic but it's okay. So one question that we might want to know the answer to, and we'll see why in a little bit, this actually helps us to prove Euclid's Lemma, we might want to find $x,y \in \mathbb{Z}$ such that $1239x+735y=gcd(1239,735)$. So from before, this is just the previous slide:
$$\begin{align*} 1239&=735(1)+504 \quad &&\text{Eqn 1}\\\\ 735&=504(1)+231 \quad &&\text{Eqn 2}\\\\ 504&=231(2)+42 \quad &&\text{Eqn 3}\\\\ 231&=42(5)+21 \quad &&\text{Eqn 4}\\\\ 42&=21(1)+0 \quad &&\text{Eqn 5} \end{align*}$$We are not going to use this information to do back substitution. What we are going to do is we're going to start with the $21$, so that's the greatest common divisor that we figured out, and what we're going to do is we're going to back substitute. So we're going to keep isolating for the remainders, and substituting those in to the previous steps, okay?
$$\begin{align*} 1239&=735(1)+504 \quad &&\text{Eqn 1} \quad &&&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad &&\text{Eqn 2}\\\\ 504&=231(2)+42 \quad &&\text{Eqn 3}\\\\ 231&=42(5)+21 \quad &&\text{Eqn 4}\\\\ 42&=21(1)+0 \quad &&\text{Eqn 5} \end{align*}$$So step one is just isolate the remainder, that's easy, and step two now is okay well we have this $42$ here, and $42$ was the previous remainder, so we're going to isolate for the previous remainder: so we get $42=504(1)+231(-2)$, and we're going to substitute that in.
$$\begin{align*} 1239&=735(1)+504 \quad\text{Eqn 1} \quad &&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad &&=231(1)+(504(1)+231(-2))(-5)\;\text{By Eqn 3}\\\\ 504&=231(2)+42 \quad \text{Eqn 3}\\\\ 231&=42(5)+21 \quad \text{Eqn 4}\\\\ 42&=21(1)+0 \quad \text{Eqn 5} \end{align*}$$And then we're going to keep going, okay? So let's take a look at this step.
$$\begin{align*} 1239&=735(1)+504 \quad\text{Eqn 1} \quad &&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad &&=231(1)+(504(1)+231(-2))(-5)\;\text{By Eqn 3}\\\\ 504&=231(2)+42 \quad \text{Eqn 3}\quad &&=231(1)+504(-5)+231(10)\\\\ 231&=42(5)+21 \quad \text{Eqn 4}\\\\ 42&=21(1)+0 \quad \text{Eqn 5} \end{align*}$$So I took the $-5$ and distribute it in.
$$\begin{align*} 1239&=735(1)+504 \quad\text{Eqn 1} \quad &&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad &&=231(1)+(504(1)+231(-2))(-5)\;\text{By Eqn 3}\\\\ 504&=231(2)+42 \quad \text{Eqn 3}\quad &&=231(1)+504(-5)+231(10)\\\\ 231&=42(5)+21 \quad \text{Eqn 4}\quad &&=231(11)+504(-5)\\\\ 42&=21(1)+0 \quad \text{Eqn 5} \end{align*}$$In the last step I added, so $1+10=11$, so I have $11$ versions of $231$, and I have $-5$ versions of $504$. Now again I do the same argument with $231$.
$$\begin{align*} 1239&=735(1)+504 \quad\text{Eqn 1} \quad &&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad &&=231(1)+(504(1)+231(-2))(-5)\;\text{By Eqn 3}\\\\ 504&=231(2)+42 \quad \text{Eqn 3}\quad &&=231(1)+504(-5)+231(10)\\\\ 231&=42(5)+21 \quad \text{Eqn 4}\quad &&=231(11)+504(-5)\\\\ 42&=21(1)+0 \quad \text{Eqn 5}\quad &&=(735(1)+504(-1))(11)+504(-5)\;\text{By Eqn 2} \end{align*}$$So I isolated for $231$ from $\text{Eqn 2}$, substituted that in.
$$\begin{align*} 1239&=735(1)+504 \quad\text{Eqn 1} \quad &&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad &&=231(1)+(504(1)+231(-2))(-5)\;\text{By Eqn 3}\\\\ 504&=231(2)+42 \quad \text{Eqn 3}\quad &&=231(1)+504(-5)+231(10)\\\\ 231&=42(5)+21 \quad \text{Eqn 4}\quad &&=231(11)+504(-5)\\\\ 42&=21(1)+0 \quad \text{Eqn 5}\quad &&=(735(1)+504(-1))(11)+504(-5)\;\text{By Eqn 2}\\\\ &\quad &&=735(11)+504(-16) \end{align*}$$Then I took the 11 and brought it into each term, and I'm added the terms together, so I'm going to get $11$ copies of $735$, and $-16$ copies of $504$. Then with the 504, I'm going to do it again.
$$\begin{align*} 1239&=735(1)+504 \quad\text{Eqn 1} \quad &&21=231(1)+42(-5) \;\text{By Eqn 4}\\\\ 735&=504(1)+231 \quad \text{Eqn 2} \quad &&=231(1)+(504(1)+231(-2))(-5)\;\text{By Eqn 3}\\\\ 504&=231(2)+42 \quad \text{Eqn 3}\quad &&=231(1)+504(-5)+231(10)\\\\ 231&=42(5)+21 \quad \text{Eqn 4}\quad &&=231(11)+504(-5)\\\\ 42&=21(1)+0 \quad \text{Eqn 5}\quad &&=(735(1)+504(-1))(11)+504(-5)\;\text{By Eqn 2}\\\\ &\quad &&=735(11)+504(-16)\\\\ &\quad &&=735(11)+(1239+735(-1))(-16)\;\text{By Eqn 1}\\\\ &\quad &&=735(27)+1239(-16) \end{align*}$$I isolated my remainder in step one, plugged it in, simplified, and I got the following equation.
Something to mention here is that your textbook also refers to this as a Certificate of Correctness. So on every step, you can actually make sure that you're doing the computations correctly, right? There's no reason to get this computation wrong. At any step you can check your answer by just multiplying it out, making sure that I always get $21$. And if you don't then you made a mistake. So this is a good way to double check your answer when you're doing your homework.
This algorithm, in my section I'm going to teach this on Monday’s lecture. I'm going to teach the Extended Euclidean Algorithm, but this process is also known as Bézout’s Lemma and the theorem states the following:
Theorem: Let $a,b \in \mathbb{Z}$. Then there exist $x,y \in \mathbb{Z}$ such that $ax+by=gcd(a,b)$
What's the proof of this? Well the proof of this is do the Euclidean Algorithm, and then do back substitution. That's the like three line proof. Now you could go through and algebraically break this down. It is a little bit painful though, so I'm not going to. You can check it out as extra reading. It’s definitely on Wikipedia, I believe it's also in your course notes. If not, again, it's on Wikipedia. It's easily accessible, it's a very common proof. But it is tedious there's no real reason to do it. If you understood the previous two slides, there's no reason to really formally prove this. But if you're curious you can go check it out. That's Bézout’s Lemma.
Now when you have something like this, one question you might want to ask is, “What about a converse type theorem?” And a converse type theorem would look something like this: the GCD Characterization Theorem.
Theorem: If $d \gt 0, d \mid a, d\mid b$, and there exist $x,y \in \mathbb{Z}$ such that $ax+by=d$, then $d=gcd(a,b)$
So we have four conditions here that need to be satisfied. We need:
$$\begin{align*} &1)\,d \in \mathbb{Z} \land d \gt 0\\\\ &2)\, d\mid a\\\\ &3)\, d\mid b\\\\ &4)\,ax+by=d \end{align*}$$If all those things are true, then $d$ is the greatest common divisor of $a$ and $b$.
So let's think about maybe how would a proof go before I just show you the proof. What would a proof look like? Well I want to show $d$ is equal to some $gcd$ value, so let's make some new letter $e=gcd(a,b)$, okay, so some non-given letter, okay, say $e$.
Now I'm trying to show that $d \leq e$ and $e \leq d$. Well $e$ is a common divisor of $a$ and $b$ so $e \mid a$, $e \mid b$, therefore by Divisibility of Integer Combinations, once again, $e \mid ax+by=d$.
And now let's go in the opposite direction. What do we have? Well $d \mid a$ and $d \mid b$, so therefore $d \leq e$ because $e=gcd(a,b)$. Therefore, $d=gcd(a,b)$. So that's basically the idea here.
So let's just take a look at it.
Let $e=gcd(a,b)$, then since $d \mid a$ and $d \mid b$, by definition and the maximality of $e$, we have that $d \leq e$.
$e$ is the greatest common divisor of $a$ and $b$ and $d$ is a common divisor of $a$ and $b$.
Again, by definition, we see that $e \mid a$ and $e \mid b$ so by Divisibility of Integer Combinations, we have that $e \mid ax+by$, specifically the given one. This implies that $e \mid d$. So thus by Bounds By Divisibility, we know that $|e| \leq |d|$.
Here's where we needed the fact that $d \gt 0$, it's right here, we only know that $|e| \leq |d|$ and we really want that $e \leq d$, and we get that because both of these things are positive.
Hence $d=e$. $\blacksquare$
So something to note here, so my proofs and I think everyone's proofs who teaches this course, are going to get a little bit I’m going to say sloppier that's not really true. If you're going to prove something directly, a lot of the times mathematicians won't write, “Assume that $d \gt 0, d \mid a, d \mid b, \exists x,y \in \mathbb{Z}$ such that $ax+by=d$." It's kind of implied that okay well if I'm proving this and I don't give you any indication that I'm doing something else, it's going to be a direct proof. You know, if I want to prove something by contradiction, maybe I'll mention, “Assume towards a contradiction…” something like that, but in a direct proof, I'm not going to rewrite the hypothesis every single time. It's pretty clear that this is going to be a direct proof, so I don't need to rewrite it.
If you find that it helps you to rewrite the hypothesis, then I suggest you go ahead and do that. That's perfectly fine. But I'm going to try to steer away from doing that and try to write mathematics now a little bit more how you would see it in a textbook and such.
So some mixed examples. Hopefully you did a bunch of examples in class. Here are some, and I decided to mix them up instead of doing them right after the theorems.
$\text{Prove that}\,gcd(3s+t,s)=gcd(s,t)\,\text{using GCDWR}$
So here, $s,t \in \mathbb{Z}$. Again if we don't say, you take them to be as big as possible. You take s and t to belong to the domain as big as possible where this makes sense. That you know of course.
So I gave you a little hint here and said, “Use GCDWR.” Again if you're solving this at home, or if you're practicing - by the way at this point in the video, you should stop it and actually try to do this, okay? It's a good practice to even redo this even if you have done this before. So if you look at this and, again, if you don't know what GCDWR is, the first thing you should do is look it up. I've been generous and I’m actually going to copy it here, but that's a good skill to have, okay?
Recall GCDWR: If $a, b, q, r \in \mathbb{Z}$ and $a=bq+r$, then $gcd(a,b)=gcd(b,r)$.
Well okay, so I need to somehow get an $a=bq+r$ and assuming that my $b$ and $r$ are going to somehow be $s$ and $t$, that means that a should probably be something from $3s+t$ and $s$ on the left. Well if $s$ is my $b$ then maybe $3s+t$ should be my $a$, and I'm going to try to make the $q$ work.
How do we do that? Well plug those in, and just figure out what's going to work.
So $3s+t=s(3)+t$. That doesn't look like much, but that's basically GCD With Remainders, right? I mean gcd with remainder states that, $gcd(3s+t,s)=gcd(s,t)$ by setting $a=3s+t, b=s, q=3, r=t$. That's exactly a direct use of this theorem. $\blacksquare$
So I have $4$ integers, $3s+t, s, t, 3$, and I've related them in some $a=bq+r$ way. That was done right here. Then I get the conclusion for free. That's using a theorem. Just a reminder of that fact at this point.
Let's do another one, another mixed example.
$\text{Prove that if}\, a,b,x,y \in \mathbb{Z}\,\text{are such that} \,gcd(a,b)\neq0\,\text{and}\,ax+by=gcd(a,b),\,\text{then}\\\\gcd(x,y)=1.$
This is something that's important, we'll see this actually later in this video as well. So what's the idea here? So since $gcd(a,b) \mid a$ and $gcd(a,b) \mid b$, we divide by the non-zero number, $gcd(a,b)$ to see that we get the following expression:
$$\frac{a}{gcd(a,b)}x+\frac{b}{gcd(a,b)}y=1$$So here I took the hypothesis, $ax+by=gcd(a,b)$, and simplified it to get $1$ on one side, okay?
Why am I doing this? So maybe I should have mentioned this before I went through the proof, but $gcd(x,y)=1$, that's in the conclusion. When a greatest common divisor condition is in the conclusion, it's usually good to use the GCD Characterization Theorem. Why do we do that? Well the reason why you do it is because, well, it will usually work, but perhaps answering the question, “why will it work?” GCDCT has the $gcd$ condition in the conclusion. So if you want to conclude something about a greatest common divisor, it's probably good to use a theorem that allows you to conclude something about the greatest common divisor.
So that's the idea, but in order to use GCDCT I need $1$ isolated on its own. And the only equation I'm given is $ax+by=gcd(a,b)$. So how do I get the $1$ on its own? Well I probably want to divide by $gcd(a,b)$.
So I'm going a little bit backwards and a little bit forward, but doing that helps you to formulate the proof and then you just have to write it up formally.
With all this in place, now we just look at what we have and now we say, “well okay $1 \mid x,1\mid y,1\gt0$, so GCDCT implies that the $gcd(x,y)=1$.” $\blacksquare$
Now if you have the GCD Characterization Theorem in front of you, this might be confusing, because here $x$ is playing the role of $a$ in that theorem and $y$ is playing the role of $b$ in that theorem, and $\frac{a}{gcd(a,b)}$ that's going to be like your $x$ and $\frac{b}{gcd(a,b)}$ is going to be like your $y$ in the GCD Characterization Theorem.
So it can be confusing, just make sure that you remember that okay these $a, b, x, y$ are different than the $a, b, x, y$ possibly in the GCD Characterization Theorem. Well when you use it. Okay? Just because things are the same letter, doesn't mean that they have the same use. That's all I should say about that.
Good tip, so just a reminder of this tip, it's good enough that I've given it its own slide.
If the greatest common divisor condition appears in the hypothesis, then Bézout’s Lemma or the Extended Euclidean Algorithm might be useful. If the greatest common divisor condition appears in the conclusion, then GCD Characterization Theorem might be useful.
Just a good tip, okay? If it's in the hypothesis, then you can use Bézout’s Lemma to get somewhere, and if it's in the conclusion then you might want to use GCDCT to get somewhere. We're going to see a lot of examples of using Bézout’s Lemma a little bit later on in this slideshow. So again a good tip, keep it in mind.
So to finish off, this is something that I like to do at this point. Again, because I proved the Fundamental Theorem of Arithmetic last week, up to this lemma. I now want to get to this lemma as quickly as possible and I have done this. Notice that this isn't cyclic in any way, shape, or form. So, I mean, I didn't use Euclid's Lemma anywhere else in the last couple of days after going through the Fundamental Theorem of Arithmetic. So there's no logical continuity errors, anything like that. But I do like to use the Fundamental Theorem of Arithmetic to motivate this result of Euclid's Lemma because it's surprisingly difficult to prove this, even though it looks very simple. So what's Euclid's Lemma say again?
Recall Euclid's Lemma: If $p$ is prime number and $p \mid ab$ for $a,b \in \mathbb{Z}$, then $p \mid a$ or $p \mid b$.
Again, a good exercise: ask yourself, “What proof technique do I use here?” I have an “or” in the conclusion. A lot of the times it makes sense to use an argument by elimination. So take one of these two things to be false, so I'm just going to pick $p \mid a$ is false, and I'm going to also assume the hypothesis, so I'm going to suppose that $p$ is prime, $p \mid ab$, and that $p \nmid a$, and I'm going to show that $p \mid b$.
Again remember, why is this true? Well if $p \mid a$, I'm done, right? The conclusion’s true, the implication is therefore true. I don't need to do anything. So I might as well start by assuming that $p \nmid a$.
So how do I link all this together? Why did I need greatest common divisors to do this? Okay so in some sense you never need something to do something else, but it does help formulate the argument a lot nicer.
Since $p \nmid a, gcd(p,a)=1$. Well because it's equal to $1$, well by Bézout’s Lemma, again, I have a $gcd$ condition, so I might as well use Bézout’s Lemma, there exist $x,y \in \mathbb{Z}$ such that
$$px+ay=1$$Now you look at this line, and maybe in a vacuum you might wonder well why is this useful? I mean I want to show that $p \mid b$ and there's no $b$ here. So when you're doing something like this, I mean sometimes it might not be clear why this is useful, right? I mean it doesn't look like I'm making any progress towards getting $p \mid b$, but sometimes it helps to just write things down and play around with it.
In this case, it actually helps a lot because now what we're going to do is multiply by $b$, we’re going to introduce $b$. And so how do we do that? We're going to multiply everything by $b$
$$\begin{align*} px+ay&=1\\\\ pbx+aby&=b \end{align*}$$Now what do we have? Well $p \mid p$, that's clear, $p \mid ab$, that was the hypothesis, so thus by Divisibility of Integer Combinations, we have that
$$p \mid p(bx)+ab(y)=b$$Hence $p \mid b$ $\blacksquare$
So this lemma is very easy to prove once you have the right tools. Before having the right tools, this could be very tricky to prove. I've actually tried it and not had much success. You could probably do it if you're careful, but I haven't had success.
This being said, now we've reached the point where we're going to have a couple more theorems that we've done through the week. Again they're good practice, they just practice our tools, these theorems. There's a lot of names here, so don't get overwhelmed, okay? Just try to take it one at a time and practice the mix, okay, don't just practice one at a time. Practice one then practice another, then go back to the first one, maybe go to another one, mix it up, okay? Why do I say mix it up? Well because on an exam or on a test or in life, things are going to be mixed up. It's not going to be hey just solve this question using this technique. It's going to take a little bit of thinking to figure out which technique is good.
So first theorem that we have is GCD Of One, GCDOO.
Theorem: Let $a,b \in \mathbb{Z}$. Then $gcd(a,b)=1$ if and only if there exists $x,y \in \mathbb{Z}$ such that $ax+by=1$
This looks very similar to something that we did earlier. That was one of the sample exercises. But here's an “if and only if” statement so that extra “only if” part, it's going to add us a little bit more work, but that's okay.
So to go in the implication direction: suppose that $gcd(a,b)=1$. Again, we started with the $gcd$ condition so we should use Bézout’s Lemma. And it turns out that that's exactly going to work, right? If we use Bézout’s Lemma, that's exactly the conclusion. So that direction’s easy.
The other direction’s not too hard either though, right?
Suppose that there exist $x,y \in \mathbb{Z}$ such that $ax+by=1$.
So what can we do now? Now we want to conclude something about the greatest common divisor, so we should use the GCD Characterization Theorem, and that's exactly what happens here.
So again, notice the difference here. When we were proving the implication, we used Bézout’s Lemma because the $gcd$ was in the hypothesis, and when we're proving the converse, we're using GCDCT because now the greatest common divisor condition is in the conclusion.
So going through with that thought, $ax+by=1, 1 \mid a, 1 \mid b, 1 \gt 0$, therefore by GCDCT, $gcd(a,b)=1$ $\blacksquare$
And that's that. So it gives us a characterization of when $gcd(a,b)=1$.
Next one: Division By the GCD.
Theorem: Let $a,b \in \mathbb{Z}$. If $gcd(a,b)=d$ and $d \neq 0$, then $gcd(\frac{a}{d},\frac{b}{d})=1$
Notice that we need $d \neq 0$ because we want to divide by $d$, so that's clearly an important condition here. Now if we think about this, what are we given? We're given a condition with the $gcd$, so we're probably going to want to use Bézout’s Theorem, and we need to conclude something about the $gcd$ of something equaling $1$, so we're probably going to also want to use the GCD Characterization Theorem, okay?
So how do we go about this? So just try to do that exact thing, okay? So now, again, maybe a good exercise, pause the video and actually try to prove this. You should be able to prove this. It actually is sort of a “follow your nose” kind of proof, given that huge hint, okay? So take a minute and try it.
Alright let's check out the proof. Suppose that the $gcd(a,b)=d \neq 0$, then by Bézout’s Lemma, there exist $x,y \in \mathbb{Z}$such that $ax+by=d$. So there's our use of Bézout’s Lemma.
Dividing by the non-zero $d$ gives us:
$$\frac{a}{d}x+\frac{b}{d}y=1$$Well now that we have this condition, this looks a lot like the last thing we just proved, so now we can use that.
By the GCD Of One condition, we know that $gcd(\frac{a}{d},\frac{b}{d})=1$. $\blacksquare$
So you don't need to reprove things that we've proven, that's the emphasis off here. But again remember so I did say we should use GCDCT. I didn't use GCDCT, well that's because GCD Of One uses GCDCT, okay? So there are lots of ways to prove this. But again if you forget this theorem, it's fine to reprove it, that's perfectly fine. If you wanted to use GCDCT it will work, but you can make your life easier by also using GCD Of One. I've made my life harder. Sometimes I like to do that.
One more, Coprimeness and Divisibility.
Theorem: If $a, b, c \in \mathbb{Z}$ and $c \mid ab$ and $gcd(a,c)=1$, then $c \mid b$.
Again take a minute to try this out. This time I'm not going to give you hints, okay? Pause the video, try this out. It's a good exercise to do, it'll help you long term. If you're stuck maybe as a hint: notice that we have a $gcd$ condition in the hypotheses, so we should use what?
It really is that sort of obvious. If a $gcd$ condition is in the hypothesis, then use Bézout’s Lemma.
Multiplying by $b$ gives:
$$abx+cby=b$$Since $c \mid ab$, there exists $k \in \mathbb{Z}$ such that $ab=ck$. Substituting gives
$$ckx+cby=c(kx+by)=b$$Thus $c \mid b$. $\blacksquare$
Again you can use DIC here or you can go directly by the definition. I guess it's good to practice doing different things. Remind ourselves what the definition of divisibility is etc. But yeah DIC would just crush it here. $c \mid ab$, $c \mid c$ so therefore $c \mid abx+cby=b$ by DIC.
Summary. We did a lot of theorems this week. An absolute ton. I didn't even prove them all, I didn't have them all in this slideshow. I actually didn't include Finding a Prime Factor, right, that a prime factor must be less than the square root of the number if it exists. So if a number’s not prime, if a number’s composite, then it has a prime factor that's less than the square root of the number. That's FPF, again, I didn't think it’s as major as the other theorems, but there's a ton, a ton, a ton of theorems in this course, okay? Even just this week alone had like 8 or 9 or whatever was, right, there's just a ton.
There are theorem cheat pages, they are available on the Math 135 Resources Page. Do I like using these? I mean, yes or no. You should practice with them at the beginning, it's hard, but you should also practice without the cheat sheet. Why should you do that? I mean in many offerings of this course, they have given you a cheat sheet on the final, so if you do or don't get a cheat sheet on the final, that shouldn't matter. You should still practice with and without the cheat sheet. By practicing without the cheat sheet, what are you doing? You're forcing yourself to actually remember what you did in the week, and by trying to remember what you actually did in the week is actually going to help you long-term remember the content, and remembering the content is really what you should be trying to do. You shouldn't be trying to cram for a test. That's definitely not the philosophy of Math 135.
This is a course that you're going to use the core ideas for in almost every single math course you take. You really want to make sure that you know these ideas, and you have them down solidly, okay? This is not something you want to goof around with, and it’s not something you want to just cram and forget. Math, in general, is not something you want to cram and forget, but this course especially will hurt you long-term if you do that.
So practice. Practice is important, practice recalling theorems with and without the cheat sheet, practice in different settings, practice with multiple questions, mix in a problem from week 3 and try some $gcd$ problems, practice with mixing is absolutely vital towards success in this course, okay? Don't just pocket your theorems. Try to mix them up. That's what this is trying to reiterate.
The toolbox analogy. Again, if you get stuck, just calm yourself down, don't panic, panicking is always bad, and just ask yourself, “Okay. Do I understand the question? That's true, then what tools do I have to answer the question? Oh, well I have GCDWR, does that apply here?” Well GCDWR applies usually really well when the parameters in the $gcd$ depend on each other. So if that's the case, then using GCDWR a couple of times will help you out. You know, if that didn't work, well maybe there's a $gcd$ condition in the hypothesis and I should use Bézout’s Lemma, or Extended Euclidean Algorithm. Maybe the $gcd$ is in the conclusion, I can use GCDCT, I mean you have a tool box. Go through it step by step and ask yourself, “Which of these tools makes sense to use? Am I going to get closer to my goal by using this tool?”
So hopefully that gives you just a brief outline of the $gcd$ content. Again this is a really packed week, so this video is probably a lot longer than I want it to be. I really want it to be $10$ minutes and I'm sure I'm over $30$ right now, but hopefully you do it bit by bit, piece by piece, and get a little bit out of what you're doing. So thank you very much for your time. Thank you for listening, hopefully this helped you out and best of luck.