First, let's test some conductor ideas. In the cell below, which should automatically evaluate for you, Sage will automatically list all the nonnegative numbers up to $n$ that can be written as $n=ax+by$ for nonnegative integers $x$ and $y$. The default values are the $a=3,b=4$ combination we ended with last time.
Notice that with the one tried above (which we did in class last time) we definitely are getting the same answers. Also notice that the algorithm I used in the code is very naive - I just listed all possible combinations under a certain size.
It would be interesting to use this to try to verify patterns you may have noticed about the precise size of the conductor, and when it exists.
The key concepts for this lecture are:
Let's start off with the division algorithm. This basically says that if you divide an integer $a$ by a positive integer $b$, you will always get an integer remainder $r$ that is nonnegative, but less than $b$. The second part is that there is only one way to write this - that is, there is a unique remainder under these circumstances. Or, $$\text{We can always write }a=qb+r\text{ with }0\leq r<b\text{ and }q\text{ an integer.}$$ And there is only one way to do this.
This is really easy to do for small examples like $a=13,b=3$ by division ($13=4\cdot 3+1$, so $q=4$ and $r=1$), but for bigger values it's nice to have it implemented in Sage.
We can check that this algorithm works by multiplying and adding back together.
That is, $281376=9702\cdot 29+18$.
Sage note:
Notice that to access the first and second parts of the answer
(the quotient and remainder), we use square brackets, and that
we ask for the 0th and 1st parts!
In Python (the programming language behind Sage), as in many other
languages, counting begins at zero. This actually turns out to be an
enduring argument in number theory, too - do we only care about positive
numbers, or nonnegative ones? We even saw this in the stamps example,
since one could send a package for free under certain circumstances
(campus mail), but might not care about that case.
The neat thing about the division algorithm is that it is not hard to prove but still uses the Well-Ordering principle; indeed, it depends on it. The key set is the set of all possible remainders of $a$ when subtracting multiples of $b$, which we call $$S=\{a-kb\, |\, k\in\mathbb{Z}\}\, .$$ Here is the proof:
It's worth actually trying out this proof with some $a$ and $b$, say with $a=26$ and $b=3$.
As a scholium, which we won't use much immediately, note that if $b<0$ there can still be a positive remainder, but here we would need $0\leq r<|b|$ in the theorem.
It's kind of fun to prove interesting things about powers with this fact, and likely you did in a previous course. Here is some pattern for remainders of perfect squares modulo 4, for instance.
Sage note:
The syntax "for i in [0..10]:" just means we want to do
the next command for integers from 0 to 10. The rest of it
(all the percent symbols and so forth) replaces things so it
formats right.
This certainly provides strong numerical evidence that a perfect square always leaves remainder $r=0$ or $r=1$ when divided by 4. But better is a proof!
One cool thing about this proof is that if we just change the proof from using $n=(4q+r)^2$ to one using $n=(mq+r)^2$, we can essentially do the same thing for several divisions at once. If the number we divide by is $m$, then $$(mq+r)^2=m^2q^2+2mqr+r^2=m(mq^2+2qr)+r^2\, ,$$ hence all that matters for the final remainder is $r^2$, since the rest is already divisible by $m$.
But we know that there are only $b$ possibilities for $r$, so it's easy to check them all. For $m=6$:
So this verifies that $r=0,1,3,4$ are the only possible remainders of perfect squares when you divide by six.
There are lots of other propositions you are probably familiar with from previous courses. Here is a sampler.
For instance, the second one can be proved by simply noting $b=ka$ for some $k\in\mathbb{Z}$, so that $cb=c(ka)=c(ak)=(ca)k$.
We now come to a great definition-theorem. The greatest common divisor of two integers $a$ and $b$ is:
This is amazing, and the first real indication of the power of having multiple perspectives on a problem. It means that the very theoretical issue of when a GCD exists (and finding it) can be treated as a purely computational problem, characterized completely independent of actually finding divisors. And further, there is a definition purely in terms of addition and multiplication, not division or subtraction.
So if you need to actually calculate a GCD, you use the algorithm. If you want to prove something about it that has to do with dividing, you use the original definition. And if you need to prove something about it where division is hard to use, you use the third characterization. This sort of idea will come up again and again in our class - that having multiple ways to define something really helps.
This is named after Euclid because of this proposition in Euclid's Elements. The version linked to (an amazing complete Java interactive implementation of all the propositions, by David Joyce) has some explanation of what Euclid assumes in doing this - in particular, he basically assumes the well-ordering principle, although of course he doesn't think of it in these anachronistic terms.
The Euclidean algorithm says that to find the gcd of $a$ and $b$, you do the division algorithm until you get zero as the remainder, each time replacing the old division by the new remainder, and the old number by the old division number. The last non-zero remainder is the gcd. To wit: $$a=bq_1+r_1$$ $$b=r_1q_2+r_2$$ $$r_1=r_2q_3+r_3$$ and so forth until you hit $$r_{n-2}=r_{n-1}q_{n}+0$$ when you know that $r_{n-1}$ is the greatest common divisor.
We'll prove this momentarily. Let's try it with the problem from last time, $a=60$ and $b=42$.
Now try it on your own by hand for the gcd of 280 and 126.
For even more practice, try this on your own with $gcd(2013,1066)$.
As you might expect, the proof makes more sense if you try it out with actual numbers. Especially if you can find $a$ and $b$ for which the algorithm takes four or five steps, you will gain some insight.
Now, before we get to the third characterization of the gcd, we need to be able to do the Euclidean algorithm backwards. This is sometimes known as the Bezout identity, and it is worth doing some examples.
You already did one for your homework, probably by trial and error. For instance, $$6=60\cdot (-2)+42\cdot 3\; .$$
The third characterization implies that this is always possible; $gcd(a,b)=ax+by$ for some integers $x$ and $y$. Euclid backwards does this.
Sometimes it's good to write the Euclidean algorithm down one side of a table, and then go backwards up the other side of the table to obtain Bezout's identity. Here's an example with the gcd of 8 and 5; follow it from top left to the bottom and then back up the right side.
| $8=1\cdot 5+3$ | $1=2\cdot 3-1\cdot 5=2\cdot (8-1\cdot 5)-1\cdot 5=2\cdot 8-3\cdot 5$ |
| $5= 1\cdot 3+2$ | $1=3-1\cdot 2=3-1\cdot(5-1\cdot 3)=2\cdot 3-1\cdot 5$ |
| $3=1\cdot 2+1$ | $1=3-1\cdot 2$ |
| $2=2\cdot 1+0$ | Done! |
This question of Bezout's identity is implemented in Sage as xgcd(a,b), because this is also known as the eXtended Euclidean algorithm.
Or, $6=-2\cdot 60+3\cdot 42$, as we saw above.
Try to get the xgcd/Bezout for $gcd(1492,1066)$. You should get $2=-5\cdot 1492+7\cdot 1066$.
Sage note:
Do you remember what the [1] means? What do you think
the [2] means in this context?
You might also want to do more than one linear combination, for variety. How might we get another such representation?
So, substituting a Bezout identity into itself yields more and more such identities. How many such identities are there? Is there a general form? That will be answered soon.
Now let's prove the final characterization of GCD - namely, the least positive integer which can be written $au+bv$ for integers $u,v$.
Remember, even though homework is not handed in daily, you are expected to do it. And you will be suitably rewarded, since a number of these will appear on the handed-in homework.