Power Residues and Primitive Roots

note

This is Lab 11 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

The least positive integer $h$ such that $a^{h} \equiv 1(\bmod m)$ is called the order of a modulo $m$. (This is Definition 2.6 on p. 97 of NZM.) The order of $a$ modulo $m$ exists and is finite if $\gcd (a, m)=1$; otherwise it is undefined.

Problem 1

Use PowerTab to determine the order of $a$ for each reduced residue class $a(\bmod 11)$. What orders occur? How many times do they occur? What is the least common multiple of these orders? Repeat this with $11$ replaced by some other prime number. Formulate conjectures regarding the situation for a general prime modulus. Compare your findings with Lemma 2.35 and Theorem 2.36 of NZM.

Problem 2

Suppose that $a$ has order $h$ modulo $m$. How is $h$ related to other numbers $k$ such that $a^{k} \equiv 1(\bmod m)$ ? Use PowerTab to investigate, for both prime and composite moduli, and then formulate a conjecture. Compare your conjecture with Lemma 2.31 of NZM. Euler's congruence asserts that $a^{\phi(m)} \equiv 1 (\bmod m)$ if $\gcd(a, m)=1$. What does this imply concerning the relation between the order of $a$ and $\phi(m)$ ? (See Corollary 2.32 of NZM.)

Problem 3

Suppose that $a$ has order $h$ modulo $m$. What is the order of $a^{k}$ modulo $m$ ? Experiment with several configurations, and formulate a conjecture. Compare with Lemma 2.33 of NZM.

Problem 4

Suppose that $a$ has order $h$ modulo $m$, and that $b$ has order $k$ modulo $m$. How large can the order of $a b$ be? How small? Use pairs taken from your work on Problem 1 above. If $\gcd (h, k)=1$, what is the order of $a b$ modulo $m$? Study some cases, and formulate a conjecture. Compare your findings with Lemma 2.34 of NZM.

Problem 5

Suppose that $a$ has order $h$ modulo $m$, that $a$ has order $k$ modulo $n$, and that $\gcd (m, n)=1$. What is the order of $a$ modulo $m n$ ? Try $a=2, m=7, n=11$. Try $a=2$, $m=5, n=17$. Try $a=17, m=7, n=11$. Formulate a conjecture (after considering additional examples, if necessary).

Problem 6

Use PowerTab to determine the order of $7(\bmod 101)$, and of $29(\bmod 101)$, and use WolframAlpha to determine the value of $7 \cdot 29(\bmod 101)$. Repeat this with $17 \cdot 75(\bmod 91)$, and with $233 \cdot 313(\bmod 424)$. Suppose that $a \cdot a' \equiv 1(\bmod m)$. Do you suspect a connection between the order of $a(\bmod m)$, and of $a' (\bmod m)$ ? Can you prove your conjecture? (This is found as Problem 14 at the end of $\S 2.8$ of NZM.)

Problem 7

The order of $a$ modulo $m$ can be determined by calculating $a, a^{2}, \ldots$ until the least $h$ is found such that $a^{h} \equiv 1 (\bmod m)$. However, since this $h$ may well be of size comparable to $m$, it is usually much faster to use the fact that $h \mid \phi(m)$. After factoring $\phi(m)$, we search for a minimal divisor $h$ of $\phi(m)$ with the property that $a^{h} \equiv 1(\bmod m)$. Note that if $a^{d} \equiv 1 (\bmod m)$, and if $q$ is a prime divisor of $d$, then either $a^{d / q} \equiv 1 (\bmod m)$, in which case we replace $d$ by $d / q$, or else $a^{d / q} \not \equiv 1(\bmod m)$, in which case the power of $q$ dividing $d$ is the same as the power of $q$ dividing the order of $a$. This technique is discussed on p. 100 of NZM.

To see how the order of 2 modulo 101 would be determined, Use OrderDem. To obtain the result without witnessing the calculation, use Order. Since the first step is to factor $m$ in order to calculate $\phi(m)$, some time may be saved by providing the value of $\phi(m)$, if this is known. For computing the order of 2 modulo 101, you can provide 100 as the third parameter (which is optional). The economy here can be quite noticeable: if the modulus is a 17 -digit prime $p$, then it will be much faster to tell the machine that $\phi(p)=p-1$, rather than let the machine try to factor $p$ by trial division. When the values $a, m, c$ are given to the program Order, it is not necessary that $c$ actually be the value of $\phi(m)$. All that is required is that $a^{c} \equiv 1$ $(\bmod m)$. What happens if $c$ does not meet this condition? Try using Order with input 2 101 and 35.

