/* =========================================

   Filename:  gcd_lcm.c
   Filedate:  February 21, 2006

   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)

   =========================================  */

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

/*  =====   Declarations ======  */ 

int gcd(int m, int n);

int find_a(int m, int n);

int find_b(int m, int n);

/*  =====   Definitions  ======  */ 

int gcd(int m, int n) {
  int r;
  if (m == n) {
    return n;
  }
  if (m < n) {
    r = m;
    m = n;
    n = r;
  }
  do {
    r = m%n;
    m = n;
    n = r;
  } while (r != 0);
  return(m);
}

int find_a(int m, int n) {
  if(m % n == 0) {
    return (0);
  }
  else {
    return (find_b(n, m % n));
  }
}

int find_b(int m, int n) {
  int q;
  if(m % n == 0) {
    return (1);
  }
  else {
    q = m/n;
    return (find_a(n, m % n) - q*find_b(n, m % n));
  }
}

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

int main() {

  int m, n, a, b, d, p;

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

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

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

  d = gcd(m,n);
  a = find_a(m,n);
  b = find_b(m,n);

  printf("\n");
  printf("The gcd of m = %d and n = %d is %d.\n", m,n,d);
  printf("\n");
  printf("Given a = %d, and b = %d, note that:\n", find_a(m,n),find_b(m,n));
  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/d);
  return(0);
}