/* ========================================= 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 #include /* ===== 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); }