Skip to main content

Chapter 7 Order of Elements of \(\mathbb{Z}_n\)

Definition 7.0.1.

Let \(n\gt 1\) and \(\gcd(a, n) = 1.\) The order of \(a\) modulo \(n\) is the smallest positive integer \(k\) such that \(a^k\equiv 1\pmod{n}.\)

Consider the elements in \(\mathbb{Z}_8.\) The only elements with \(\gcd(a, 8) = 1\) are those in \(U_8;\) that is

\begin{equation*} U_8 = \{1, 3, 5, 7\}. \end{equation*}

Now trivially \(1\) has order \(1\text{.}\) Note that \(3^2 = 9\equiv 1\pmod{8}, 5^2 = 25\equiv 1\pmod{8},\) and \(7^2 = 49\equiv 1\pmod{8},\) so \(3,5,7\) all have order \(2\) modulo \(8.\)

Let \(p\) be a prime. Then \(p-1\) has order \(2\) modulo \(p,\) since

\begin{equation*} (p-1)^2 = p^2-2p + 1\equiv 1\pmod{p}. \end{equation*}

The condition that \(\gcd(a, n) = 1\) is paramount. For if \(\gcd(a, n)\gt 1,\) then the congruence

\begin{equation*} ax\equiv 1\pmod{n} \end{equation*}

has no solution so then for every \(k\in\mathbb{N},\)

\begin{equation*} a^k\not\equiv 1\pmod{n}. \end{equation*}

If \(a\equiv b\pmod{n},\) then \(a^i \equiv b^i \pmod{n}\) for every \(i\text{.}\) The result follows.

Let \(a\) have order \(k\) modulo \(n.\)

Suppose that \(k\vert h,\) then \(h = kj\) for some \(j.\) Since \(a^k\equiv 1\pmod{n},\) we have

\begin{equation*} a^h=(a^k)^j\equiv 1^j=1 \pmod{n}. \end{equation*}

Conversely, let \(h\geq 1\) be such that \(a^h\equiv 1\pmod{n}.\) By the division algorithm, there exist \(q, r\) with \(h = qk + r,\) where \(0\leq r \lt k.\) So

\begin{equation*} a^h=a^{qk+r}=(a^k)^qa^r. \end{equation*}

Since \(a^h\equiv 1 \pmod{n}\) and \(a^k\equiv 1 \pmod{n},\) we have that \(a^r\equiv 1 \pmod{n}.\) But \(k\) is the smallest positive integer such that \(a^k\equiv 1 \pmod{n},\) thus \(r = 0,\) and hence \(k\vert h.\)

Consider \(2\in\mathbb{Z}_{13}.\) We know from the above theorem that \(2\) has order dividing \(\varphi(13) = 12;\) so the possible orders of \(2\) modulo \(13,\) are \(1,2,3,4,6,\) and \(12.\) Now

\begin{equation*} 2^1\equiv 2 \hspace{5mm} 2^2\equiv 4 \hspace{5mm} 2^3\equiv 8 \hspace{5mm} 2^4\equiv 3 \hspace{5mm} 2^6\equiv 12 \hspace{5mm} 2^{12}\equiv 1 \pmod{13}, \end{equation*}

so \(2\) has order \(12\) modulo \(13.\)

Let \(a\) have order \(k\) modulo \(n.\) If \(a^i\equiv a^j \pmod{n},\) then \(a^{i-j}\equiv 1\pmod{n},\) so that by theorem \(k\vert i-j\) and so \(i\equiv j \pmod{k}.\)

If \(i\equiv j \pmod{k},\) then \(i = j + qk\) for some \(q.\) So

\begin{equation*} a^i=a^{j+qk}=a^j(a^k)^q\equiv a^j \pmod{n} \end{equation*}

since \(a^k\equiv 1 \pmod{n}.\)

If \(a^j\equiv a^i \pmod{n},\) for \(1\leq i\lt j\leq k,\) then we know by the previous theorem that \(i\equiv j \pmod{k},\) which is impossible under the conditions on \(i\) and \(j.\)

The order of an element, and of powers of an element are related in the following way.

Let \(d = \gcd(h, k).\) Then we may write \(h = h_1d\) and \(k = k_1d,\) with \(\gcd(h_1, k_1) = 1.\) Now

\begin{equation*} (a^h)^{k_1}=(a^{h_1d})^{k/d}=(a^k)^{h_1}\equiv 1\pmod{n}. \end{equation*}

If we assume that \(a^h\) has order \(r\) modulo \(n,\) then we know that \(r\vert k_1.\) On the other hand, because \(a\) has order \(k\) modulo \(n,\)

\begin{equation*} a^{hr}=(a^h)^r\equiv 1\pmod{n} \end{equation*}

gives \(k\vert hr,\) so \(k_1d\vert h_1dr\) so \(k_1\vert h_1r.\) But \(\gcd(k_1, h_1) = 1,\) so \(k_1\vert r\) by Euclid's Lemma. Thus \(r = k_1,\) and

\begin{equation*} r = k_1 =\frac{k}{d}=\frac{k}{\gcd(k,h)}. \end{equation*}