```package arith;

// algorithme d'Euclide

public class Euclid {

static int gcd(int u, int v) {
if (v < 0) v = -v;
if (u < 0) u = -u;
while (v != 0) { // invariant gcd(u,v) = gcd(u0,v0)
int tmp = v;
v = u % v;
u = tmp;
}
return u;
}

// renvoie {a,b,g} tels quel au+bv = g = gcd(u,v)
static int[] extendedGcdPoly(int u0, int v0) {
int[] u = { 1, 0, u0 }, v = { 0, 1, v0 };
while (v[2] != 0) {
int q = u[2] / v[2];
int[] t = { u[0] - q * v[0], u[1] - q * v[1], u[2] - q * v[2] };
u = v;
v = t;
}
return u;
}

static int[] extendedGcd(int u, int v) {
int u0 = 1, u1 = 0, u2 = u, v0 = 0, v1 = 1, v2 = v;
while (v2 != 0) {
int q = u2 / v2;
int t0 = u0 - q * v0, t1 = u1 - q * v1, t2 = u2 - q * v2;
u0 = v0; u1 = v1; u2 = v2;
v0 = t0; v1 = t1; v2 = t2;
}
return new int[] { u0, u1, u2 };
}

// division de u par v modulo m, en supposant gcd(v,m) = 1
static int divMod(int u, int v, int m) {
int[] g = extendedGcd(v, m);
assert g[2] == 1;
// g[0] * v + g[1] * m = g[2] = gcd(v,m) = 1
int r = (g[0] * u) % m;
return r < 0 ? r + m : r;
}

static void check(int u, int v, int g) {
assert (u % g == 0);
assert (v % g == 0);
for (int d = 1; d <= Math.min(u,  v); d++)
if (u % d == 0 && v % d == 0)
assert (g % d == 0);
}

public static void main(String[] args) {
assert (gcd(0, 0) == 0);
assert (gcd(2, 1) == 1);
assert (gcd(2, 2) == 2);
assert (gcd(2, 3) == 1);
assert (gcd(2, 4) == 2);
assert (gcd(10, 25) == 5);
assert (gcd(-10, 25) == 5);
assert (gcd(-10, -25) == 5);
assert (gcd(10, -25) == 5);

for (int u = 1; u <= 100; u++)
for (int v = 1; v <= 100; v++) {
check(u, v, gcd(u, v));
int[] e = extendedGcd(u,  v);
assert (e[0] * u + e[1] * v == e[2]);
check(u, v, e[2]);
}

int m = 19;
for (int u = 0; u < m; u++)
for (int v = 1; v < m; v++) {
int d = divMod(u, v, m);
assert 0 <= d && d < m;
assert u % m == (v * d) % m;
}

System.out.println("Test Euclid OK");

//    for (int u = -10; u <= 10; u++)
//      for (int v = -10; v <= 10; v++) {
//        if (v == 0) continue;
//        System.out.println(u + " % " + v + " = " + u % v);
//      }
}

}
```