Question

#include <stdio.h>

int main() {

    int i, j;

    printf("Enter two positive integers: ");

    scanf("%d%d", &i, &j); // need to validate both being positive

    while (i != j) {

        i > j ? (i -= j) : (j -= i);

    }

    printf("GCD: %d\n", i);

    return 0;

}

The above code returns a GCD from two numbers entered. Use the above program to design

a C program to compute of integer coefficients a and b such that gcd(i, j) = a xi + b x j.

EXAMPLE RUNS:

​

Enter two positive integers: 446 39

GCD: 1 = 23 * 446 + (-263) * 39

​

Enter two positive integers: 48 112

GCD: 16 = (-2) * 48 + 1 * 112

​

Enter two positive integers: 3 2

GCD: 1 = (-1) * 3 + 2 * 2

Thank you!!

Answer 1

#include <stdio.h>

// Returns gcd of two integers i and j
int gcd(int i, int j)
{
   while (i != j)
   {
       i > j ? (i -= j) : (j -= i);
   }
   return i;
}

int main()
{
   int i, j;
   printf("Enter two positive integers: ");
   scanf("%d%d", &i, &j);

   int GCD = gcd(i,j);
   printf("GCD: %d", GCD);
  
   int x=1,a,b;
   while(1)
   {
       // For a = 1, 2, 3,....
       a = x;
       b = (GCD-a*i)/j;
       if(a*i + b*j == GCD)
       {
           printf(" = %d * %d + (%d) * %d",a,i,b,j);
           break;
       }
       // For a = -1, -2, -3,....
       a = x-2*x;
       b = (GCD-a*i)/j;
       if(a*i + b*j == GCD)
       {
           printf(" = (%d) * %d + %d * %d",a,i,b,j);
           break;
       }
       x++;
   }
   return 0;
}

output screenshot: