# To do for Wed, Jan 23rd

• There’s a good chance we’ll move rooms (around the corner in ECCR), which would allow me to let the waitlist of students into the class. I will report more on this when I know more (perhaps Tuesday). It is not for sure.
• Please complete the when2meet poll with your availability for office hours. The link & explanation for the poll is available as an announcement in canvas (I didn’t want to put it on a public site).
• Allow me to remind you of the last proposition from class, which was this (restated here a little differently):

Proposition. Let a and b be integers. Then, for some integer k, define the quantity c = a + kb. Then gcd(a,b) = gcd(b,c).

• Suppose you want to compute the gcd of 1925 and 931. The Proposition lets you make a “move” that replaces that big problem with a smaller one. For example, using k=-2, we get c=63 and learn that:

gcd(1925, 931) = gcd(931, 63)

• So, by clever choices of moves, we can replace the original big problem with smaller and smaller ones, until the gcd is obvious. We can go like this:

gcd(1925, 931) = gcd(931, 63) = gcd(63,49) = gcd(49,14) = gcd(14,7) = gcd(7,0) = 7

• First, please verify the set of moves above (recreate it for yourself).
• Your task is to find the “slickest” / “fastest” series of moves to discover the gcd of 4181 and 6765 that you can. On Wednesday bring it to class and we will see who can get to the gcd in the fewest moves (when you get to gcd(a,0)=a, you are done).