Due Monday, September 25th, 2023

  1. Find the inverse of 35 modulo 61.  Use the extended Euclidean algorithm.
  2. What if we want to solve 3x + 5y = 0?  The zero is the weird part.  Then we don’t use the Euclidean algorithm.
    1. Give one solution by inspection (just find a clever one).
    2. Now give another one different from the first.
    3. Now give infinitely many.
  3. Find a solution to 3x + 5y = 1 (using the algorithm from class, or by guessing one).
  4. Now find infinitely many different solutions to 3x+5y = 1.  (Hint:  use questions 2 and 3 above)
  5. The goal of this exercise is to work out the runtime of the Euclidean algorithm (you may have seen this already, but do this without looking anything up):
    1. Think of the Euclidean algorithm as replacing one pair $(a,b)$ with a new pair $(a’,b’)=(b,a-qb)$ at each step.   For example, if we start with $(a,b)=(183,105)$ as on the last daily post, then we get $(a’,b’)=(b,a-b)=(105,78)$ at the next step.
    2. Show that, if $b < a/2$, then $b’ < a/2$.
    3. Show that, if $b \ge a/2$, then $b’ \le a/2$.
    4. Conclude that after two steps $(a,b) \rightarrow (a’,b’) \rightarrow (a^{”},b^{”})$, the size of the first entry has decreased by at least half (so, it may have decreased more than that).
    5. What is the runtime of the Euclidean algorithm?