Relevant Textbook Sections:

3.1 (The Euclidean Algorithm), 3.2 (The Extended Euclidean Algorithm).

To Do:

1. If you’d like a refresher on today’s material, watch my videos on the Euclidean algorithm and the Extended Euclidean algorithm (also on the Notes/Videos page). You can also play with the new Euclidean Algorithm page, which shows the algorithm as piles of dots and walks you through the recipe cards; use it to check your answers below.
2. Compute the gcd of 135 and 170. Show all the steps of the algorithm.
3. Consider the equation $7x + 15y = 1$. Find an integer solution to this equation using inspection or trial and error. Using it, tell me the inverse of $7$ modulo $15$ and the inverse of $15$ modulo $7$. (This should require no computation, just look at your solution and have an aha moment!)
4. Compute the gcd of 183 and 105. Show all the steps of the algorithm. Verify using the Sage Sandbox.
5. Solve $183x + 105y = 3$ by expanding your work above into “recipe cards” as shown in class. Verify your answer using Sage’s command xgcd in the Sage Sandbox.
6. 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.
   4. Find a solution to $3x + 5y = 1$ (using the algorithm from class, or by guessing one).
   5. Now find infinitely many different solutions to $3x + 5y = 1$. (Hint: use parts 1–4.)
7. 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)$, then we get $(a',b') = (105,78)$ at the next step.
   1. Show that, if $b < a/2$, then $b' < a/2$.
   2. Show that, if $b \ge a/2$, then $b' \le a/2$.
   3. 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.
   4. What is the runtime of the Euclidean algorithm?
8. (AI suggestion) Run the Euclidean algorithm on $89$ and $55$ and count the steps. Now try some other pairs of numbers of about the same size. Why are consecutive Fibonacci numbers such slow inputs? How does this compare with your bound in the previous problem?
9. (AI suggestion) Which integers $c$ can be written as $12x + 42y$ for integers $x, y$? Explain. Then find all integer solutions of $1071x + 462y = 21$.
10. (AI suggestion) Use Sage to compute $\gcd(2^{12} - 1, 2^{18} - 1)$, and a few more like it, such as $\gcd(2^{a} - 1, 2^{b} - 1)$ for other $a, b$. Guess a formula. Can you explain it by running the Euclidean algorithm “in the exponents”? (Hint: $2^{a} - 1 = 2^{a-b}(2^{b} - 1) + (2^{a-b} - 1)$.)