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
|