Primitive Root

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

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.

Leave a Reply

Your email address will not be published. Required fields are marked *