Primitive roots

The powers of a number modulo a prime always come back to 1, but often early. Is there always a number whose powers visit every nonzero remainder first, and what does such a number let us do?

Where you are 2 in Congruences

Why this exists

Fermat’s little theorem says that if p is prime and p \nmid a, then a^{p-1} \equiv 1 \pmod{p}, so the powers of a modulo p cycle with a period dividing p - 1. Modulo 11 the powers of 3 return to 1 after five steps, while the powers of 2 pass through all ten nonzero remainders first. A base of the second kind writes every nonzero remainder as one of its powers, so multiplying remainders becomes adding exponents, as with logarithms. This lesson asks whether such a base exists for every prime, and for which other moduli.

Definition

Let n \ge 1 and \gcd(a, n) = 1. By Euler’s theorem (Theorem 7 of Fermat's little theorem), a^{\varphi(n)} \equiv 1 \pmod{n}. The order of a modulo n, written \operatorname{ord}_n(a), is the least positive integer t with a^t \equiv 1 \pmod{n}.

A primitive root modulo n is an integer g with \gcd(g, n) = 1 and \operatorname{ord}_n(g) = \varphi(n), the largest order Euler’s theorem allows.

If g is a primitive root modulo n and \gcd(a, n) = 1, the index \operatorname{ind}_g(a) is the unique integer k with 0 \le k < \varphi(n) and g^k \equiv a \pmod{n} (Corollary 3 shows that it exists and is unique). It is also called the discrete logarithm of a.

The residues coprime to n form the group of units modulo n, \mathbb{Z}_n^{\times} (algebra texts write \mathbb{Z}_n as \mathbb{Z}/n\mathbb{Z}). A primitive root is a generator, and one exists exactly when \mathbb{Z}_n^{\times} is a cyclic group.

Intuition

Place 1, 2, \dots, 10 around a circle and follow multiplication by 2 modulo 11: 1 \to 2 \to 4 \to 8 \to 5 \to 10 \to 9 \to 7 \to 3 \to 6 \to 1. The path touches all ten points, so 2 is a primitive root. Multiplication by 3 gives 1 \to 3 \to 9 \to 5 \to 4 \to 1, a loop of five, so \operatorname{ord}_{11}(3) = 5.

1 2 3 4 5 6 7 8 9 10
2^k \bmod 11
1 2 3 4 5 6 7 8 9 10
3^k \bmod 11
Figure 1Modulo 11, the powers of 2 visit every nonzero remainder before returning to 1; the powers of 3 close up after five steps.

Since 2^8 = 256 = 23 \cdot 11 + 3, stepping by 3 is stepping eight places around the loop of 2, which returns after 10 / \gcd(10, 8) = 5 steps: one primitive root gives every order. Existence is the hard part; it rests on Theorems 5 and 6 below.

Results

Throughout, n \ge 1, \gcd(a, n) = 1 and t = \operatorname{ord}_n(a).

Theorem 1 (orders). (a) For a whole number k, a^k \equiv 1 \pmod{n} if and only if t \mid k. (b) t \mid \varphi(n). (c) For whole numbers i, j, a^i \equiv a^j \pmod{n} if and only if i \equiv j \pmod{t}; so 1, a, \dots, a^{t-1} are pairwise incongruent.

Theorem 2 (order of a power). For every whole number u, \operatorname{ord}_n(a^u) = \dfrac{t}{\gcd(t, u)}.

Corollary 3 (powers of a primitive root). Let g be a primitive root modulo n. Then g^0, g^1, \dots, g^{\varphi(n)-1} are congruent, in some order, to the \varphi(n) integers from 1 to n coprime to n. For a whole number k, g^k is a primitive root if and only if \gcd(k, \varphi(n)) = 1. So a modulus with one primitive root has exactly \varphi(\varphi(n)) of them, counted modulo n.

Theorem 4 (a test). Let n \ge 2 and \gcd(g, n) = 1. Then g is a primitive root modulo n if and only if g^{\varphi(n)/q} \not\equiv 1 \pmod{n} for every prime q dividing \varphi(n).

Theorem 5 (Lagrange’s theorem on roots). Let p be prime and f(x) = c_k x^k + \dots + c_1 x + c_0 have integer coefficients, k \ge 0 and p \nmid c_k. Then f(x) \equiv 0 \pmod{p} has at most k solutions among 0, 1, \dots, p - 1.

Theorem 6 (divisor sum of \varphi). For every positive integer n, \sum_{d \mid n} \varphi(d) = n, the sum running over the positive divisors d of n.

Theorem 7 (primitive roots modulo a prime). Let p be prime. For each positive divisor d of p - 1, exactly \varphi(d) of 1, \dots, p - 1 have order d modulo p. In particular p has a primitive root, and exactly \varphi(p - 1) of them.

Theorem 8 (indices). Let g be a primitive root modulo n and \gcd(a, n) = \gcd(b, n) = 1. Then \operatorname{ind}_g(ab) \equiv \operatorname{ind}_g(a) + \operatorname{ind}_g(b) and \operatorname{ind}_g(a^k) \equiv k \operatorname{ind}_g(a), modulo \varphi(n), for every whole number k. If n = p is an odd prime, \displaystyle \operatorname{ind}_g(-1) = \frac{p-1}{2}.

Theorem 9 (which moduli). A primitive root modulo n exists if and only if n is 1, 2, 4, p^k or 2p^k, where p is an odd prime and k \ge 1.

Artin’s conjecture (stated, not proved). If an integer a is neither -1 nor a perfect square, then a is a primitive root modulo infinitely many primes. Hooley proved it in 1967 assuming the generalized Riemann hypothesis; without that hypothesis no single such a is known to satisfy it.

Why it is true

Proof of Theorem 1. Part (a) is proved in Powers modulo n: the exponents giving 1 are exactly the multiples of the order. Part (b) follows from (a) and Euler’s theorem. For (c), say i \ge j. A prime dividing a^j and n would divide a (Euclid’s lemma), so a^j is coprime to n and may be canceled (Modular inverses and linear congruences): a^i \equiv a^j if and only if a^{i-j} \equiv 1, that is, by (a), t \mid i - j. \square

Proof of Theorem 2. Let d = \gcd(t, u), t = dt' and u = du'. Then \gcd(t', u') = 1, since a common divisor c > 1 would make dc a common divisor of t and u. By Theorem 1(a), (a^u)^k \equiv 1 if and only if t \mid uk, that is, t' \mid u'k, and by the coprime factor lemma (Bezout's identity and the extended Euclidean algorithm) that holds if and only if t' \mid k. The least positive such k is t/d. \square

Proof of Corollary 3. Each g^k is coprime to n, so it is congruent to one of the \varphi(n) integers from 1 to n coprime to n. By Theorem 1(c), g^0, \dots, g^{\varphi(n)-1} are pairwise incongruent, so they fill all those classes. By Theorem 2, \operatorname{ord}_n(g^k) = \varphi(n)/\gcd(\varphi(n), k), which is \varphi(n) exactly when the gcd is 1; and the k with 0 \le k < \varphi(n) coprime to \varphi(n) number \varphi(\varphi(n)). \square

Proof of Theorem 4. If g is a primitive root, its order \varphi(n) does not divide the smaller number \varphi(n)/q, so g^{\varphi(n)/q} \not\equiv 1 by Theorem 1(a). Conversely, if t = \operatorname{ord}_n(g) < \varphi(n), then \varphi(n) = tm with m > 1 (Theorem 1(b)). For a prime q \mid m, \varphi(n)/q = t \cdot (m/q) is a multiple of t, so g^{\varphi(n)/q} \equiv 1. \square

Proof of Theorem 5. Induction on k. If k = 0, then f = c_0 with p \nmid c_0, and there is no solution. Let k \ge 1, assume the result for degree k - 1, and let r be a root (if there is none, we are done). For i \ge 1,

\begin{aligned} x^i - r^i = (x - r)(x^{i-1} &+ x^{i-2} r \\ &+ \dots + r^{i-1}), \end{aligned}

so f(x) - f(r) = \sum_{i=1}^{k} c_i (x^i - r^i) = (x - r) h(x) with h of integer coefficients, degree k - 1 and leading coefficient c_k. If s \not\equiv r is another root, then (s - r) h(s) = f(s) - f(r) \equiv 0, and p \nmid s - r, so p \mid h(s) by Euclid’s lemma. So the other roots are roots of h, at most k - 1 of them by hypothesis. \square

Primality was used only in Euclid’s lemma. Modulo 8, x^2 - 1 \equiv 0 has four solutions 1, 3, 5, 7, because (3 - 1)(3 + 1) = 8 is 0 with neither factor 0.

Proof of Theorem 6. Sort m = 1, \dots, n by e = \gcd(m, n). The m with \gcd(m, n) = e are m = em' with 1 \le m' \le n/e and \gcd(m', n/e) = 1, because \gcd(em', e \cdot n/e) = e \gcd(m', n/e): the gcd is the least positive combination (Bezout's identity and the extended Euclidean algorithm), and the combinations of em' and e \cdot n/e are e times those of m' and n/e. So there are \varphi(n/e) of them and n = \sum_{e \mid n} \varphi(n/e); as e runs over the divisors of n, so does d = n/e. \square

Proof of Theorem 7. For d \mid p - 1 let \psi(d) count the a \in \{1, \dots, p-1\} of order d. Every order divides \varphi(p) = p - 1, so \sum_{d \mid p-1} \psi(d) = p - 1. If \psi(d) > 0, pick a of order d. Then 1, a, \dots, a^{d-1} are d incongruent roots of x^d - 1 (Theorem 1(c), and (a^i)^d = (a^d)^i \equiv 1), so by Theorem 5 they are all its roots. Every element of order d is a root, hence some a^i with 0 \le i < d, and by Theorem 2 it has order d exactly when \gcd(i, d) = 1. So \psi(d) \le \varphi(d) in every case, and by Theorem 6

p - 1 = \sum_{d \mid p-1} \psi(d) \le \sum_{d \mid p-1} \varphi(d) = p - 1.

Equality forces \psi(d) = \varphi(d) for every d, and \psi(p-1) = \varphi(p-1) \ge 1. \square

Proof of Theorem 8. g^{\operatorname{ind}(a) + \operatorname{ind}(b)} \equiv ab \equiv g^{\operatorname{ind}(ab)}, so the exponents agree modulo \varphi(n) by Theorem 1(c); likewise for a^k. For an odd prime p, x = g^{(p-1)/2} has x^2 \equiv 1, so p \mid (x - 1)(x + 1) and x \equiv \pm 1 by Euclid’s lemma; x \not\equiv 1 since \displaystyle 0 < \frac{p-1}{2} < \operatorname{ord}_p(g). \square

Proof of Theorem 9. For m \ge 3, \varphi(m) is even: the integers from 1 to m coprime to m pair off as x \leftrightarrow m - x, and x = m/2 is never among them, as \gcd(m/2, m) = m/2 > 1. For coprime u, v, \varphi(uv) = \varphi(u)\varphi(v): the bijection x \mapsto (x \bmod u, x \bmod v) of The Chinese remainder theorem (Theorem 4) matches the x coprime to uv with pairs coprime to u and to v, by Euclid’s lemma.

No primitive root. (i) n = 2^k, k \ge 3. Every odd a has a^{2^{k-2}} \equiv 1 \pmod{2^k}, by induction: for k = 3, a^2 - 1 = (a - 1)(a + 1) is a product of consecutive even numbers, one a multiple of 4; and squaring a^{2^{k-2}} = 1 + 2^k m gives 1 + 2^{k+1} m + 2^{2k} m^2 \equiv 1 \pmod{2^{k+1}}. So every order is below 2^{k-1} = \varphi(2^k). (ii) n = uv with \gcd(u, v) = 1 and u, v \ge 3. For \gcd(a, n) = 1 let e = \varphi(u)\varphi(v)/2 = \varphi(n)/2. Euler’s theorem gives a^e = (a^{\varphi(u)})^{\varphi(v)/2} \equiv 1 \pmod{u}, likewise modulo v, so uv \mid a^e - 1 by the coprime factor lemma. Every n off the list is one of these: write n = 2^j m with m odd. If m = 1, then j \ge 3. If m has two prime factors, take u = p^{v_p(n)} for one of them and v = n/u. If m = p^k, then j \ge 2; take u = 2^j and v = p^k.

Existence. 1 is a primitive root modulo 1 and 2, and 3 modulo 4. Modulo an odd prime power p^k one exists: the step from p to p^2 is Exercise 18, and the general case is proved in Ireland and Rosen, A Classical Introduction to Modern Number Theory, Chapter 4. Given a primitive root modulo p^k, it or it plus p^k is odd; call that one h. As h^s - 1 is even, 2p^k \mid h^s - 1 exactly when p^k \mid h^s - 1, so \operatorname{ord}_{2p^k}(h) = \varphi(p^k) = \varphi(2p^k). \square

Worked examples

Example 1

Orders modulo 19 by the test

Find \operatorname{ord}_{19}(7), and show that 2 is a primitive root modulo 19.

Solution

Here \varphi(19) = 18, so every order divides 18 (Theorem 1(b)). For 7: 7^2 = 49 \equiv 11 and 7^3 \equiv 77 = 4 \cdot 19 + 1, while 7 and 7^2 are not 1, so \operatorname{ord}_{19}(7) = 3.

For 2, Theorem 4 needs only the primes dividing 18 = 2 \cdot 3^2, that is, the exponents 9 and 6. Now 2^6 = 64 = 3 \cdot 19 + 7 and 2^9 = 2^6 \cdot 2^3 \equiv 56 \equiv -1. Neither is 1, so 2 is a primitive root. Also 7 \equiv 2^6, and Theorem 2 predicts \operatorname{ord}_{19}(7) = 18 / \gcd(18, 6) = 3, as found.

Example 2

Every primitive root modulo 19, and an index table

Find all primitive roots modulo 19 and all residues of order 3, and tabulate \operatorname{ind}_2(a) for a = 1, \dots, 18.

Solution

Doubling and reducing from 2^0 = 1 gives 2^k \bmod 19 for k = 0, 1, \dots, 17:

\begin{aligned} &1, 2, 4, 8, 16, 13, 7, 14, 9, \\ &18, 17, 15, 11, 3, 6, 12, 5, 10. \end{aligned}

By Corollary 3, 2^k is a primitive root exactly when \gcd(k, 18) = 1, so for k = 1, 5, 7, 11, 13, 17, and the primitive roots modulo 19 are 2, 3, 10, 13, 14, 15: \varphi(18) = 6 of them. By Theorem 2, 2^k has order 3 when \gcd(18, k) = 6, so k = 6, 12, giving 7 and 11. Reading the list backward gives the indices:

a\operatorname{ind}_2 aa\operatorname{ind}_2 a
101017
211112
3131215
42135
516147
6141511
76164
831710
98189
Example 3

Solving a power congruence with indices

Solve 5x^3 \equiv 2 \pmod{19}, and show that x^3 \equiv 5 \pmod{19} has no solution.

Solution

No solution has 19 \mid x, so write y = \operatorname{ind}_2(x). By Theorem 8, 5x^3 \equiv 2^{16 + 3y}, and by Theorem 1(c) this is \equiv 2^1 exactly when 16 + 3y \equiv 1 \pmod{18}. So 3y \equiv 3, that is, 18 \mid 3(y - 1), which holds exactly when 6 \mid y - 1: y = 1, 7, 13, and x \equiv 2^1, 2^7, 2^{13} \equiv 2, 14, 3. Check x = 3: 5 \cdot 27 = 135 = 7 \cdot 19 + 2. The solutions are x \equiv 2, 3, 14 \pmod{19}.

For x^3 \equiv 5 the same steps give 3y \equiv 16 \pmod{18}. Since 3 divides 3y and 18, it would divide 16. So no x works: 5 is not a cube modulo 19.

Example 4

A shared key over an open channel

Yuna and Kofi talk by walkie-talkie, and anyone on the channel hears every word. Openly they agree on p = 19 and g = 2. Yuna picks a secret a = 5 and announces 2^a \bmod 19; Kofi picks a secret b = 8 and announces 2^b \bmod 19. Each raises the number heard to their own secret exponent. Find the shared key, and say what a listener holding the index table learns.

Solution

Yuna announces 2^5 \equiv 13 and Kofi announces 2^8 \equiv 9. Yuna computes 9^5: 9^2 \equiv 5, 9^4 \equiv 25 \equiv 6, 9^5 \equiv 54 \equiv 16. Kofi computes 13^8: 13^2 = 169 \equiv -2, 13^4 \equiv 4, 13^8 \equiv 16. Both are 2^{ab} = 2^{40}, and 40 \equiv 4 \pmod{18} gives 2^4 = 16. The shared key is 16.

A listener hears 19, 2, 13 and 9. Finding a from 2^a \equiv 13 is finding \operatorname{ind}_2(13), which the table gives as 5, and then 9^5 is the key. For p with hundreds of digits no fast method for computing indices is known. This is the Diffie-Hellman key exchange, published in 1976.

Example 5

The period of a repeating decimal

Let p be a prime other than 2 and 5. Show that the decimal expansion of \displaystyle \frac{1}{p} repeats from the first digit with least period \operatorname{ord}_p(10), and find the periods of \displaystyle \frac{1}{17} and \displaystyle \frac{1}{73}.

Solution

Let t = \operatorname{ord}_p(10). Then 10^t - 1 = pN for a positive integer N < 10^t, and

\begin{aligned} \frac{1}{p} &= \frac{N}{10^t - 1} \\ &= N\left(10^{-t} + 10^{-2t} + \cdots\right). \end{aligned}

So the digits are the t digits of N, padded with leading zeros, repeated forever (Terminating and repeating decimals). Conversely, if the digits repeat with period s from the first, then \displaystyle \frac{10^s}{p} and \displaystyle \frac{1}{p} have the same digits after the point, so \displaystyle \frac{10^s - 1}{p} is an integer and t \mid s by Theorem 1(a). So t is the least period.

For p = 17, \varphi(17) = 16 = 2^4, so Theorem 4 needs only 10^8: 10^2 \equiv -2, 10^4 \equiv 4, 10^8 \equiv -1. So 10 is a primitive root modulo 17 and \displaystyle \frac{1}{17} = 0.\overline{0588235294117647} has period 16. For p = 73, 73 \cdot 137 = 10001, so 10^4 \equiv -1 and 10^8 \equiv 1; the order divides 8 but not 4, so it is 8, and \displaystyle \frac{1}{73} = 0.\overline{01369863} has period 8.

Example 6

A proof: power sums modulo a prime

Let p be prime and k a whole number. Prove that 1^k + 2^k + \dots + (p-1)^k is \equiv -1 \pmod{p} if (p - 1) \mid k, and \equiv 0 \pmod{p} otherwise.

Solution

Proof. Call the sum S. If (p - 1) \mid k, each term is \equiv 1 by Fermat’s little theorem and Theorem 1(a), so S \equiv p - 1 \equiv -1. Otherwise let g be a primitive root modulo p (Theorem 7). By Corollary 3, 1, \dots, p - 1 are congruent in some order to g^0, \dots, g^{p-2}, so with h = g^k,

S \equiv \sum_{i=0}^{p-2} h^i \pmod{p}.

As p - 1 = \operatorname{ord}_p(g) does not divide k, h \not\equiv 1 by Theorem 1(a). Multiplying out, (h - 1) S \equiv h^{p-1} - 1 \equiv 0 by Fermat’s little theorem, and p \nmid h - 1, so Euclid’s lemma gives p \mid S. \square

Boundaries

  • Many moduli have none. Modulo 8 the units 1, 3, 5, 7 all square to 1; modulo 15 every unit has a^4 \equiv 1 while \varphi(15) = 8. Theorem 9 lists the moduli that have one.
  • Lagrange’s bound needs a prime and p \nmid c_k. x^2 \equiv 1 \pmod{8} has four solutions, and 7x \equiv 0 \pmod{7} has seven.
  • Existence is not construction. The proof of Theorem 7 names no primitive root, and no base works for every prime: \operatorname{ord}_7(2) = 3. A square b^2 with p \nmid b has (b^2)^{(p-1)/2} \equiv 1 for odd p, and -1 has order at most 2; hence the exclusions in Artin’s conjecture.
  • An index belongs to its base and lives modulo \varphi(n). Modulo 19, \operatorname{ind}_2(3) = 13 but \operatorname{ind}_3(3) = 1; and \operatorname{ind}_2(18) + \operatorname{ind}_2(18) = 18 while \operatorname{ind}_2(18 \cdot 18) = 0.
  • Hard, not proved hard. Powers are fast (Powers modulo n); recovering the exponent is believed slow for well-chosen large primes, with no proof.

Where this goes next

With a primitive root modulo an odd prime p, the squares modulo p are the residues of even index, half of the nonzero ones; that is the starting point of Quadratic residues and the Legendre symbol. RSA and primality tests uses orders to analyze the Fermat and Miller-Rabin tests. In algebra, Theorem 7 says \mathbb{Z}_p^{\times} is cyclic, and the same count shows every finite group of nonzero elements of a field is cyclic (Finite fields, Theorem 4). Theorem 1(b) is the case \mathbb{Z}_n^{\times} of Lagrange's theorem.

Exercises

Orders and primitive roots

  1. Find \operatorname{ord}_{17}(2) and \operatorname{ord}_{17}(3).
  2. Use Theorem 4 to show that 3 is a primitive root modulo 31.
  3. Find the smallest positive primitive root modulo 41, showing why each smaller candidate fails.
  4. How many primitive roots does 37 have? How many of 1, \dots, 36 have order 12 modulo 37, and how many have order 9?
  5. Using Exercise 1, find every residue of order 4 modulo 17.
  6. Suppose \operatorname{ord}_n(a) = 12. Find the orders of a^8 and a^9.

Indices modulo 19

Use the table of \operatorname{ind}_2 from Example 2.

  1. List the nonzero cubes modulo 19: the a with 19 \nmid a for which x^3 \equiv a is solvable.
  2. Solve x^6 \equiv 7 \pmod{19}.
  3. Show that 3x^4 \equiv 5 \pmod{19} has no solution.
  4. Find every positive integer x with 6^x \equiv 5 \pmod{19}.
  5. In the exchange of Example 4, with the same p = 19 and g = 2, Yuna announces 6 and Kofi announces 11. Find the shared key.

Other moduli

  1. Find the periods of the decimal expansions of \displaystyle \frac{1}{19} and \displaystyle \frac{1}{37}.
  2. Show that 2 is a primitive root modulo 27, and find a primitive root modulo 54.
  3. Which of 18, 26, 27, 50, 64, 100 have a primitive root?

Proofs

  1. Prove Wilson’s theorem, (p-1)! \equiv -1 \pmod{p} for every prime p, using a primitive root.
  2. Let p be prime and \operatorname{ord}_p(a) = 3. Prove that a^2 + a + 1 \equiv 0 \pmod{p} and \operatorname{ord}_p(a + 1) = 6.
  3. Let p be prime and d \mid p - 1. Prove that x^d \equiv 1 \pmod{p} has exactly d solutions among 1, \dots, p - 1.
  4. Let p be prime and g a primitive root modulo p. Prove that g or g + p is a primitive root modulo p^2.
  5. Let n \ge 3 have a primitive root. Prove that the only solutions of x^2 \equiv 1 \pmod{n} are x \equiv \pm 1.
Answers
  1. \operatorname{ord}_{17}(2) = 8 and \operatorname{ord}_{17}(3) = 16. Orders divide 16. 2^4 \equiv -1, so 2^8 \equiv 1 while 2^4 \not\equiv 1. For 3: 3^4 = 81 \equiv -4 and 3^8 \equiv 16 \equiv -1, so by Theorem 4 (only q = 2) 3 is a primitive root.
  2. \varphi(31) = 30 = 2 \cdot 3 \cdot 5, so check 3^{15}, 3^{10}, 3^6. From 3^3 \equiv -4 and 3^5 = 243 \equiv -5: 3^6 \equiv 16, 3^{10} \equiv 25 \equiv -6, 3^{15} \equiv (-6)(-5) \equiv -1. None is 1.
  3. 6. \varphi(41) = 40 = 2^3 \cdot 5, so test a^{20} and a^8. 2^{10} = 1024 \equiv -1 gives 2^{20} \equiv 1; 3^4 = 81 \equiv -1 gives 3^8 \equiv 1; 4^{20} = (2^{20})^2 \equiv 1; 5^4 \equiv 10, 5^8 \equiv 18, 5^{16} \equiv -4, 5^{20} \equiv -40 \equiv 1. For 6: 6^2 \equiv -5, 6^4 \equiv 25, 6^8 \equiv 10, 6^{16} \equiv 18, 6^{20} \equiv 450 \equiv -1. Neither 6^8 nor 6^{20} is 1.
  4. By Theorem 7: \varphi(36) = 12 primitive roots, \varphi(12) = 4 residues of order 12 and \varphi(9) = 6 of order 9.
  5. 4 and 13. As 3 is a primitive root, they are 3^k with \gcd(16, k) = 4, so k = 4, 12: 3^4 \equiv 13 and 3^{12} \equiv (-4)^3 = -64 \equiv 4.
  6. 3 and 4, by Theorem 2: 12/\gcd(12, 8) and 12/\gcd(12, 9).
  7. 1, 7, 8, 11, 12, 18. With y = \operatorname{ind}_2 x, x^3 \equiv a means 3y \equiv \operatorname{ind}_2 a \pmod{18}, solvable exactly when 3 \mid \operatorname{ind}_2 a: indices 0, 3, 6, 9, 12, 15.
  8. x \equiv 2, 3, 5, 14, 16, 17 \pmod{19}. 6y \equiv \operatorname{ind}_2 7 = 6 \pmod{18} means 3 \mid y - 1, so y = 1, 4, 7, 10, 13, 16 and x \equiv 2, 16, 14, 17, 3, 5.
  9. x \equiv 0 fails; otherwise 13 + 4y \equiv 16 \pmod{18}, so the odd number 4y - 3 would be a multiple of 18, and there is no y.
  10. x \equiv 5 \pmod{9}. 14x \equiv \operatorname{ind}_2 5 = 16 \pmod{18} means 7x \equiv 8 \pmod{9}, and 7 \cdot 4 \equiv 1 gives x \equiv 32 \equiv 5. Check: 6^2 \equiv -2, 6^4 \equiv 4, 6^5 \equiv 24 \equiv 5.
  11. 7. \operatorname{ind}_2 6 = 14 and \operatorname{ind}_2 11 = 12, so the key is 2^{168}, and 168 = 9 \cdot 18 + 6 gives 2^6 \equiv 7.
  12. 18 and 3, the orders of 10 (Example 5). \operatorname{ind}_2 10 = 17 is coprime to 18, so 10 is a primitive root modulo 19. Modulo 37, 10^3 = 1000 = 27 \cdot 37 + 1, and \displaystyle \frac{1}{37} = 0.\overline{027}.
  13. \operatorname{ord}_{27}(2) divides 18 and is even, since 2^t \equiv 1 \pmod{27} forces 2^t \equiv 1 \pmod{3}. Of 2, 6, 18: 2^2 = 4 and 2^6 = 64 \equiv 10, so it is 18. Modulo 54 take the odd number 29 = 2 + 27; as in the proof of Theorem 9, \operatorname{ord}_{54}(29) = \operatorname{ord}_{27}(29) = 18 = \varphi(54).
  14. By Theorem 9, 18, 26, 27 and 50 have one; 64 = 2^6 and 100 = 2^2 \cdot 5^2 do not.
  15. Proof. For p = 2, 1! \equiv -1. Let p be odd, g a primitive root and \displaystyle m = \frac{p-1}{2}. By Corollary 3, (p-1)! \equiv g^0 g^1 \cdots g^{p-2} = g^{(p-2)m}, and g^m \equiv -1 by Theorem 8, so (p-1)! \equiv (-1)^{p-2} = -1. \square
  16. Proof. 0 \equiv a^3 - 1 = (a - 1)(a^2 + a + 1) and a \not\equiv 1, so Euclid’s lemma gives a^2 + a + 1 \equiv 0. Then (a + 1)^2 \equiv a and (a + 1)^3 \equiv a^2 + a \equiv -1, so (a + 1)^6 \equiv 1 and the order divides 6. It is not 1 or 2, since either would give (a + 1)^2 \equiv 1, while (a + 1)^2 \equiv a \not\equiv 1; nor 3, as -1 \not\equiv 1 (p \ne 2, since 3 \mid p - 1). \square
  17. Proof. x^d \equiv 1 exactly when \operatorname{ord}_p(x) \mid d. Each e \mid d divides p - 1, so by Theorem 7 exactly \varphi(e) residues have order e, and the count is \sum_{e \mid d} \varphi(e) = d by Theorem 6. \square
  18. Proof. Let t = \operatorname{ord}_{p^2}(g). Then t \mid p(p - 1), and (p - 1) \mid t since g^t \equiv 1 \pmod{p}, so t is p - 1 or p(p - 1). If g^{p-1} \not\equiv 1 \pmod{p^2}, g works. Otherwise use g + p, also a primitive root modulo p. By the binomial theorem, modulo p^2,
\begin{aligned} (g + p)^{p-1} &\equiv g^{p-1} + (p - 1) g^{p-2} p \\ &\equiv 1 - p g^{p-2}, \end{aligned}

which is not 1 as p \nmid g. So g + p has order p(p - 1) modulo p^2. \square 19. Proof. Let g be a primitive root and m = \varphi(n), even as n \ge 3. A solution is coprime to n, so it is g^k with 0 \le k < m, and m \mid 2k (Theorem 1(a)), so k is 0 or m/2. Both 1 and -1 are solutions, different as n \ge 3. \square

math.wiki · updated 2026-11-18 · CC-BY-SA-4.0