Extended Euclidean Theorem

import java.util.Scanner;

public class ExtendedEuclideanTheorem {

    static int[] gcd(int p, int q) {
        if (q == 0)
            return new int[] { p, 1, 0 };

        int[] vals = gcd(q, p % q);
        int d = vals[0];
        int a = vals[2];
        int b = vals[1] - (p / q) * vals[2];
        return new int[] { d, a, b };
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the p and q");
        int p = sc.nextInt();
        int q = sc.nextInt();
        int vals[] = gcd(p, q);
        System.out.println("gcd(" + p + ", " + q + ") = " + vals[0]);
        System.out.println(vals[1] + "(" + p + ") + " + vals[2] + "(" + q
                + ") = " + vals[0]);
    }
}

/*
OUTPUT:
Enter the p and q
65537
3511
gcd(65537, 3511) = 1
-1405(65537) + 26226(3511) = 1
*/