Finding Primitive roots of a prime number n using python

 

What is primitive root?

A number g is a primitive root modulo n if every number coprime to n is congruent to a power of g modulo n

 you can  learn more here: Primitive roots

For Example:

For example, 3 is a primitive root modulo 7, but not modulo 11, because

Modulo 7,

3^1≡3

3^2≡2

3^3≡6 (3^3=27mod7=6 )

3^4≡4

3^5≡5

3^6≡1(mod7)

you got all the possible results: 3,2,6,4,5,1

You can't get a 0, but 0 is not coprime to 7, so it's not a problem. Hence 3 is a primitive root modulo 7.

Whereas, modulo 11,

3^1≡3,

3^2≡9,

3^3≡5,

3^4≡4,

3^5≡1

3^6≡3(mod11)

And modulo 11, you only got the possible values 3,9,5,4 and the sequence start’s repeating after 3^6, so you will never get a 3^k≡2

 

I have implemented a code in python that finds all Primitive roots  of a number😀

 

Python code:

print("##################################")
print("######Primitive roots finder######")
print("##################################")
n = int(input("Enter the Prime number to find Primitive roots = "))
#l is a list that keeps all the outputs of each round 
#ex : for i=3 n=7 in loop  l=[3,2,6,4,5,1]
l=[]
#check() functions checks if there is any duplicate in l(list)
#if it finds a duplicate then it's not a primitive root
#ex: i=3 n=11 in loop l=[3,9,5,4,1,3] 3 has been repeated so, it's a primitive root
def check(n,l):
    out = []
    for i in l:
        if i not in out:
            out.append(i)
        else:
            return False
    out.clear()        
    return True
tot = 0
roots = []
for i in range(1,n):
    for j in range(1,n):
        t = (pow(i,j))%n
        print("{}^{} mod {} = {}".format(i,j,n,t))
        l.append(t)
    if(check(n,l)):
        tot = tot + 1
        roots.append(i)
    l.clear()
    print()           
print("Primitive roots are ",roots)

 

Output:

Comment if there's any error and also share it with your friends.😄

さよなら😛