title: Question about the Extended Euclidean Algorithm
body: <p>So about the Extended Euclidean algorithm, the algorithm that finds, <code>a</code>, <code>b</code>, and <code>d</code> in the equation <code>am+bn=d</code>, where <code>m</code> and <code>n</code> are two positive integers, <code>d</code> is their GCD, and <code>a</code> and <code>b</code> are two integers (not necessarily positive)</p>
  <p>So the book I am following has the following instructions for implementing this algorithm:</p>
  <pre><code>E1. [Initialize.] Set a′ ← b ← 1, a ← b′ ← 0, c ← m, d ← n.
  
  E2. [Divide.] Let q and r be the quotient and remainder, respectively,
        of c divided by d. (We have c = qd + r and 0 ≤ r &lt; d.)
  
  E3. [Remainder zero?] If r = 0, the algorithm terminates; 
        we have in this case am + bn = d as desired.
  
  E4. [Recycle.] Set c ← d, d ← r, t ← a′, a′ ← a, a ← t − qa, t ← b′, b′ ← b, b ← t − qb, 
        and go back to E2.
  </code></pre>
  <p>My problem is that I don't particularly understand all the math around this algorithm, I understand the normal Euclidean algorithm well enough, so I understand half of the extended one as well. What I don't understand is the need for <code>a'</code> and <code>b'</code> as well <code>t</code> (I get that <code>t</code> is a temporary variable but I don't get the <code>a = t - qa</code> and <code>b = t - qb</code> part). That as well as the initialization of the variables <code>a</code>, <code>a'</code>, <code>b</code>, and <code>b'</code> as well as the swapping of the values between them on each iteration. Can anybody help me bridge these gaps in my understanding of this algorithm?</p>