For Friday September 23:

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?