public class Diophant
{
 	static public int getY(int a,int b,boolean ausgabe)
 	{
		int n= 0,wert;
		n = Eukgetn(n,a,b);
		int k[] = new int[n+1];
		int q [] = new int[n+1];
		int p [] = new int[n+2];
		n =0;
		n= Euk(n,q,a,b,p);
		wert =(Dioy(n,q,k)+b)%b;
		if(ausgabe==true) ausgeben(n,k,q,p,'y');
		return wert;
	}

	static public int getX(int a,int b,boolean ausgabe)
	{
		int n= 0,wert;
		n = Eukgetn(n,a,b);
		int k [] = new int[n+1];
		int q [] = new int[n+1];
		int p [] = new int [n+2];
		n =0;
		n= Euk(n,q,a,b,p);
		wert = (Diox(n,q,k)+b)%b;
		if(ausgabe==true) ausgeben(n,k,q,p,'x');
		return wert;

	}

	static public void ausgeben(int n,int k[],int q[],int p[],char a)
	{
		System.out.println("Euklid: Anfangswerte a = "+p[0]+ " b = "+p[1]);
		for(int i=2;i!=p.length;i++)
		{
			System.out.println("");
			System.out.println("r"+(i-2)+"\t=\tq"+(i-2)+"*r"+(i-1)+"\t+\tr"+(i));
			System.out.println(p[i-2]+ "\t=\t"+ q[i-2]+"*"+p[i-1]+"\t+\t"+p[i]);
		}

		System.out.println("\t\t   ^");
		System.out.println("\t\t  ggt");
		System.out.println("");
		System.out.println("Diophant: Nach "+a+" Aufgeloest");
		for(int i=2;i!=k.length;i++)
		{
			System.out.println(a+""+i+"\t=\t"+a +(i-2) +"\t-\tq"+ + (i-2) + "\t*\t"+a+(i-1));
			System.out.println(k[i] + "\t=\t" + k[i-2]+ "\t-\t" +  q[i-2]+"\t*\t"+k[i-1]);
			System.out.println("");
		}
	}

	static public int Diox(int n,int q[],int k[])
	{
		if (n==0)
		{
			return 1;
		}
		else if (n==1)
		{
			return 0;
		}
		else
		{
			k[n-2] = Diox(n-2,q,k);
			k[n-1] =Diox(n-1,q,k);
			k[n] = k[n-2]-q[n-2]*k[n-1];
			return k[n];
		}

	}
	static public int Dioy(int n,int q[],int k[])
	{
		int yfirst,ysecond;
		if (n==0)
		{
			return 0;
		}
		else if (n==1)
		{

			return 1;
		}
		else
		{

			k[n-2] = Dioy(n-2,q,k);
			k[n-1] = Dioy(n-1,q,k);
			k[n] = k[n-2]-q[n-2]*k[n-1];
			return k[n];
		}

	}

	static public int Euk(int n,int [] q,int a,int b,int [] p)
	{
		if (a<b)
		{
			return Euk(n,q,b,a,p);
		}
		else if (b==0)
		{
			p[n] = a;
			p[n+1] = b;
			return n;
		}
		else
		{
			p[n] = a;
			p[n+1] = b;
			q[n] = a/b;
			return Euk(n+1,q,a%b,b,p);
		}

	}
	static public int Eukgetn(int n,int a,int b)
		{
			if (a<b)
			{
				return Eukgetn(n,b,a);
			}
			else if (b==0)
			{
				return n;
			}
			else
			{
				return Eukgetn(n+1,a%b,b);
			}

	}

}