Le PGCD d'Euclide

public class Pgcd {
    public static void main(String[] args) {
        int a = 1071, b = 462;
        System.out.print("pgcd(" + a + ", " + b + ") = ");
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        System.out.println(a);
    }
}

pgcd(1071, 462) = 21

Les tours : $(1071,462)\to (462,147)\to (147,21)\to (21,0)$. Le reste diminue strictement à chaque tour et reste positif ou nul : la boucle se termine forcément. Le PGCD est affiché avant la boucle, parce que celle-ci modifie a et b.