Order of an Element

If \(a\) and \(n\) are relatively prime integers, Euler's theorem says that \( a^{\phi(n)} \equiv 1 \pmod n\), where \( \phi \) is Euler's totient function. But \( \phi(n) \) is not necessarily the smallest positive exponent that satisfies the equation \( a^d \equiv 1 \pmod n \); the smallest positive exponent is called the order of \(a\) mod \(n \).

Analysis of the orders of elements \( n\) has numerous applications in elementary number theory. In particular, the proof of the theorem on the existence of primitive roots hinges upon counting elements of a given order and answering questions about which orders are possible.

This definition of order is consistent with other, more general definitions of "order" in group theory and set theory. In particular, the number of elements in a set is sometimes referred to as its order. In this case, the order of \( a\) is the (set-theoretic) order of the set of powers of \( a\) mod \( n \). (In the language of group theory, the order of \( a \) is the order of the cyclic subgroup generated by \( a \).)

Given a positive integer \(n > 1\) and an integer \(a\) such that \(\gcd(a, n) = 1,\) the smallest positive integer \(d\) for which \(a^d \equiv 1\) mod \( n \) is called the order of \(a\) modulo \(n\). Note that Euler's theorem says that \(a^{\phi(n)} \equiv 1\pmod n \), so such numbers \(d\) indeed exist. The order of \( a\) mod \( n \) is sometimes written as \(\text{ord}_{ n }(a)\) for short.

There are \(\phi(9) = 6 \) distinct congruence classes mod \( 9\) of integers that are relatively prime to \( 9 \), namely \( 1,2,4,5,7,8\). Compute their orders mod \( 9 \).

---

• The powers of \( 1 \) are \( 1,1,1,\ldots \). The order of \( 1 \) is \( 1 \).
• The powers of \( 2 \) are \( 2,4,8,7,5,1, \ldots \). The order of \( 2 \) is \( 6 \).
• The powers of \( 4 \) are \( 4,7,1,\ldots \). The order of \( 4 \) is \( 3 \).
• The powers of \( 5 \) are \( 5,7,8,4,2,1, \ldots \). The order of \( 5 \) is \( 6 \).
• The powers of \( 7 \) are \( 7,4,1, \ldots \). The order of \( 7 \) is \( 3 \).
• The powers of \( 8 \) are \( 8,1, \ldots \). The order of \( 8 \) is \( 2 \). \(_\square\)

The example suggests another way to think about the order: the sequence of powers of \( a \) is periodic, and the order of \( a \) is simply the minimum period of this sequence.

Notice that in each case of the previous example, the order was \( \le 6 \), as noted above. Moreover, the order was always a divisor of \( 6 \). This is true in general:

\(\quad (1)\) If \({ a }^{ m } \equiv 1 \pmod{n}\), then \(\text{ord}_{ n }(a)|m\).
\(\quad (2)\) \(\text{ord}_{ n }(a)|\varphi(n)\); if \(p\) is a prime, then \(\text{ord}_{ p }(n)|(p - 1)\) for any \(n\).
\(\quad (3)\) If \({ a }^{ \ell } \equiv { a }^{ m } \pmod{n}\), then \({ \ell } \equiv { m } \pmod{\text{ord}_{ n }(a)}\).

In order to prove property \((1)\), let \(d = \text{ord}_{ n }(a)\). Since \(a^{m} \equiv 1\pmod n \) and \(a^{d} \equiv 1\pmod n \), \( a^{mx+dy} \equiv 1\pmod n \) for any \( x\) nd \(y \). By Bezout's identity, there exist \( x \) and \( y \) such that \(mx+dy = \text{gcd}(d,m).\) Then, from the minimality of \(d,\) it follows that \(d \le \gcd(m, d)\), which cannot hold unless they are equal and \(d|m\).

(Another way to see (1) is that the minimum period of a periodic sequence divides any other period, essentially by the division algorithm.)

Property (2) follows from property (1) and Euler's theorem, and property (3) follows from property (1) applied to \(\ell-m\).

Prove that \(n|\varphi ({ a }^{ n } - 1)\) for all positive integers \(a\) and \(n\).

