// オイラーの定理の確認
// m^(p-1)(q-1) = 1 mod pq for prime p,q
import java.math.BigInteger;
import java.util.Random;
public class Euler
{ public static void main (String[] args) 
    { int bit=30;
      BigInteger n, m, p1, q1, f, t;
      BigInteger One = new BigInteger("1");
      BigInteger p = new BigInteger(bit, 20, new Random());
      BigInteger q = new BigInteger(bit, 20, new Random());
      System.out.println("p="+p.toString()+" q="+q.toString());
      m = One;
      n  = p.multiply(q);
      p1 = p.subtract(One);
      q1 = q.subtract(One);
      f  = p1.multiply(q1);
      for (int k=2; k<=10; k++)
        { m = m.add(One);
//  t=m^(f) mod n, n=p*q, f=(p-1)*(q-1)
          t = m.modPow(f, n);
          System.out.println("m="+m.toString()+"  t="+t.toString());       
        }
    }
}