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 = (gz (mod n))
for example:
2 is a primitive root mod 5, because for every number a relatively prime to 5
- 21 = 2, 2 (mod 5) = 1, so 21 = 2
- 22 = 4, 4 (mod 5) = 2, so 22 = 4
- 23 = 8, 8 (mod 5) = 3, so 21 = 3
- 24 = 16, 16 (mod 5) = 1, so 24 = 1
For every integer relatively prime to 5, there is a power of 2 that is consistent.