// Show that a base raised to a prime minus 1 is 1 modulo the prime
// Example:  primes 44 673
// 251303535585582656914981949477708997481074178199173321938981419023985905
// 703370182976843789340283911227412204630824679337204303527653826289076014
// 634935359564668713996166247675241204398862120325089780531817761061582204
// 587017693645688392510007793661164938500556610471525079706799174756526133
// 161115289648386455627151373763356196494333480332485264099345903677547943
// 515450012326181712286455875033910999402109135489106725010328293678719720
// 962619672930022515990699526422948060349488092154581099483748556930687804
// 496081710936436303340259713599204540653593390450009220611324716761952836
// 087598079769495923017394681974243774425314925407266122780272240290865181
// 462507043655059673767514324499405184224478745317482559660011624280736128
// 268427214263309087324771830001108468484026275974683495082383737107646107
// 282353206233846867391891817475568603293397009582430937855303216683858018
// 024949451043121304981456580603500409358016339571943507058117183789076502
// 941529723524939316076345950082955201449614469996241665146211369932186869
// 508328657595446108792912692471015919454508846641542150528809412419039057
// 4645822456663938261057536 1
// 
// The big number is 44 raised to the power 672 and the 1 is the big number
// mod 673.
#include <iostream>
#include "bigint.h"
#include "power.h"
using namespace std;

int main (int argc, char **argv) {
   if (argc != 3) {
      cerr << "Usage: " << argv[0] << " <base> <prime>\n";
      cerr << "  function: show <base>^(<prime>-1) = 1 mod <prime>\n";
      exit(0);
   }
   int base = atoi(argv[1]);
   int prime = atoi(argv[2]);
   Power *p = new Power();
   BigInt *res = p->pow(base, prime-1);
   BigInt *ops = res->modBigInt(new BigInt(prime));
   cout << res << " " << ops << "\n";
}