// ModGCD.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* Tests of GCD, modulo, Chinese remainder, and related ops.

   Usage:
     > compile ModGCD.java
     > run ModGCD <a> <b>
   e.g.
     > run ModGCD 197 203

 */

import java.math.*;
import java.util.*;

import de.tilman_neumann.jml.modular.ModularPower;


public class ModGCD
{

  public static void main(String[] args)
  {
    if (args.length != 2) {
      System.out.println("Usage: run ModGCD <a> <b>");
      return;
    }
    int a = Nut.parseInt(args[0]);
    int b = Nut.parseInt(args[1]);

    if ((a <= 0) || (b <= 0)) {
      System.out.println("Both the integers must be > 0");
      return;
    }

    if (a < b) {
      System.out.println("Swapping the integers, so the first is bigger");
      int temp = a;
      a = b;
      b = temp;
    }

    // ------------------- GCD and related ops ------------------

    System.out.println("a = " + a + ", b = " + b);
    System.out.println("gcd(a,b): " + Nut.gcd(a, b));
    System.out.println("lcm(a,b): " + Nut.lcm(a, b));

    long[] vals = Nut.egcd(a, b);    // vals == {gcd, j, k}
    System.out.println("egcd(a,b): " + vals[0] + 
                          " = (a * " + vals[1] + 
                         ") + (b * " + vals[2] + ")");


    // ------------------ mod and related ops --------------
    System.out.println();
    ModularPower mp = new ModularPower();
    System.out.println("modPow(4, 3, 5) = " + mp.modPow(4, 3, 5));
    System.out.println("modPow(7, 7, 10) + = " + mp.modPow(7, 7, 10));

    System.out.println("modInv(2,7) == " + 
                              Nut.modInv(2, 7));   // 4
        // Compute b such that ab mod n = 1


    ArrayList<Long> xs = Nut.modSolve(5, 9, 7);    
                                    // a, b, n
    System.out.println("modSolve(5, 9, 7) == " + 
                        Arrays.toString(xs.toArray()));
       // all x solutions to ax mod n = b;   gcd(a,n) | b


    BigInteger big1 = new BigInteger("321456");
    BigInteger big2 = new BigInteger("31711");
    System.out.println("\nBigInteger mod(" + big1 + ", " +
               big2 + " ) == " +  big1.mod(big2));   // 4346

    big1 = new BigInteger("23895");
    big2 = new BigInteger("14189");
    BigInteger exp = new BigInteger("15");
    System.out.println("\nBigInteger modPow " + big1 + "^" + exp + " % " +
                            big2 + " = " + big1.modPow(exp, big2));  // 344
 
    big1 = new BigInteger("8");
    big2 = new BigInteger("21");
    System.out.println("\nBigInteger modInverse " + big1 + "^(-1) % " +
                            big2 + " = " + big1.modInverse(big2));  // 8


    // -------------- Chinese remainder theorem --------------------
    // https://en.wikipedia.org/wiki/Chinese_remainder_theorem

    System.out.println();
    System.out.println("crt(6, 3, 11, 7) == " + 
                        Nut.crt(6, 3, 11, 7));   // 51
      // Chinese remainder theorem
      // find such that z mod 6 = 3  and z mod 11 = 7 

    System.out.println("crt(36, 12, 51, 5) == " + 
                        Nut.crt(36, 12, 51, 5));   // -1
      // find such that z mod 36 = 12  and z mod 51 = 5   
      // no soln since 36 and 51 are not relatively prime	


    System.out.println("\ncrt3(3, 2, 5, 1, 7, 6) == " + 
                  Nut.crt3(3, 2, 5, 1, 7, 6));   // 41
      // find such that z mod 3 = 2,  z mod 5 = 1,   
      // and z mod 7 = 6;

    System.out.println("crt3(8, 5, 14, 7, 35, 21) == " + 
                  Nut.crt3(8, 5, 14, 7, 35, 21));   // 21
      // find such that z mod 8 = 5,  z mod 14 = 7,   
      // and z mod 35 = 21;


    long[] res = Nut.linearDiophantine(3, 5, 19);  
                            // xa + yb = c; res == {x, y} or null
    if (res != null)
      System.out.println("\nlinearDiophantine(3, 5, 19) == " + 
                             res[0] + ", " + res[1]);   // 38, -19
  }	// end of main()



}  // end of ModGCD class