/** * Euclidean algorithm to find the greatest common divisor (gcd) * @param a * @param b * @return */ public static int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); } /** * Extended euclidean algorithm to find the greatest common divisor (gcd) * @param a * @param b * @return */ public static int[] egcd(int a, int b) { int x = 0; int y = 1; int u = 1; int v = 0; while(b != 0) { int buffer = b; int q = a / b; b = a % b; a = buffer; buffer = x; x = u - q* x; u = buffer; buffer = y; y = v - q*y; v = buffer; } return new int[]{u,v,a}; }