Extended Euclidean Algorithm (with complete output)

output.txt

//This is how the output looks

    i    g    s    u    v
    0 9692    0    1    0
    1  360   26    0    1
    2  332    1    1  -26
    3   28   11   -1   27
    4   24    1   12 -323
    5    4    6  -13  350



ggt(9692,360)=4 =(-13*9692)+(350*360)

SomeMath.java

public class SomeMath {

    public static int extendedEuclideanAlgorithm(int a, int b) {
        ArrayList<Integer> g = new ArrayList<>();
        g.add(Math.max(a, b));
        g.add(Math.min(a, b));
        ArrayList<Integer> s = new ArrayList<>();
        s.add(0);
        ArrayList<Integer> u = new ArrayList<>();
        u.add(1);
        u.add(0);
        ArrayList<Integer> v = new ArrayList<>();
        v.add(0);
        v.add(1);
        int i = 1;
        while (g.get(i) != 0) {
            s.add(Math.floorDiv(g.get(i - 1), g.get(i)));
            g.add(Math.floorMod(g.get(i - 1), g.get(i)));
            u.add(u.get(i - 1) - (u.get(i) * s.get(i)));
            v.add(v.get(i - 1) - (v.get(i) * s.get(i)));
            i++;
        }
        printTable(i,g,s,u,v);
        String ggt=String.format("ggt(%d,%d)=%d",g.get(0),g.get(1),g.get(i-1));
        String bezout=String.format("(%d*%d)+(%d*%d)",u.get(i-1),g.get(0),v.get(i-1),g.get(1));
        System.out.println(ggt+" ="+bezout);
        return g.get(i - 1);
    }


    private static void printTable(int imax,ArrayList<Integer> g,ArrayList<Integer> s,ArrayList<Integer> u,ArrayList<Integer> v) {
        System.out.println(String.format("%5s%5s%5s%5s%5s","i","g","s","u","v"));
        for (int i = 1; i <= imax; i++) {
            System.out.println(String.format("%5d%5d%5d%5d%5d", i-1, g.get(i-1), s.get(i-1), u.get(i-1), v.get(i-1)));
        }
        System.out.println("\n\n");
    }


}