Modular Inverse (Extended Euclid)

/*
 * Problem : Find the modular inverse of a modulo m.
 * Input   : Two integers a and m.
 * Output  : The inverse or -1.
 * Approach: Use extended Euclid.
 * Time    : O(log m)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long a, long b) {
        // Step 1: If m is 1 there is no useful inverse.
        if (b <= 1) {
            return -1;
        }

        // Step 2: Extended Euclid. We keep two rows: (remainder, coefficient of a).
        long oldRemainder = a % b;
        long remainder = b;
        long oldCoefficient = 1;
        long coefficient = 0;

        // Step 3: Run the Euclid steps. In each step we also update the coefficients.
        while (remainder != 0) {
            long quotient = oldRemainder / remainder;

            long nextRemainder = oldRemainder - quotient * remainder;
            oldRemainder = remainder;
            remainder = nextRemainder;

            long nextCoefficient = oldCoefficient - quotient * coefficient;
            oldCoefficient = coefficient;
            coefficient = nextCoefficient;
        }

        // Step 4: The last non-zero remainder is the gcd. If it is not 1, there is no inverse.
        if (oldRemainder != 1) {
            return -1;
        }

        // Step 5: Make the coefficient positive and smaller than m.
        return ((oldCoefficient % b) + b) % b;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}