Extended Euclidean algorithm

        static void Main(string[] args)
        {
            //Solving ax + by = gcd(a, b);
            int[] result = SolveByIterativeExtendedEuclideanAlgorithm(21, 9);
            Console.WriteLine("Iterative result: x:{0}, y:{1}", result[0], result[1]);

            result = SolveByRecursiveExtendedEuclideanAlgorithm(21, 9);
            Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);

            result = SolveByIterativeExtendedEuclideanAlgorithm2(21, 9);
            Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);

            Console.ReadKey();

        }

 

        /// <summary>
        /// Extended Euclidean algorithm
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
        /// <returns></returns>
        private static int[] SolveByIterativeExtendedEuclideanAlgorithm(int a, int b)
        {
            //Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
            int lastX = 1, x = 0;
            int lastY = 0, y = 1;

            int temp = 0;
            int quotient = 0;

            while(b != 0)
            {
                temp = b;
                quotient = a / b;
                b = a % b;
                a = temp;

                //Compute xi+1= xi-1- qixi
                temp = x;
                x = lastX – quotient * x;
                lastX = temp;

                //Compute yi+1= yi-1- qiyi
                temp = y;
                y = lastY – quotient * y;
                lastY = temp;
            }

            //The answers are the second-to-last of xn and yn.
            return new int[] { lastX, lastY };
        }

 

        /// <summary>
        /// Extended Euclidean algorithm
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
        /// <returns></returns>
        private static int[] SolveByRecursiveExtendedEuclideanAlgorithm(int a, int b)
        {
            // If a is divisible by b, the algorithm ends and return the trivial solution x = 0, y = 1.
            if ((a % b) == 0)
                return new int[] { 0, 1 };
            //Otherwise, repeat the algorithm with b and a modulus b, storing the solution as x’ and y’.
            int[] result = SolveByRecursiveExtendedEuclideanAlgorithm(b, a % b);
            //Then, the solution to the current equation is x = y’, and y = x’ minus y’ times quotient of a divided by b
            return new int[] {result[1], result[0] – a / b * result[1] };
        }

 

        private static int[] SolveByIterativeExtendedEuclideanAlgorithm2(int a, int b)
        {

            int m = a;
            int n = b;

            int p = 1;
            int q = 0;

            int r = 0;           
            int s = 1;

            while (! ((m == 0) || (n == 0)) )
            {
                if (m >= n)
                {
                    m = m – n;
                    p = p – r;
                    q = q – s;
                }
                else
                {
                    n = n – m;
                    r = r – p;
                    s = s – q;
                }
            }

            if (m == 0)
            {
                return new int[] { r, s};
            }
            else
            {
                return new int[] { p, q};
            }
        }