Compute the gcd of 135 and 170. Show all the steps of the algorithm, as in the video.
Consider the equation $7x + 15y = 1$. Find an integer solution to this equation using inspection or trial and error.
Using the previous problem, tell me the inverse of $7$ modulo $15 and the inverse of $15$ modulo $7$. (This should require no computation, just look at the previous problem and have an aha moment!)
Compute the gcd of 183 and 105. Show all the steps of the algorithm, as in the video. Verify using the Sage Sandbox (link at left for whenever you need it).
Solve $183x + 105y = 3$ by expanding your work above into “recipe cards” as shown in class. Here’s another video which explains this (~11 mins) in case you need a refresher. Verify your answer using Sage’s command xgcd (Sage Sandbox).
Find the inverse of 35 modulo 61. Use the extended Euclidean algorithm. Verify your answer by multiplying out.
What if we want to solve 3x + 5y = 0? The zero is the weird part. Then we don’t use the Euclidean algorithm.
Give one solution by inspection (just find a clever one).
Now give another one different from the first.
Now give infinitely many.
Find a solution to 3x + 5y = 1 (using the algorithm from class, or by guessing one).
Now find infinitely many different solutions to 3x+5y = 1. (Hint: use questions 2 and 3 above)
If time remains: 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):
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.
Show that, if $b < a/2$, then $b’ < a/2$.
Show that, if $b \ge a/2$, then $b’ \le a/2$.
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).