# MAT 338 Day 2 2011

## 2679 days ago by kcrisman

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.

%auto @interact def _(a=(3,[2..10]),b=(4,[2..10]),n=(20,[10..50])): list_of_them=list(set([a*x+b*y for x in srange(n/a+1) for y in srange(n/b+1)])) list_of_them=[item for item in list_of_them if item <= n ];list_of_them.sort() html("The nonnegative integers up to $n=%s$ which can be written as positive combinations of $a=%s$ and $b=%s$ are:"%(str(n),str(a),str(b))) print list_of_them

 a 2 3 4 5 6 7 8 9 10 b 2 3 4 5 6 7 8 9 10 n 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

## 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.

divmod(281376,29) # This gives the quotient and remainder, in parentheses (a 'tuple')
 (9702, 18) (9702, 18)

We can check that this algorithm works by multiplying and adding back together.

divmod(281376,29)[0]*29+divmod(281376,29)[1]
 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 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}\}\, .$$  To recap the proof:

• $S$ must be nonempty, so the nonnegative piece of $S$ (call it $S'$) must have the well-ordering principle apply.
• Give the name $r$ to the smallest element of $S'$, which automatically must be writeable as $r=a-bq$.  Since if $r\geq b$, we could have subtracted another copy of $b$ while keeping the remainder in $S'$, we must have that $r<b$.  Note that $r$ is the smallest nonnegative such number.
• These elements $r$ and $q$ must be unique.  The way to prove it in the book is one way, more traditional.  Another way to prove it would be to prove that the least element of a well-ordered set must be unique, along with the idea that if $bq=bq'$, then we have $q=q'$.  That actually requires proof - that $b(q-q')=0$ and $b>0$ implies $q-q'=0$, which is a property of the integers we haven't proved.  No matter how we do it, we need to make use of some factoring argument.

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.

for i in [0..10]: html("The remainder of %s squared with respect to 4 is %s"%(i,divmod(i^2,4)[1]))
 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:

for i in [0..5]: html("The remainder of %s squared with respect to 6 is %s"%(i,divmod(i^2,6)[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 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 }c|a\text{ and }c|b\text{, then }c|au+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 definition-theorem.  The greatest common divisor of two integers $a$ and $b$ is:

• The largest integer $d$ such that $d|a$ and $d|b$.
• The number achieved by applying the Euclidean algorithm (a repeated division algorithm - Theorem 1.6) to $a$ and $b$.
• The smallest positive number which can be written as $ax+by$ for some integers $x$ and $y$ (Theorem 1.8).

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 well-ordering 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 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$$  But the division algorithm says each $r_i$ is less than the previous one, yet they may not be less than zero.  Thus the well-ordering 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 two-digit numbers.

gcd(1492,1066) # Checking our text's Example 1.3!
 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 $a-qb=1\cdot a+(-q)\cdot b$ so $d\mid a-qb=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 3-1\cdot 5=2\cdot (8-1\cdot 5)-1\cdot 5=2\cdot 8-3\cdot 5$$ $$5= 1\cdot 3+2\qquad \qquad 1=3-1\cdot 2=3-1\cdot(5-1\cdot 3)=2\cdot 3-1\cdot 5$$ $$3=1\cdot 2+1\qquad\qquad 1=3-1\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.

xgcd(1492,1066)
 (2, -5, 7) (2, -5, 7)

Or, $-5\cdot 1492+7\cdot 1066=2$.

xgcd(1492,1066)[1]*1492+xgcd(1492,1066)[2]*1066 # Checking it works
 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:

• We used the backwards Euclidean algorithm to see that $2=1492\cdot (-5)+1066\cdot 7$.
• Since $2$ is itself a divisor of both 1492 and 1066, let's pick one (the smaller one!), 1066, and write it as $1066=533\cdot 2$.
• Then we can really write $1066=533\cdot 2=533\cdot (1492\cdot (-5)+1066\cdot 7)$, since after all we just saw that was a way to represent $2$!
• Now we plug this back into the original equation: $$2=1492\cdot (-5)+1066\cdot 7=1492\cdot (-5)+533\cdot 2\cdot 7=1492\cdot (-5)+533\cdot (1492\cdot (-5)+1066\cdot 7)\cdot 7$$
• If we simplify it out, that means $2=1492\cdot (-18660)+1066\cdot 26117$, which is indeed correct!

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.

• Call $c$ the smallest such $au+bv$.
• Clearly, any integer which divides $a$ and $b$ divides any such $au+bv$, so it divides the smallest such $au+bv=c$.   In particular, the gcd of $a$ and $b$ (which we'll call $d$) divides $c$.
• That means $c=de$ for some integer $e$.  But we know from the backward Euclidean algorithm/Bezout identity that $d$ can be written $d=ax+by$ for some integers $x$ and $y$.
• But if a positive number $d$ divides another positive number $c$, we know that $d\leq c$.  (To prove this, we would use the fact that there is no integer between 0 and 1 from last time!)
• Since $c$ is the smallest, and $d$ also has the right form, $d=c$ if we want to avoid a contradiction.

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.

gcd([3800,7600,1900]) # By the way, Sage allows you to calculate arbitrary GCDs like this
 1900 1900

For next time, homework (not handed in) is:

1. Read the rest of Chapter 1, doing all in-line exercises.  (You may skim the section on the least common multiple, though still do the exercises.)  Study the proof and statement of Theorem 1.13 enough that you not only understand Example 1.9, but also can do Exercise 1.15 without assistance.
2. Write the GCD of 3 and 4 as a linear combination of 3 and 4 in two different ways.  (Hint: trial and error.)
3. Use the Euclidean algorithm to find the GCD of 51 and 87, and then to write that GCD as a linear combination of 51 and 87.  Do the same thing for 151 and 187.  Find another way to write the GCD of one of these pairs as a linear combination.
4. Find the GCD of the four numbers 1240, 6660, 15540, and 19980.
5. Let $a$ be a positive integer.  What is the greatest common divisor of $a$ and $a+1$?  What is the greatest common divisor of $a$ and $a+2$?
6. The example with 8 and 5 was an example of Fibonacci numbers.   Verify that our example satisfies Exercise 1.18 (you'll need 1.17 to understand it) and then do 1.18.
7. Study the proof of Corollary 1.11, and then try to use Bezout's identity and/or Corollary 1.9 to prove the similar statement that if $a$ and $c$ are coprime, and likewise $b$ and $c$ are coprime, then $ab$ and $c$ are coprime.