00001 #include <stdio.h>
00002 
00003 int pgcd(int a, int b) {
00004     int e = (a < 0)?-a:a; // Pour assurer des valeurs positives.
00005     int f = (b < 0)?-b:b;
00006     int tmp;
00007     if (e == 0) return f;
00008     while (f > 0) {
00009         tmp   = f;
00010         f = e % f; // Calcul de r = a % b.
00011         e = tmp;
00012     }
00013     return e;
00014 }
00015 
00016 int pgcd_rec(int a, int b) { // Version récursive.
00017     int e = (a < 0)?-a:a;
00018     int f = (b < 0)?-b:b;
00019     if (f == 0) return e;
00020     return pgcd_rec(f, e%f);
00021 }
00022 
00023 /**
00024  * Calcul des coefficients de Bezout tels que d = pgcd(a,b) = a.u + b.v.
00025  */
00026 int bezout(int a, int b, int * u, int * v) {
00027     int e = (a < 0)?-a:a;
00028     int f = (b < 0)?-b:b;
00029     *u = 1;
00030     *v = 0;
00031     int u_aux = 0, v_aux = 1;
00032     int q, r, tmp;
00033     while (f > 0) {
00034         q = e/f;
00035         r = e%f;
00036         e = f;
00037         f = r; 
00038         tmp = u_aux; u_aux = *u - q*u_aux; *u = tmp;
00039         tmp = v_aux; v_aux = *v - q*v_aux; *v = tmp;
00040     }
00041     if (a < 0) *u = -(*u);
00042     if (b < 0) *v = -(*v);
00043     return e;
00044 }
00045 
00046 int inv_mod(int a, int n, int * res) {
00047     int d, u, v;
00048     d = bezout(a, n, &u, &v);
00049     if (d == 1) {
00050         *res = (n + u) % n; // u peut être négatif et il faut un résultat dans Z/nZ.
00051         return 0;
00052     }
00053     return 1;
00054 }
00055 
00056 int main() 
00057 {
00058     int a = -14, b = 21;
00059     int d1 = pgcd(a, b);
00060     int d2 = pgcd_rec(a, b);
00061     printf("d1 = %d \t d2 = %d\n", d1, d2);
00062     return 0;
00063 }