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¹ = 2,  2 (mod 5) = 1, so 2¹ = 2
• 2² = 4,  4 (mod 5) = 2, so 2² = 4
• 2³ = 8,  8 (mod 5) = 3, so 2¹ = 3
• 2⁴ = 16,  16 (mod 5) = 1, so 2⁴ = 1

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