For Friday:

1. Compare your last few daily posts to the solutions: Sep 12 solns, Sep 20 solns.
2. Find the inverse of 6 modulo 13 using the Euclidean algorithm.
3. If you know $x \equiv 3 \pmod{6}$, what do you know (if anything) about the following values (in other words, could they be anything, or are they restricted to one or a few possibilities)?
   1. $x \pmod{3}$
   2. $x \pmod{12}$
   3. $x \pmod{5}$
4. The goal of this exercise is to work out the runtime of the Euclidean algorithm:
   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?