Welcome back!
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.
Click to the left again to hide and once more to show the dynamic interactive window 
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  whether about Exercise 1.25, or about the precise size of the conductor, and when it exists.
The key concepts for this lecture are those you read about  namely, the division algorithm, greatest common divisor, and Euclidean algorithm. Then we'll put them together with the Bezout identity, Theorem 1.8 in the book.
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.}$$
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.
(9702, 18) (9702, 18) 
We can check that this algorithm works by multiplying and adding back together.
281376 281376 
That is, $281376=9702\cdot 29+18$. (The book would use $281376=9702\, .\, 29+18$ in the British style  another reason for us to use it less and less.)
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 WellOrdering 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=\{akb\, \, k\in\mathbb{Z}\}\, .$$ To recap the proof:
We won't use it much immediately, but the book does have something similar to say if $b<0$.
Let's look briefly at Example 1.2 and Exercise 1.2.
The remainder of 0 squared with respect to 4 is 0 The remainder of 1 squared with respect to 4 is 1 The remainder of 2 squared with respect to 4 is 0 The remainder of 3 squared with respect to 4 is 1 The remainder of 4 squared with respect to 4 is 0 The remainder of 5 squared with respect to 4 is 1 The remainder of 6 squared with respect to 4 is 0 The remainder of 7 squared with respect to 4 is 1 The remainder of 8 squared with respect to 4 is 0 The remainder of 9 squared with respect to 4 is 1 The remainder of 10 squared with respect to 4 is 0 The remainder of 0 squared with respect to 4 is 0 The remainder of 1 squared with respect to 4 is 1 The remainder of 2 squared with respect to 4 is 0 The remainder of 3 squared with respect to 4 is 1 The remainder of 4 squared with respect to 4 is 0 The remainder of 5 squared with respect to 4 is 1 The remainder of 6 squared with respect to 4 is 0 The remainder of 7 squared with respect to 4 is 1 The remainder of 8 squared with respect to 4 is 0 The remainder of 9 squared with respect to 4 is 1 The remainder of 10 squared with respect to 4 is 0 
This certainly provides strong numerical evidence for Example 1.2  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 the proof provided 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$, as in the book:
The remainder of 0 squared with respect to 6 is 0 The remainder of 1 squared with respect to 6 is 1 The remainder of 2 squared with respect to 6 is 4 The remainder of 3 squared with respect to 6 is 3 The remainder of 4 squared with respect to 6 is 4 The remainder of 5 squared with respect to 6 is 1 The remainder of 0 squared with respect to 6 is 0 The remainder of 1 squared with respect to 6 is 1 The remainder of 2 squared with respect to 6 is 4 The remainder of 3 squared with respect to 6 is 3 The remainder of 4 squared with respect to 6 is 4 The remainder of 5 squared with respect to 6 is 1 
So this verifies that $r=0,1,3,4$ are the only possible remainders of perfect squares when you divide by six.
From Transitions to Higher Math, I assume that you are familiar with the kind of theorems in Exercise 1.3 and Theorem 1.3. It is true that Corollary 1.4 is quite useful: $$\text{If }ca\text{ and }cb\text{, then }cau+bv\text{ for all integers }u\text{ and }v.$$I will probably ask you to prove a couple things like this. I also assume that the notion of a common divisor of $a$ and $b$ (that is, an integer $d$ dividing both $a$ and $b$) is familiar. You may want to write down all the common divisors of $36$ and $30$ for practice.
We now come to a great definitiontheorem. 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.
Notice that Joyce's online Java Elements version of this proposition has some explanation of what Euclid assumes in doing this  in particular, he basically assumes the wellordering principle, which our text uses when it says "after at most $b$ steps". Let's clarify this.
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 nonzero remainder is the gcd. To wit: $$a=bq_1+r_1$$ $$b=r_1q_2+r_2$$ $$r_1=r_2q_3+r_3$$ But the division algorithm says each $r_i$ is less than the previous one, yet they may not be less than zero. Thus the wellordering principle applied to the set of remainders must have a least positive element, and that's your answer. (Since $b$ is finite, this also implies you end in a finite number of steps, but you don't even need this to actually start the process.)
Let's try to find the GCD with some twodigit numbers.
2 2 
Now try it on your own by hand for the gcd of 280 and 126.
The other part of the proof is of course Lemma 1.5. In words:
If $d\mid a$ and $d\mid b$ then $aqb=1\cdot a+(q)\cdot b$ so $d\mid aqb=r$ (the remainder) as well, as often as you want; since the greatest common divisor is the biggest, and since $d$ divides all relevant numbers, the greatest of these is the same as the greatest of the divisors of the remainder.
Now, before we get to Theorem 1.8, the third characterization of the gcd, we need to be able to do the Euclidean algorithm backwards. That is the content of Theorem 1.7 (the Bezout identity), and it is worth doing some examples. 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\qquad \qquad 1=2\cdot 31\cdot 5=2\cdot (81\cdot 5)1\cdot 5=2\cdot 83\cdot 5$$ $$5= 1\cdot 3+2\qquad \qquad 1=31\cdot 2=31\cdot(51\cdot 3)=2\cdot 31\cdot 5$$ $$3=1\cdot 2+1\qquad\qquad 1=31\cdot 2$$ $$2=2\cdot 1+0\qquad \qquad \text{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.
(2, 5, 7) (2, 5, 7) 
Or, $5\cdot 1492+7\cdot 1066=2$.
2 2 
You might also want to do more than one linear combination, as in Exercise 1.6. The answer in the back is unmotivated. Here is another way to think about it:
So, substituting a Bezout identity into itself yields more and more such identities. How many are there? Is there a general form? That will be answered next time.
Now let's prove the final characterization of GCD  namely, the least positive integer which can be written $au+bv$ for integers $u,v$. What follows is not quite right yet, but will be in the final form.
Finally, let's think about an interesting corollary of all this. Remember, $a$ and $b$ have greatest common divisor 1 precisely when you can write $ax+by=1$ for some integers $x$ and $y$. That means, in fact, that you can write any integer as a (linear) combination of $a$ and $b$ if their gcd is 1!
This is a property I think people would have come up with no matter how the development of mathematics had gone; the pairs of integers such that you can write any number as a combination of them. We call these (as on page 10) relatively prime numbers or coprime numbers.
One nice thing that comes from it are the corollaries on page 11 which are natural, yet only use the notion of not sharing factors. For instance, one can check that $gcd(11\cdot 38,11\cdot 45)=11\cdot gcd(38,45)$, but it's nice to be able to prove that without actually checking factors.
1900 1900 
For next time, homework (not handed in) is:
