// Arup Guha
// 11/10/08
// Solution to CIS 3362 Homework #4 Problem #4: Primitive Roots.
#include <stdio.h>

int isPrime(int n);

int main() {
    
    int p, a;
    
    // Get the user input.
    printf("Enter a small prime number.\n");
    scanf("%d", &p);
    printf("Enter a number to check as a primitive root.\n");
    scanf("%d", &a);
    
    // Only run if p is prime.
    if (isPrime(p)) {
    
        int ans = a;
        int exp = 1;
        
        // Continue modular exponentiation until the answer is 1.
        while (ans != 1) {
            ans = (ans*a)%p;
            exp++;      
        }
        
        // If the smallest positive exponent such that a^exp = 1 mod p
        // is p-1, then the root is primitive.
        if (exp == p-1)
            printf("%d is a primitive root of prime %d.\n",a,p);
        else
            printf("%d is NOT a primitive root of prime %d.\n",a,p);
    }
    else
        printf("Sorry your number isn't prime.\n");
        
    system("PAUSE");
    return 0;
}

// Standard brute-force primality check.
int isPrime(int n) {
    
    // First prime is 2...
    if (n <= 1) return 0;
    
    int i;
    
    // Check each number for divisibility upto the square root of n.
    for (i=2; i*i<=n; i++)
        if (n%i == 0)
            return 0;
    return 1;
}