Problem 8

The program PrimRoot finds the least positive primitive root of a prime number $p$, by calculating the order of $a$ for $a=2,3, \ldots$ until an $a$ is found of order $p-1$. Usually this does not take very many trials. Find the least positive primitive root of several primes in this way. For example, use PrimRoot with input 1093. If you wish to find the least primitive root larger than a certain number $a$, enter it as the input $a$. By using the program PrimRoot repeatedly, find all the primitive roots of the prime $p=101$. How many primitive roots do you find? (Recall Theorem 2.36 of NZM.) What is the biggest gap found between consecutive primitive roots?

Problem 9

The program PrimRoot is not equipped to find primitive roots modulo $p^{k}$ when $k>1$, but the program Order is useful in this connection. Suppose that $g$ is a primitive root modulo $p$. Then $g$ is a primitive root modulo $p^{2}$ if and only if the order of $g$ modulo $p^{2}$ is $p(p-1)$. The only other possibility is that the order of $g$ modulo $p^{2}$ is $p-1$, in which case $g+p$ is a primitive root modulo $p^{2}$. (See the proof of Theorem 2.39 of NZM.) Is $2$ a primitive root modulo $101^{2}$ ? Show that $14$ is a primitive root of $29$ . Is it a primitive root of $29^{2}$ ? Find the least positive primitive root $g$ of the prime $40487$. Show that $g$ is not a primitive root modulo $40487^{2}$. (This is the least prime $p$ whose least positive primitive root fails to be a primitive root modulo $p^{2}$.)

Problem 10

To determine the order of a residue class $a$ modulo $m$, we need first a number $c$ such that $a^{c} \equiv 1 (\bmod m)$. We could take $c=\phi(m)$, but usually a smaller number will do. Let $\lambda(m)$ denote the least positive integer $c$ such that $a^{c} \equiv 1(\bmod m)$ for all reduced residue classes $a$. This is the Carmichael $\lambda$-function. Its values are determined by the following relations. $\lambda(1)=\lambda(2)=1 . \lambda(4)=2$. If $k \geq 2$ then $\lambda\left(2^{k}\right)=2^{k-2}$. If $p$ is an odd prime then $\lambda\left(p^{k}\right)=p^{k-1}(p-1)$. If $\gcd \left(m_{1}, m_{2}\right)=1$, then $\lambda\left(m_{1} m_{2}\right)=\mathrm{lcm}\left(\lambda\left(m_{1}\right), \lambda\left(m_{2}\right)\right)$.

Use the program Car to determine the value of $\lambda(100)$. Find a reduced residue class modulo 100 that has this maximal order.

Problem 11

For the programmer. Write a program that counts the number $N(x)$ of those primes $p$ not exceeding $x$ for which 2 is a primitive root of $p$. Would you conjecture that there are infinitely many such primes? Does it seem that this set of primes has positive asymptotic density among the set of all primes? That is, do you guess that $N(x) \sim c \pi(x)$ as $x \rightarrow \infty$ for some positive constant $c$ ? Gauss conjectured that there exist infinitely many such primes, and E. Artin suggested a particular asymptotic density. However, D. H. Lehmer, A note on primitive roots, Scripta Math. 26 (1963), 117-119 found that numerical evidence does not fit with Artin's conjecture. This led Artin to the realization that one aspect of the situation had been overlooked (see pp. viii, ix of Artin's Collected Works). A modified form of Artin's conjecture is now widely accepted as very likely to be true, especially since C. Hooley, On Artin's conjecture, J. Reine Angew. Math. 225 1967, 209-210, showed that the modified conjecture is a consequence of the Generalized Riemann Hypothesis. The conjectured constant is

$$c=\prod_{p}\left(1-\frac{1}{p(p-1)}\right)$$

where the product is taken over all primes. The number 2 can be replaced by any integer $a$, and the general conjecture is that there is a positive constant $c_{a}$ such that $N_{a}(x) \sim c_{a} \pi(x)$ as $x \rightarrow \infty$, provided that $a \neq-1, a \neq 0$, and that $a$ is not a perfect square.