/* =========================================
   Filename:  gcd_lcm.c
   Filedate:  February 25, 2007

   The program asks for values for m and n to be input
   on the command line.  It then calculates 

          d = g.c.d(m, n)

   and finds integers a and b so that

          d = a*m + b*n

   It also reports l.c.m.(m,n)

   NOTE:  The whole program is a loop.
   =========================================  */

#include<stdio.h>
#include<stdlib.h>

/*  =====   Main  ======  */ 

int main() {

  int m, n, a, b, c,d, q, r, x, y;
  int save_a, save_b;

  printf("Input a positive integer:\n");
  scanf("%d", &m);
  printf("Now input a second positive integer:\n");
  scanf("%d", &n);

  if (m <= 0 || n <= 0) {
    printf("The integers m and n must be positive!\n");
    exit(1);
  }

  if (m < n) {
    a = m;
    m = n;
    n = a;
  }

  a = 0;
  b = 1;
  c = 1; 
  d = 0;
  x = m;
  y = n;

  r = x%y;

  while (r > 0) {
    q = (x-r)/y;
    save_a = a;
    save_b = b;
    a = c - a*q;
    b = d - b*q;
    c = save_a;
    d = save_b;
    x = y;
    y = r;
    r = x%y;
  } 

  printf("\n");
  printf("The gcd of m = %d and n = %d is %d.\n", m,n,y);
  printf("\n");
  printf("Given a = %d, and b = %d, note that:\n", a,b);
  printf("\n");
  printf("   a*m + n*b = %d\n", a*m+b*n);
  printf("\n");
  printf("Also, the lcm of m = %d and n = %d is %d.\n", m,n,m*n/y);
  return(0);
}