Find the inverse of 35 modulo 61. Use the extended Euclidean algorithm.
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)
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).