#include <stdio.h>


/* Die folgende Funktion gibt von Zahl modulo mod die
   Standarddarstellung modulo mod zurueck */

long Reduziere(long Zahl, long mod)
{
	while(Zahl<0)
	{
		Zahl=Zahl+mod;
	}
	while(Zahl>=mod)
	{
		Zahl=Zahl-mod;
	}
    
	return(Zahl);
}




/* ggt-Funktion: Rueckgabe: ggT. Die Rueckgabe des Koeffizienten
   in der Darstellung des ggT vor der zweiten eingegebenen Zahl 
   wird ueber den Zeiger koeffizient geregelt. */

long ggT(long ZahlA, long ZahlB, long *koeffizient)
{
	long  Q=0,A=0,AV,AVV, S=0, SV=1,SVV=0;
   
	AV=ZahlB;
	AVV=ZahlA;
 
	do
	{
        //A= Reduziere(AVV, AV);  
        /* Die Reduziere-Funktion wirkt genauso wie der modulo-Operator,
        hat bei grossen Zahlen aber eine drastisch schlechtere Laufzeit.*/
		A=AVV%AV;
		Q=(AVV-A)/AV;
 
		S=SVV-SV*Q;
		AVV=AV;  AV=A;  A=0;
		SVV=SV;  SV=S;  S=0;

	} while(AV!=0);  
 
 /* ggT von ZahlA,ZahlB: AVV*/
 /* Darstellung: ggT=     RVV* ZahlA + SVV * ZahlB                  */
 
	*koeffizient=SVV;
 
	return(AVV);
   
}


/*---------------------------------------------*/

int main(void)
{
	long Modul, Einheit, gegete, Inverses;
 
	printf("Dieses Programm prueft in Z/mZ, ob es sich bei einer\n\
vorgelegten Zahl a um eine Einheit handelt und bestimmt ggfs.\n\
in Z/mZ ihr Inverses 1/a.\n\
Geben Sie bitte zunaechst den Modul m ein.\n\
Es muss eine natuerliche Zahl groesser oder gleich 2 sein: "); 
 
	scanf("%li",&Modul);
 
	if(Modul<=1)
	{
		printf("Programm wird wegen fehlerhafter Eingabe beendet.\n");  
		return(1);
	} 
 
	printf("Geben Sie nun bitte die zu ueberpruefende Zahl a ein.\n\
Diese natuerliche Zahl soll groesser oder gleich 1 und kleiner oder gleich %li sein: ",(Modul-1));  
  
	scanf("%li",&Einheit); 
 
	if(Modul<=Einheit || Einheit<=0)
	{
		printf("Programm wird wegen fehlerhafter Eingabe beendet.\n");  
		return(1);
	}
   
	gegete=ggT(Modul, Einheit, &Inverses);
 
 
	if(gegete==1)
	{
		printf("Bei %li handelt es sich in Z/%liZ um eine Einheit.\n", Einheit, Modul);  
		printf("Hier gilt: 1/ %li = %li .\n", Einheit, Reduziere(Inverses, Modul)); 
	}
	else
	{
		printf("Die Zahl %li ist in Z/%liZ keine Einheit.\n", Einheit, Modul);  
	}
 

 
	return(0);
  
}