title: How to write Extended Euclidean Algorithm code wise in Java?
body: <p>I have a question which is actually requires a bit of understanding Euclidian Algorithm. Problem is simple. An int "First" and int "Second" numbers are given by the user via Scanner.
  Than we need to find greatest common divisor of them. Than the process goes like explained below:  </p>
  
  <p>Now Assume that the First number is: 42 and the Second is: 30 - they've given by the user. -</p>
  
  <p>int x, y;    </p>
  
  <p>(x * First) + (y * Second) = gcd(First, Second); // x ? y ?    </p>
  
  <p>To Find GCD you may use: gcd(First, Second); Code is below:    </p>
  
  <pre><code>public static int gcd(int a, int b)    
      {    
          if(a == 0 || b == 0) return a+b; // base case   
          return gcd(b,a%b);    
      }    
  </code></pre>
  
  <p>Sample Input: First: 24 Second: 48 and Output should be x: (-3) and y: 2<br>
  Sample Input: First: 42 Second: 30 and Output should be x: (-2) and y: 3<br>
  Sample Input: First: 35 Second: 05 and Output should be x: (0) and y: 1    </p>
  
  <pre><code> (x * First) + (y * Second) = gcd(First, Second); // How can we find x and y ? 
  </code></pre>
  
  <p>I would very appreciate it if you could show a solution code wise in java thanks for checking!    </p>