For Friday:
- Compare your last few daily posts to the solutions: Sep 12 solns, Sep 20 solns.
- Find the inverse of 6 modulo 13 using the Euclidean algorithm.
- 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)?
- $x \pmod{3}$
- $x \pmod{12}$
- $x \pmod{5}$
- The goal of this exercise is to work out the runtime of the Euclidean algorithm:
- 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).
- What is the runtime of the Euclidean algorithm?