NTP

22. Prosireni Euklidov algoritam.

Ako je d = nzd(a, b), onda postoje celi brojevi x i y takvi da je
d = a * x + b * y

Primer:
a = 39, b = 15
39 = 39 * 1 + 15 * 0
15 = 39 * 0 + 15 * 1
9 = 39 * 1 + 15 * (-2)
6 = 15 * 1 + 9 * (-1) = 39 * (-1) + 15 * 3
3 = 9 * 1 + 6 * (-1) = 39 * 2 + 15 * (-5)

int nzdext(int a, int b) {
  int c;
  int q;
  int xa, ya, xb, yb, xc, yc;
  // a = ap * xa + bp * ya
  xa = 1; ya = 0;
  xb = 0; yb = 1;
  while (b != 0) {
    c = a % b;
q = a / b;
xc = xa – q * xb;
yc = ya – q * yb;
a = b; xa = xb; ya = yb;
b = c; xb = xc; yb = yc;
  }
// u a se nalazi nzd, a u xa i ya brojevi za koje vazi
// nzd(ap, bp) = ap * xa + bp * ya
}