Primitive Roots

By Liona Fan-Chiang

 

We had turned to the tables, hoping to find the sought principle expressed through a different medium, but found much more. With the new tools derived from the previous inductive analysis, we can re-approach the geometric representation of the modulus from a higher standpoint.

By using our table of residues for the real number 17, many complicated investigations involving the complex modulus can be significantly aided, reducing tedium down to a minimum, such that the state of experimentation is freely allowed to consume the creative mind. For example, consider the initial investigations on biquadratic residues, where the character of each residue was found by physically squaring each complex number within the modulus. As we saw then, even a small modulus, such as modulus 29, had already begun to imitate a football coach's playbook.
modulus 29
In this diagram, the arrows indicate the action of squaring, leading from the residue, to the residue that is congruent to the the square of that residue. The quadratic residue pointed at, is then marked with a medium sized colored dot. As a result, the arrows leading from those then point to biquadratic residues.

 

However, with the tables in hand, and complex numbers in mind, the biquadratic characteristics of each modulus can be obtained with ease. One method is simply to look down the second and fourth column, immediately obtaining the quadratic and biquadratic residues respectively.

modulus 29 as a table
On the left hand side is the first 6 columns of a table constructed for modulus 29. On the right, is one representation of modulus 29 on the complex plane. If complex number is labeled by its congruent real number residue, the second and fourth column of the table can be used to determine which complex numbers are biquadratic, quadratic, or non- residues.
Further, not only the biquadratic residues, but the cubic, quintic, and even heptic residues can be easily obtained from the tables.
Therefore, let us take advantage of the new-found capability, and assume an investigation of a higher degree.
What kind of characteristics can we uncover about the modulus, if we take into account, not only square and biquadratic numbers, but rather all the powers that are represented in the table? For example, what type of mapping would result from following one row of the table, which corresponds to a single residue and its successive powers, across.
Let us begin with the primitive roots.
An Advanced Look at Primitive Roots
Although the primitive roots may have appeared to be the least important, or maybe even the least interesting, of the four types of residues (biquadratic residues, quadratic residues, primitive roots and quadratic non-residues), we will soon see that, those residues which most aid in illuminating the personality of each modulus is that modulus' primitive roots. Ironically, the numbers which tell us the most about the modulus are the those which are most incongruent to the respective modulus.1
As noted above, the defining characteristic a primitive root, is that when taken to every power successively, for example 3, 32, 33, 34¼3p, the residues which each value is congruent to, never repeat. Thereby, every residue of the modulus will be traversed by the primitive root and those residues congruent to that root raised to successive powers, repeating only at hp º h, where h is used here to indicate any primitive root, and p, the modulus. As we shall see, this unique property of primitive roots will provide a useful shortcut for finding the biquadratic character of a modulus.
Since we are familiar with modulus 17 from the last section, we shall begin with modulus 17 as an illustration. Follow a primitive root, such as 3, through its entire period. As before, you could physically multiply the complex number by itself, then multiply its product by that same primitive root again, and so on.

In contrast, you could look at the table, find 3 in the left column, and read along the row.
 modlus 17 as table
The arrows in the bottom right square follow the numbers shown in the left square, numbers which are congruent with the corresponding complex number residue, in succession, according to the table, beginning with the red dot, which marks the primitive root 3. Notice that every residue is traversed.
By following the locus traced out by the primitive root and the residues congruent to that primitive root taken to successive powers, we can track the "pathway" that 3 traverses in its conquest. (For the sake of brevity, the following illustrated action will simply be referred as "the pathway of the primitive root 3", or "the pathway of the biquadratic residue 4" etc.) Every second number in the path of 3, and all other primitive roots, will be congruent to a quadratic residue, while every fourth will also be a biquadratic residue. Thus, merely following one primitive root presents us with the biquadratic character of the entire modulus!

As before, the large circles represent biquadratic residues, the medium circles represent quadratic residues which are not biquadratic residues, and the smallest respresent primitive roots.
To continue this investigation, find the other primitive roots of modulus 17, and follow their pathways as they traverse their entire period. If you do not already know which residues those are, either look for them in the diagram constructed by following the pathway of 3 above, or again, turn to our table of residues for 17, which provides us with the the most direct method for identifying primitive roots. As mentioned already, the period for a primitive root is p-1. At hp-1, the congruent residue is 1, as it is with all other residues. This means, that at half of the period of any primitive root, h, i.e. under the column [(p-1)/2], h[(p-1)/2] º -1. Glancing at the table for modulus 17, we find that 3, 5, 6, 7, 10, 11, 12, 14, are all primitive roots.
Here is an illustration of each of the pathways of all of the primitive roots of modulus 17 in one of the two complex representations of that modulus:

