// C# program to demonstrate working
// of extended Euclidean Algorithm
using System;

class Values
{
	
	// extended Euclidean Algorithm
	public static int hcf(int a, int b,
								int x, int y)
	{
		// Base Case
		if (a == 0)
		{
			x = 0;
			y = 1;
			return b;
		}

		// To store results of
		// recursive call
		int x1 = 1, y1 = 1;
		int gcd = hcf(b % a, a, x1, y1);

		// Update x and y using
		// results of recursive call
		x = y1 - (b / a) * x1;
		y = x1;

		return gcd;
	}
	
	// Driver Code
	static public void Main ()
	{
		int x = 1, y = 1;
		int a = 2, b = 5;
		int g = hcf(a, b, x, y);
      int lcm = a*b/g;
		Console.WriteLine("HCF(" + a + " , " +
							b + ") = " + g);
      Console.WriteLine("LCM is "+lcm);
	}
}