public static int inverse(int a, int b) throws Exception {
    List<Integer> l1 =  new ArrayList<>();
    List<Integer> l2 = new ArrayList<>();
    l1.add(b);
    l1.add(a);

    while (true) {
        int r = l1.get(l1.size() - 2) % l1.get(l1.size() - 1);
        int q = l1.get(l1.size() - 2) / l1.get(l1.size() - 1);
        l1.add(r);
        l2.add(q);
        if (r == 0 || r == 1) {
            break;
        }
    }
    if (l1.get(l1.size() - 1) == 0) {
        throw new Exception("inverse does not exist");
    }

    int i, j, k, l;
    i = 1; j = 0; k = 0; l = 1;
    for (Integer n : l2) {
        int tmp1 = i - (n * k);
        int tmp2 = j - (n * l);
        i = k;
        j = l;
        k = tmp1;
        l = tmp2;
    }

    if (l < 0) {
        l += b;
    }
    return l;
}