Shown above are all the primitive roots of modulus 17 as they each traverse their individual pathways.
Notice that none of them are the same, and yet none of them are entirely uniquely different from all the rest.
For example, the pathways of 3 (-1+i in the following animation) and 6 (2+i) look exactly the same, yet if you were to follow their pathways simultaneously, these paths would only coincide once, at the residue -1, bouncing off each other before continuing on their separate ways.


10 
13 
15 
11 
16 
14 
12 
1
12 
14 
16 
11 
15 
13 
10 
1
In fact, upon observing the pathways taken by all of the primitive roots, there is more cause for wonder, as all of the primitive roots have a reflective friend. Must this always be the case?
For modulus p=17, the eight primitive roots can be arranged into four pairs of primitive roots that reflect each other, e.g., 3 and 6, 5 and 7, 10 and, and 11 and 14. Thus, although there are eight pathways traversed by each of the eight primitive roots, there are only four different patterns produced by the four matching pairs.
Complement pairs of residues for modulus 17
Why must this reflective property exist?
Look now at the corresponding modulus on the complex plane, i.e. 1+4i, which has corresponding pairs, 2+i and -1+i, 1+i and -1+2i, 1-2i and -1-i, and finally -2-i and 1-i, respectively. Observe that in the complex plane representation, there is, within a single cycle of an entire period of a primitive root, a quadruple periodicity. For example, take the residue 2+i.
residue 2+i in modulus 17
About which axes is the symmetry? Notice that when the pathway reaches i or -i, the pattern traversed seem to repeat; only this time, rotated 90 degrees, as though treating i, or -i as its new starting position, or equivalently, multiplying the path by i.

From this standpoint, look back again at the pairs of pathways generated by the primitive roots.
Notice that every primitive root always encounters i or -i at one quarter way through the pathway.
That is,
h[(p-1)/4] º i or -i
In fact, exactly half of these paths reach i first, while the other half reach -i first. Thus, half of the residues have a portion of their path rotated by i, while the other half rotates by -i! Although this property alone does not completely reveal the cause of both the occurrence of the reflected pairs, nor the reason the pathways take the unique ones they do, geometry again has unveiled an ordering that was hidden in the numbers.

Something else, however, has been unveiled. Reflect on the paradox we had encountered earlier, concerning the introduction of modulus 17 into the theory of classes.

complex modulus 17>
</center>

<div class=

The ambiguity of the division of the eight quadratic non-residues of modulus 17 into the classes B and D can finally be resolved. Previously, the act of squaring each residue resulted in a unique distribution into the four classes A, B, C, D for only a certain quality of number, which we learned in the last section, are of the form p=8n+5. However, when the same process was applied to a number of the form p=8n+1, e.g. modulus 17, no such distinction could be made. After some investigation of these quadratic non-residues, resulting from an extensive investigation of the tables, we finally arrive at the fact, that the primitive roots do indeed identify themselves with i or -i, but only when each primitive root was allowed to traverse their entire period of powers (or at least to the power of [(p-1)/4]). That is, their association could only be seen as a result of action of higher degrees than had previously been considered.

Following such a symmetric realization, a new question may now be posed: Do these pathways that each primitive root follows, when raised to successive powers, determine the characteristics of i, or does i dictate the particular pathways taken by each residue? This is a question to be examined after some experimentation.
For now, we return to some questions posed above: Are the pathways taken by these primitive roots uniquely determined. That is, why does the primitive root choose this path and not any other? There are only eight primitive roots and therefore only eight possible pathways, in this case. However, since pairs of residues share the same pathway, though in a different order, the number of possible variations are again halved. Why must pairs of pathways exist at all?
In preparation for an analysis of the answers to these questions, let us first draw out the remaining pathways, i.e. of periods of residues which are not primitive roots:
Quadratic Residues
Quadratic residues have a period of [(p-1)/2].
Biquadratic Residues
Biquadratic residues have a period less than [(p-1)/2].
Experiment in Causality2
The positing of such questions such as, "Why does the primitive root follow the particular pathway that it does?" "Why must there only be these particular pathways?" "Are there no other pathways that also reach the quadratic residues in the same order?" may trigger impatient responses such as, "What are you thinking, isn't it just following the numbers in the table? It is simply what happens when each number is taken to successive powers. It obviously could not follow another pathway."
For example, examine the period of the primitive root 2+i in the context of modulus 17. Every other number in the period is a quadratic residue, as would be expected, since every other number is the residue of that primitive root taken to an even power. Moreover, the quadratic residues which are reached, happen to follow the same series of quadratic residues as followed by the path taken by the number 2. In fact, the table of residues for 17 will reveal, that every other number in the rows of these two primitive roots are identical.
[TABLE]
The PR's are following the periods of the quadratic residues.
To proceed, therefore, let us take 2 and its associate numbers 2i, -2, -2i as an example. [ANIMATION]