---

It is immediate that \( \text{ord}_{ { a }^{ n } - 1 }(a) = n\): certainly \( a^n \equiv 1 \) \(\pmod {a^n-1} \), and \( a^d\equiv 1 \) \(\pmod {a^n-1} \) implies \( (a^n-1)|(a^d-1)\), so \( d \ge n \). Then the result follows from property (1) above. \( _\square \)

If \(a^p\equiv 1\pmod n\) with prime \(p\) and \(n\nmid a-1\), then \(\text{ord}_{n}{a}=p\).

---

It follows from property (1) above that \(\text{ord}_{n}(a)|p\), so \(\text{ord}_{n}(a)\) must equal either \(1\) or \(p\). Since \(n\nmid a-1\), the order cannot be \(1\), so it is \(p\). \(_\square \)

Prove that there does not exist an integer \(n>1\) such that \(n|2^n-1\).

---

Suppose there does exist such \(n\), and let \(p\) be the smallest prime divisor of \(n\). Then it follows from \(2^n\equiv 1\pmod {p}\) that \(\text{ord}_{p}(2)|n\). However, we know \(\text{ord}_{p}(2)|p-1\) by property (2) above and \(\text{ord}_{p}(2)>1\) (the order is divisible by a prime); thus \(\text{ord}_{p}(2)<p\), which contradicts \(p\) being the smallest prime divisor of \(n\). \(_\square\)

Prove that any prime factor of the \(n^\text{th}\) Fermat number \(2^{ 2^n }+1\) is congruent to \(1\) modulo \(2^{n + 1}\). Show that there are infinitely many prime numbers of the form \({ 2 }^{ n }k + 1\) for any fixed \(n\).

---

Consider a prime \(p\) such that \(p|{ 2 }^{ 2^n }+1\); that is, \( 2^{2^n} \equiv -1 \pmod p \).Then \({ 2 }^{ 2^{ n+1 }} \equiv 1\pmod p \) and consequently \(\text{ord}_{ p }(2)|{ 2 }^{ n+1 }\). So \(\text{ord}_{ p }(2)={ 2 }^{ k }\) for some \( k \le n+1\). We will prove that in fact \(k = n + 1\). Indeed, if this is not the case, then \({ o }_{ p }(2)|2^{n}\) and so \(2^{2^n} \equiv 1 \pmod p \). But this implies that \( 1 \equiv -1 \pmod p \), so \( p =2\), but this is impossible. Therefore, we have found that \(\text{ord}_{ p }(2) = { 2 }^{ n+1 }\) and so \( 2^{n+1} | (p-1) \) by Property (1) above.

The second part is a direct consequence of the first. Indeed, it is enough to prove that there exists an infinite set of Fermat numbers \(\large { (2^{ 2^{ n_k }} + 1) }_{ { n }_{ k } > a }\), any two relatively prime. Then we could take a prime factor of each such Fermat number and apply the first part to obtain that each such prime is of the form \({ 2 }^{ n }k + 1\). Not only is it easy to find such a sequence of co-prime Fermat numbers, but in fact any two distinct Fermat numbers are relatively prime. Indeed, suppose that \(d|\gcd(2^{ 2^a } + 1,2^{ 2^{ a+b }} + 1)\). Then \(2^{ 2 ^{ a + 1 }} \equiv 1\pmod d \) and so \(d| 2 ^{ 2^{ a+b }} - 1\). Combining this with \(d|2^{ 2^{ a+b }} + 1\), we obtain a contradiction. Hence both parts of the problem are solved. \(_\square\)

The positive integer \(a\) is called a primitive root mod \(n\) if \(\gcd(a, n) = 1\) and \(\text{ord}_{ n }(a) = \phi (n)\). The proof that primitive roots exist mod \( p \) where \( p \) is a prime involves counting elements of various orders mod \( p \). Here is an outline.

