欧几里得扩展算法

1. 计算元素逆元

题目描述

编程实现欧几里得扩展算法（辗转相除）求元素逆元，即任给整数e,m互素，求出d，使得ed=1 (mod m)。

提示：对同余式 ex+my=(e,m)=1，求解x。

对e=6597求出d，使得ed=1 mod 11200，求解结果d=3533

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

//对给定整数e,m作辗转相除，求出使得ex+my=(e,m)的x,y值，返回(e,m) 
long Egcd(long e, long m, long *x, long *y) {
    if (m == 0) {
        *x = 1;
        *y = 0;
        return e;
    } else {  
        long g = Egcd(m, e % m, x, y);
        long tmp = *x - e / m * (*y);
        *x = *y;
        *y = tmp;
        return g;   
    }
} 

int main() {
    long e, m;
    long x, y;
    long gcd;
    printf("Please enter the value of e: ");
    scanf("%ld", &e);
    printf("Please enter the value of m: ");
    scanf("%ld", &m);
    gcd = Egcd(e, m, &x, &y);
    if (gcd < 0) {
        gcd = 0 - gcd;
        x = 0 - x;
        y = 0 - y;
    } 
    if (gcd != 1) {
        printf("\n(%ld, %ld) = %ld, ", e, m, gcd);
        printf("the inverse element of %ld does not exit!\n", e);
    } else {
        printf("\n(%ld, %ld) = %ld, %ld * %ld = 1(mod %ld)\n", e, m, gcd, e, x, m);
        printf("The inverse element of %ld is %ld\n", e, x);    
    }
    return 0;
}

2. 计算最大公因数

题目描述

设计一个程序，计算100000以内任意两个整数a,b的最大公因数，进一步求出整数s,t 使得 sa+tb=(a,b)

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

//对给定整数a,b作辗转相除，求出使得sa+tb=(a,b)的s,t值，返回(a,b)
long Egcd(long a, long b, long *s, long *t) {
    if (b == 0) {
        *s = 1;
        *t = 0;
        return a;
    } else {
        long g = Egcd(b, a % b, s, t);
        long tmp = *s - a / b * (*t);
        *s = *t;
        *t = tmp;
        return g;   
    }
} 

int main() {
    long a, b;
    printf("Please enter the value of a: ");
    scanf("%ld", &a);
    printf("Please enter the value of b: ");
    scanf("%ld", &b);
    long s, t;
    long gcd;
    gcd = Egcd(a, b, &s, &t);
    if (gcd < 0) {
        gcd = 0 - gcd;
        s = 0 - s;
        t = 0 - t;
    } 
    printf("\n(%ld, %ld) = %ld\n", a, b, gcd);
    printf("(%ld, %ld) = %ld * %ld + %ld * %ld\n", a, b, s, a, t, b);
    return 0;
}