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. 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. 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. An Advanced Look at Primitive Roots^{1}
^{2}, 3^{3}, 3^{4}¼3^{p}, 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 h^{p} º 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.
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. 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. ^{p-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.
Shown above are all the primitive roots of modulus 17 as they each traverse their individual pathways.
all of the primitive roots have a reflective friend. Must this always be the case?
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,
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. 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 have a period of [(p-1)/2].
Biquadratic residues have a period less than [(p-1)/2].
Experiment in Causality^{2}
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.
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]
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.
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}
And, how about this one:
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:
Here is the period of -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:
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:
Here, the numbers represent the powers to which each residue is taken, i.e. for modulus 5: i, i ^{2} º -1, i^{3} º -i, i^{4} º 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:
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
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:^{1}However, experienced Gauss fans should expect this, because primitive roots are Gauss' tools for dividing the circle into 17 parts!
^{2}Experiment conducted by Michael Kirsch
^{3}For 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. |