EUCLID and EXTENDED EUCLID algorithm.

#include<stdio.h>

#include<conio.h>

void main()

{

            int a,b,r1,r2,q,r,s1,s2,s,t1,t2,t,gcd,ans,c;

            clrscr();

            printf("0:EUCLIDIAN\n");

            printf("1:EXTENDED EUCLIDIAN\n");

            printf("Plese enter your choice\n");

            scanf("%d",&c);

            if(c==1)

            {

            printf("Enter the numbers to find GCD\n");

            printf("Enter r1 and r2:\n");

            scanf("%d%d",&a,&b);

            r1=a;

            r2=b;

       s1=1;

       s2=0;

       t1=0;

       t2=1;

            while(r2>0)

            {

                        q=r1/r2;

                        r=r1-(r2*q);

                        r1=r2;

                        r2=r;

                        s=s1-(q*s2);

                        s1=s2;

                        s2=s;

                        t=t1-(q*t2);

                        t1=t2;

                        t2=t;

            }

            gcd=r1;

            s=s1;t=t1;

            ans=(s*a)+(t*b);

            printf("\nGCD For %d and %d  GCD(%d,%d) is : %d",a,b,a,b,gcd);

            printf("\nGCD For %d and %d  GCD(%d,%d) is (%d*%d)+(%d*%d)=%d",a,b,a,b,s,a,t,b,ans);

            }

            else

            {

            printf("Enter the numbers to find GCD\n");

            printf("Enter r1 and r2 :\n");

            scanf("\t%d\t%d",&r1,&r2);

            a=r1;

            b=r2;

            while(b>0)

            {

                        q=a/b;

                        r=a-(b*q);

                        a=b;

                        b=r;

            }

            gcd=a;

            printf("\nGCD For %d and %d  GCD(%d,%d) is : %d",r1,r2,r1,r2,gcd);

            }

            getch();

}

output: