對于擴(kuò)展歐幾里得主要部分說明:
1. d' = bx'+(a mod b)y', d' = gcd(b, a mod b);
    設(shè) d = gcd(a, b), 因?yàn)?d = d', 所以
    d = d' = bx'+(a mod b)y' = bx' + (a-floor(a/b)*b)y' = ay'+b(x'-floor(a/b)y');
    故有迭代:
    x = y'; y = x'-floor(a/b)y';

對于解方程主要部分說明:
1.首先給出兩個(gè)定理(證明請查看相關(guān)數(shù)論書):
   A. 方程 ax = b (mod n) 有解, 當(dāng)且僅當(dāng) gcd(a, n) | b;
   B. 方程 ax = b (mod n) 有d個(gè)不同的解, 其中 d = gcd(a, n);
2.證明方程有一解是: x0 = x'(b/d) mod n;
   由 a*x0 = a*x'(b/d) (mod n)
         a*x0 = d (b/d) (mod n)   (由于 ax' = d (mod n))
                 = b (mod n)
   證明方程有d個(gè)解: xi = x0 + i*(n/d)  (mod n);
   由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
                             = (a*x0+a*i*(n/d)) (mod n)
                             = a * x0 (mod n)             (由于 d | a)
                             = b

代碼如下:

#include <iostream>
#include <cmath>
using namespace std;

int egcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    } else {
        int tx, ty, d;
        d = egcd(b, a%b, tx, ty);
        x = ty; y = tx-a/b*ty;
        return d;
    }
}

void mels(int a, int b, int n) {
    int tx, ty, d, x0, i;
    d = egcd(a, n, tx, ty);
    if (b%d==0) {
        x0 = ((tx*b/d)%n+n)%n;
        for (i=0; i<d; i++) {
            printf("%d ", (x0+i*n/d)%n);
        }
    } else {
        printf("No solutions!");
    }
    printf("\n");
}

int main() {
    mels(14, 30, 100);
    return 0;
}