This week we practice with abstraction. Chapter 2 in Sethuraman is our starting point and model.

1. If you think you might learn something by working more on problem 6 from the last homework, here's a place you might start: Use the Euclidean algorithm to find gcd(34,21) (pretend you don't already know the answer is 1) and then (working it backwards) see what it finds for a solution to

   	34x + 21y = 1
   

   (I chose two adjacent Fibonacci numbers for this example - large enough so that you can see what's happening, small enough so that it shouldn't take you too long.)

2. If you didn't do problem 7 last time, do it now. Prove that the Euclidean algorithm finding gcd(m,n) finishes in at most 2*log₂(m) steps (assuming m < n). That's much faster than the bound of m steps that we know works because the remainder is at most m-1 at the first step (and so on).

   One way to do that is to show that after two steps the smaller number (the second remainder) is at most m/2. Here's a hint. If the first remainder is already < m/2 then there's nothing more to prove because the second remainder will be even smaller. If the first remainder is > m/2 you should be able to see directly what the quotient and remainder are the next time. (If you can't see it right away algebraically, try a few numerical examples.)

3. Use Sethuraman's axioms for a ring (page 31) to prove all the assertions listed on page 41. (We did some of those in class.)

4. Answer the question in the last sentence of Remark 2.8 (on page 42).

5. Write out the complete addition and multiplication tables for arithmetic on the 6 and 7 hour clocks. Your answer begins this way

   6 hour clock:
   
   	+  0 1 2 3 4 5 		*  0 1 2 3 4 5 
              -----------             -----------
   	0 |0 1 2 3 4 5          0 |0 0 0 0 0 0
           1 |1 2 3 4 5 0          1 |0 1 2 3 4 5
           2 |2 3 4 5 0 1          2 |0 2 4 0 2 4
           3 |
   

   Then spend some time commenting on what seems interesting to you. Speculate about what you would expect to find if you went to the trouble of working out the full tables for 12 and 13 hour clocks.

   Note: these observations are the most important part of the problem. I assume you can do all the arithmetic and get the answers right, so I won't even spend time checking it. What I want to see you do is think about what you can learn from all that arithmetic.

   Try to state your observations as formal conjectures, like "If (n has some property) then for the n hour clock the + (or *) table will (have some particular property)"

   (Some of your conjectures might be for every n, some for only particular kinds of integers n.)

   If you get really ambitious you can try to prove that some of your conjectures are theorems.

   Note: Sethuraman discusses the 2-, 3- and n-hour clocks (without calling them that, and with a particularly clumsy notation) in examples 8 and 9 on pages 38-40. You're free to read that (of course) but I don't recommend it.

6. Work on problem 10 in Chapter 2 on the ring of numbers of the form a + b*sqrt(-5). (You will find this long problem on pages 56-58.) You probably won't be able to do it all, both because it's long and because there's lots to learn along the way. Just get as far as you can. You can start with the fact that each element of the ring in question can be written uniquely in the form

   	a + b sqrt(-5)
   

   for integers a and b . That way you won't need to look back at Exercise 5.