Chinese Remainder: Two Congruences

/*
 * Problem : Solve both congruences.
 * Input   : a, m, b, n.
 * Output  : The smallest x.
 * Approach: Inverse by extended Euclid
 * Time    : O(log n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 4: Extended Euclid finds the inverse of value modulo mod, when they are coprime.
        static long inverseMod(long value, long mod) {
            long oldR = value;
            long r = mod;
            long oldS = 1;
            long s = 0;
            while (r != 0) {
                long q = oldR / r;
                long t = oldR - q * r;
                oldR = r;
                r = t;
                t = oldS - q * s;
                oldS = s;
                s = t;
            }
            return ((oldS % mod) + mod) % mod;
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(int[] a) {
        long first = a[0];
        long m = a[1];
        long second = a[2];
        long n = a[3];
        // Step 1: Write x = first + k * m. Then x mod m = first for every k.
        // Step 2: Find k so that x mod n = second, which means k * m = second - first (mod n).
        long inverse = inverseMod(m % n, n);
        long diff = (((second - first) % n) + n) % n;
        long k = diff * inverse % n;
        // Step 3: The smallest x uses the smallest k.
        return first + k * m;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}