Step 1: Prove a version of the division algorithm for polynomials with coefficients in \( {\mathbb Z}_p\). That is, given two polynomials \( a(x) \) and \( b(x) \) with coefficients in \( {\mathbb Z}_p\), we can write \( a(x) = b(x)q(x)+r(x) \) for some polynomials \( q(x) \) and \( r(x) \), such that \( r(x) = 0 \) or deg \( r(x) < \) deg \( b(x) \).

Step 2: Use step 1 to show that a polynomial of degree \( d \) has at most \( d \) roots mod \( p \): If \( a \) is a root of \( f(x) \), write \( f(x) = (x-a)q(x)+r(x) \) and evaluate at \( a \) to show that \( r(x) = 0 \). Induct on the degree of \( f(x) \). Note that we are using that \( p \) is prime in a subtle way: namely, if \( f(b) \equiv 0 \pmod p \), then \( (b-a)q(b) \equiv 0 \pmod p \), so either \( b\equiv a \) or \( q(b) \equiv 0 \). This last conclusion fails for composite modulus in general. For instance, \( x^2-1 \) has four roots mod \( 8 \).

Step 3: Suppose there is an element \( a \) of order \( d \), \( d|(p-1) \). Then \( x^d-1 \) has at most \( d\) roots mod \( p \), by step 2, but on the other hand \( 1,a,a^2,\ldots, a^{d-1} \) are all distinct roots. So this is the entire set of roots. Show that exactly \( \phi(d) \) of these roots have order \( d \) (because the others have smaller orders).

Step 4: For every divisor \( d|(p-1) \), let \( \psi(d) \) be the number of elements of order \( d \) mod \( p \). Step 3 shows that either \( \psi(d) = 0 \) or \( \psi(d) = \phi(d) \). Now every nonzero element mod \( p \) has some order \( d|(p-1) \), so the sum of the \( \psi(d) \) is \( p-1 \): \[ p-1 = \sum_{d|(p-1)} \psi(d) \le \sum_{d|(p-1)}\phi(d) = p-1. \] (This last equality is proved in the page on proofs by bijections.) So equality holds everywhere, so we have proved:

Let \( p \) be an odd prime. For every \( d|(p-1)\), there are exactly \( \phi(d) \) elements of order \( d \) in \( {\mathbb Z}_p^* \).

In particular, there are \(\phi(p-1)\) primitive roots.

What do all prime divisors of \(n^2+n+1\) have in common?

To list the first few, we have

\[\begin{array}{rrr} n=1: 1^2+1+1&=&3\\ n=2: 2^2+2+1&=&7\\ n=3: 3^2+3+1&=&13\\ n=4: 4^2+4+1&=&3\cdot 7\\ n=5: 5^2+5+1&=&31\\ n=6: 6^2+6+1&=&43\\ n=7: 7^2+7+1&=&3\cdot 19&. \end{array}\]

Notice that all the primes are either \(0\) or \(1\)\(\pmod 3\). In other words, it appears that all prime divisors of \(n^2+n+1\) that are greater than \(3\) are of the form \(3k+1\). Indeed, the observation is true and can be generalized as follows:

If \(q\) is a prime divisor of \(\large \frac {n^p-1}{n-1}\), then either \(q=p\) or \(q\equiv 1\pmod {p}\).

Although this result is immediate by cyclotomic polynomials, it is also simple using the divisibility properties of order. We make use of the following handy lemma:

If \(a^p\equiv 1\pmod n\) with prime \(p\) and \(n\nmid a-1\), then \(\text{ord}_{n}{a}=p\).

---

It follows from property (1) above that \(\text{ord}_{n}(a)|p\), so \(\text{ord}_{n}(a)\) must equal either \(1\) or \(p\). Since \(n\nmid a-1\), the order cannot be \(1\), so it is \(p\).

Since \(q|\frac {n^p-1}{n-1}\), \(q\) satisfies \(n^p\equiv 1\pmod q\).

If \(q|n-1\), then \(q|(\frac {n^p-1}{n-1},n-1)=(p,n-1)|p\) \(\implies q=p\).

If \(q\nmid n-1\), then according to the property above \(p=\text {ord}_{q}(n)|q-1\), i.e \(q\equiv 1\pmod p\). \(_\square \)