// Contoh Bab 14: teorema Fermat kecil dan invers modulo.
//
// Compile:  g++ -std=c++17 -O2 -o fermat exercises/14/03-fermat.cpp
// Jalankan: ./fermat

#include <iostream>
using namespace std;

long long pangkat_mod(long long a, long long b, long long m) {
    long long hasil = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) hasil = hasil * a % m;
        a = a * a % m;
        b /= 2;
    }
    return hasil;
}

int main() {
    long long p = 7;
    cout << "p = 7 (prima)\n";
    for (long long a = 1; a < p; a++)
        cout << "  " << a << "^6 mod 7 = " << pangkat_mod(a, p - 1, p) << "\n";

    long long q = 12;                      // bukan prima
    cout << "q = 12 (bukan prima)\n";
    for (long long a = 1; a < 6; a++)
        cout << "  " << a << "^11 mod 12 = " << pangkat_mod(a, q - 1, q) << "\n";

    // Invers modulo untuk membagi.
    long long P = 1000000007;
    long long x = 10, y = 3;
    long long inv = pangkat_mod(y, P - 2, P);
    long long bagi = x % P * inv % P;

    cout << "(10 / 3) mod P     = " << bagi << "\n";
    cout << "diperiksa: " << bagi << " * 3 mod P = " << bagi * 3 % P << "\n";
    return 0;
}