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).