Experimental modulus 17

 

Here the red lines represent the whole pathway animated above. The second part of the diagram distinguished between the four steps shows of the path being reflected symmetrically. So, the first of every four of the remaining three sets will be one of the associates of 2+i: -1+2i, -2-i, 1-2i. The second of each is a quadratic residues, namely 2, 2i, -2, -2i respectively. The third of each set is another primitive root, of different associated numbers -1-i, 1-i, 1+i, -1+i. The last set of numbers are again the quadratic residues (also, biquadratic residues from above), i, -1, -i, 1.

 

Therefore, the 4 sets are as follows.

2+i
®
2
®
-1-i
®
i
®
-1+2i
®
2i
®
1-i
®
-1
®
-2-i
®
-2
®
1+i
®
-i
®
1-2i
®
-2i
®
-1+i
®
1
What can we notice about these sets? First, from our above analysis of the different classes for modulus 1+4i, there are here in each quarter period, one number from each class, i.e, the first is a primitive root, then quadratic residue, next another primitive root, and finally a biquadratic residue.
Next, each set of four can be generated by rotating the prior set by 90 degrees, or, it can be said that the next four, are the residues of the first multiplied by i, as noted earlier.
Therefore, let's return to the question: Why do the PR's take the particular pathways that they do? What is the reason for it being the way it is and not some other way? Could there be any other possible period that fits the criteria we just saw?
I made up a couple of my own:3
Experimental modulus 17

2+i
®
2
®
1-i
®
i
®
-1+2i
®
2i
®
1+i
®
-1
®
-2-i
®
-2
®
-1+i
®
-i
®
1-2i
®
-2i
®
-1-i
®
1
And, how about this one:
Experimental modulus 17 for residue 2

2+i
®
2
®
-1+i
®
i
®
-1+2i
®
2i
®
-1-i
®
-1
®
-2-i
®
-2i
®
1-i
®
-i
®
1-2i
®
-2i
®
1+i
®
1
Ok, do these fit the criteria? Do they follow the same patterns, falling on a quadratic residue every second position, and a biquadratic residue at every fourth. Also, do they form a symmetrical pattern which generates, multiplied by i, generate the next successive quarter period? Yes. Well, wait a second here! What is going on? Why isn't the one I made sufficient to have been the pattern? By this experiment, it can be readily concluded, that the geometrical route which the primitive traverses is not the causal element in the determinating of the order of the residues in its particular pattern. Since we could construct our own, which follow the same character-istic steps, the geometry is simply a consequence of some higher cause; simply an effect.
But, even if the geometrical route is not the causal element, still, the question remains: Why do they take the specific course they do? For insight into this, perhaps we'll get some assistance by looking elsewhere. Just as we looked at the dependency of primitive roots on quadratic residues, let us examine the dependency of quadratic residues on biquadratic residues. What is the relationship that must be maintained in this case?
For every biquadratic residue, there are two quadratic residues, where every other number in their pathway is a shared biquadratic residue. Take for example biquadratic residue i for the case of modulus 17. 2 and -2 have the positions of the powers of i drawn out in every other number of their series.
Here is the period of 2:
Experimental modulus 17 residue 2
Here is the period of -2:
Experimental residue -2
Looking at these examples, is their any other pathway these quadratic residues could take? Try this out for yourself.
To conclude this part of the investigation, with respect to the complex number 1+4i, whose norm is of the form 8n+1, we can see that there are layers of causality within the residues. The primitive roots follow the quadratic residues. The quadratic residues, in turn, follow the series of biquadratic residues and thus are bound to a certain pathway. But, since the quadratic residues themselves are bound to follow the biquadratic residues, the primitive roots are really just a consequence of that which bounds and determines the characteristics of biquadratic residues.
What's the primary difference?
What do these unique properties of actions of residues tell us about moduli in general? For example, can they be used to shed any light on the discrepancy between the two apparent types of numbers which are representable on the complex plane: p=8n+1 and p=8n+5.
Remember that, geometrically, the two types of moduli had a difference in appearance, when the biquadratic character of each was shown:
p=8n+5 p=8n+1
Moduli which which have the norm p=8n+5 (left) vs. moduli with norm of the form p=8n+1 (right). The squares drawn inside each moduli are lines connecting associate sets in order to make the symmetry more apparent. For clarity, only some have been drawn in.
As mentioned above, primitive roots taken to successive powers encounter one of the roots of -1 at its first quarter period, i.e. h[(p-1)/4] º i or -i (h signifies any primitive root). However, what has also been examined, is that every fourth step of a primitive root's period is congruent to a biquadratic residue. Or inversely, the biquadratic residues are generated by every 4 steps along the pathway of a the primitive root. How do these two cycles, namely, the pathways of primitive roots intrinsic to the modulus, and the cycle of 4, characteristic of biquadratic residues, interact?
Let us look at some examples:
Primitive roots of modulus 5 Primitive roots of modulus 13
Here, the numbers represent the powers to which each residue is taken, i.e. for modulus 5: i, i2 º -1, i3 º -i, i4 º 1.
When looking at modulus 13, note the occurrence of coincidence between the progression of the primitive root, in this case 2, with the unities, i, -1, -i and finally 1.

