rozszerzony alg. euklidesa i dzielenie modulo na duzych licz

Witam!!

mialbym prosbe do kogos bieglego w c# o napisanie programu: rozszerzony algorytm euklidesa oraz dzielenie modulo na duzych liczbach, musze oddac te 2 zadanka na zaliczenie w przyszla niedziele a ja jestem z programowania raczej slaby.
z gory dziekuje za pomoc!!

ps.ewentualne wynagrodzenie do uzgodnienia.

znalazlem taki kod w sieci odnosnie alg. euklidesa ale cos sie nie uruchamia:/-->

// Rozszerzony algorytm Euklidesa

using System;

namespace euklides_rozsz
{

	class Euklides
	{
		static void Main(string[] args)
		{
			int r, a, q, b;
			int x, x1, x2;
			int y, y1, y2;
			int nwd_a, nwd_b, nwd;

	
			Console.WriteLine("Podaj pierwsza liczbe");
			nwd_a = int.Parse(Console.ReadLine());

			Console.WriteLine("Podaj druga liczbe");
			nwd_b = int.Parse(Console.ReadLine());


			if (nwd_b > nwd_a)
			{
				nwd = nwd_b;
				nwd_b = nwd_a;
				nwd_a = nwd;
			}

   
	
			a = nwd_a;
			b = nwd_b;

		
			q = a/b;
			r = a - q*b;
			nwd = b;
	   
		
			x2 = 1;
			x1 = 0;
			y2 = 0;
			y1 = 1;
			x = 1;
			y = y2 - (q-1)*y1;
   
			while (r != 0)
			{
				a = b;
				b = r;
      
				x = x2 - q*x1;
				x2 = x1;
				x1 = x;
		
				y = y2 - q*y1;
				y2 = y1;
				y1 = y;      
		
				nwd = r;
				q = a/b;
				r = a - q*b; 
			}


			Console.WriteLine("NWD("+nwd_a+", "+nwd_b+") = "+nwd+" = "+x+" * "+nwd_a+" + "+y+" * "+nwd_b);

			if (nwd == 1)
				Console.WriteLine(nwd_b+" * "+y+" mod "+nwd_a+" = 1");
		}
	}
}

czy on jest poprawny,a moze wystarczy cos zmienic??

pozdrawiam