title: euclid's extended algorithm C ++
body: <p>I'm having an issue with Euclid's Extended Algorithm. (ax+by=gcd(a,b)) I'm trying to determine both the GCD and x and y. The GCD isn't a problem but using the loop method something is going wrong with x and y. Normally one number comes up as 0 and the other is an abnormally large negative number. Code follows:</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  main ()
  {
      int a,b,q,x,lastx,y,lasty,temp,temp1,temp2,temp3;
      cout &lt;&lt; "Please input a" &lt;&lt; endl;
      cin &gt;&gt; a; 
      cout &lt;&lt; "Please input b" &lt;&lt; endl;
      cin &gt;&gt; b;
      if (b&gt;a) {//we switch them
          temp=a; a=b; b=temp;
      }
      //begin function
      x=0;
      y=1;
      lastx=1;
      lasty=0;
      while (b!=0) {
          q= a/b;
          temp1= a%b;
          a=b;
          b=temp1;
  
          temp2=x-q*x;
          x=lastx-q*x;
          lastx=temp2;
  
          temp3=y-q*y;
          y=lasty-q*y;
          lasty=temp3;
      }
  
      cout &lt;&lt; "gcd" &lt;&lt; a &lt;&lt; endl;
      cout &lt;&lt; "x=" &lt;&lt; lastx &lt;&lt; endl;
      cout &lt;&lt; "y=" &lt;&lt; lasty &lt;&lt; endl;
      return 0;
  }
  </code></pre>