Roots

BACKGROUND:


1) --------------


The number gcd(A,B) is the largest positive integer that divides both A and B
with a remainder of zero.
(greatest comon divisor)



Example:


gcd(2, 4) = 2
gcd(1, 6) = 1
gcd(5, 6) = 1
gcd(4, 6) = 2


2) --------------


If N is a positive integer, then phi(N) is defined as follows


phi(1) = 1


if N > 1, then phi(N) is the number of integers between 1 and N, inclusive,
that are relatively prime to N.


A and B are relatively prime if and only if gcd(A,B) = 1, where gcd is the
greatest common divisor function.


Example:


phi(4) = 2, since gcd(1,4) = 1 and gcd(3,4) = 1
phi(7) = 6, since gcd(1,7) = gcd(2,7) = ... = gcd(6,7) = 1



3) --------------


A number X is a primitive root of N if gcd(X,N) = 1 and the values:


X, X ^ 2, X ^ 3, ... , X ^ phi(N)


all have distinct remainders when divided by N.


(X mod N, or X % N is the remainder when X is divided by N)


Example 1:



isPrimitiveRoot(3, 4)  returns 1


phi(4) = 2


3 is a primitive root because gcd(3, 4) = 1 and


3 ^ 1 mod 4 = 3
3 ^ 2 mod 4 = 1

and the two values are distinct



Example 2:



isPrimitiveRoot(2, 5) returns 1


phi(5) = 4, gcd(2,5) = 1, and


2 ^ 1 mod 5 = 2
2 ^ 2 mod 5 = 4
2 ^ 3 mod 5 = 3
2 ^ phi(5) mod 5 = 1


are all distinct, so 2 is a primitive root of 5.




Example 3:


isPrimitiveRoot(4, 8) returns 0 because gcd(4,8) = 4



Example 4:


isPrimitiveRoot (2, 7) returns 0 because


phi(7) = 6


2 ^ 1 mod 7 = 2
2 ^ 2 mod 7 = 4
2 ^ 3 mod 7 = 1
2 ^ 4 mod 7 = 2


and 2 ^ 4 = 2 ^ 1 (mod 7)






Class name: Roots
Method name: isPrimitiveRoot
Parameters: int, int
Returns: int


Implement a class Roots, which has a method isPrimitiveRoot.


Method signature:  int isPrimitiveRoot(int X, int N) (be sure your method is
declared public)


*X is between 1 and 10, inclusive (1 <= X <= 10)
*X is between 1 and N minus 1  (N - 1), inclusive (1 <= X <= N-1)



isPrimitiveRoot returns 1 if X is a primitive root of N or 0 if X is not a
primitive of root