### Question:

Given a prime number n and mod k number find out whether provided prime number n is having a primitive root mod k

### Answer

A **primitive root** mod n is an integer g such that every integer relatively prime to n is congruent to a power of g mod n. That is, the integer g is a primitive root (mod n) if for every number a relatively prime to n there is an integer *z* such that

a = (g^{z} (mod n))

for example:

2 is a primitive root mod 5, because for every number a relatively prime to 5

- 2
^{1}= 2, 2 (mod 5) = 1, so 2^{1}= 2 - 2
^{2}= 4, 4 (mod 5) = 2, so 2^{2}= 4 - 2
^{3}= 8, 8 (mod 5) = 3, so 2^{1}= 3 - 2
^{4}= 16, 16 (mod 5) = 1, so 2^{4}= 1

For every integer relatively prime to 5, there is a power of 2 that is consistent.