Shown above is the primitive root and its 'pathway' through all the powers of 2. The complex modulus is colored by quarter period, while the modulus on the right follows along with numbers indicating the power that the primitive 2 is raised to. Notice that at every even power of 2 appears a quadratic residue, while at every residue that is congruent to 2 raised to a power that is a multiple of four appears a biquadratic residue.
Again, this conjunction occurs at every fourth step along the pathway of each primitive, namely at powers 3, 6, 9, and 12. However, the occurrence of biquadratic residues has a steady cycle of 4, appearing at powers 4, 8 and 12. The interaction of these two incommensurable cycles then creates the asymmetric mapping displayed above. This relationship holds in general for moduli which satisfy p-1=4n or p=4n+1. The result of this interplay is that i and -i, residues of a primitive root taken to an odd power, will be quadratic non-residues, while -1, a residue of a primitive root taken to an even power that is not divisible by 4, will be a quadratic residue.
Take a look at the modulus investigated above, modulus 17:
primitive roots of 17
Notice now, when the pattern of each quarter pathway repeats, this time rotated by 90 degrees, as noted earlier (indicated here with different colors), so does the periodicity defining the biquadratic residues. In other words, the quarter periods corresponding to primitive residues of powers 4, 8, 12, exactly coincide with the periodicity of the biquadratic residues! Stated in mathematical terms, [(p-1)/4]=4n, i.e. every modulus that has a norm p=16n+1 will look as symmetrical as modulus 17 does! Can you find the next prime number modulus that will be decorated as symmetrically as modulus 17?
One more: Modulus 41
primitive roots of 41
This time, a quarter of the whole period of the primitive root is 10, which is not a multiple of 4. However, half of the period, 20, is a multiple of 4! This gives [(p-1)/2]=4n, or p=8n+1. From this, we see that every modulus which satisfies p=8n+1, will be halfway symmetrical (as is modulus 41 above), and that -1 will always be a biquadratic residue, while i and -i, a residue of a primitive number that is taken to a power half of a multiple of 4, i.e. [4n/2]=even, will always be at least a quadratic residues. Now remember, moduli of the form p=8n+1 were only a subsection of all p=4n+1 moduli which have a complex plane representation. Therefore, the remaining division, namely moduli of the form p=8n+5 still have the property that was described above for moduli of the form p=4n+1, that is, -1 will always be a quadratic residue, but not a biquadratic residue.
Finally, in the end, the mystery of the apparent difference between the two types of moduli, p=8n+1 and p=8n+5, presented near the beginning of this investigation, has been partially resolved. Resolved not by looking at the geometry, nor a look purely at the numbers, but rather, both served only as a medium through which to reflect a process produced from a consideration of the interplay of cycles defined by two different principles: one by the nature of biquadratic numbers, and the other by the specific modulus being considered.
Wait, we are not done! Now that these two types of moduli have been distinguished from each other, what is the interaction of the resulting biquadratic character among the two types?


Footnotes:

1However, experienced Gauss fans should expect this, because primitive roots are Gauss' tools for dividing the circle into 17 parts!
2Experiment conducted by Michael Kirsch
3For the purpose emphasis on the symmetrical properties of the modulus, several of the following diagrams exclude the line connecting the unities 1, i, -1, and -i to the next residue in the pathway.


File translated from TEX by TTH, version 3.80.
On 06 Mar 2008, 16:16.