Primitive Root

I’m surprised that I haven’t come across this concept before but it was brought to my attention via one of the properties of 26701, my diurnal age on Wednesday, May 11th 2022. It is a member of OEIS A061334: primes with 22 as smallest positive primitive root. The initial members of this sequence are:

3361, 6841, 9439, 13681, 14449, 26591, 26701, 28729, 39373, 40609, 41161, 41521, 54601, 61031, 66071, 66301, 68041, 68881, 70729, 82021, 85201, 89209, 90217, 93601, 96769, 104831, 110161, 112921, 117721, 121631, 125329, 126001, 128521

The question that I naturally asked was: what is a primitive root?

This YouTube video provides a good explanation and Figure 1 shows a screenshot of the author’s simplified definition:

Figure 1

Using this definition, it’s easy enough to show that 22 is the smallest primitive root of 26701 (permalink plus see SageMathCell verification below).

xxxxxxxxxx

 

1

p=26701

2

for n in [2..(p-1)]:

3

    S=[]

4

    for x in [1..(p-1)]:

5

        y=n^x%p

6

        S.append(y)

7

    if len(S)==len(Set(S)):

8

        print("smallest primitive root of",p,"is",n)

9

        print("there is a total of",euler_phi(euler_phi(p)),"primitive roots")

10

        break

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Some other larger primitive roots are 26, 29, 38, 47, 59 and 66. In fact, as the calculation above shows, there are a total of $\phi (\phi(26701)=7040$ primitive roots where $\phi$ is the euler totient function. This YouTube link to Michael Penn’s video explains why this is so. What is less apparent however, is the usefulness of finding the primitive root of a prime number. I should investigate this further at some point but I’m still on holidays and my mind in holiday mode.