5.1: More Properties of Multiplicative Order

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

But first, we need some more facts about [multiplicative] order.

Theorem \(\PageIndex{1}\)

Suppose \(n\in\NN\) and \(a\in\ZZ\) satisfy \(n\ge2\) and \(\gcd(a,n)=1\). Then \(a^k\equiv1\pmod{n}\) for \(k\in\NN\) iff \(\ord_n(a)\mid k\).

Proof

One direction is very easy: if \(k\in\NN\) satisfies \(\ord_n(a)\mid k\) then \(\exists d\in\NN\) such that \(k=\ord_n(a)\cdot d\) and thus \[a^k=a^{\ord_n(a)\cdot d}=(a^{\ord_n(a)})^d\equiv1^d=1\pmod{n}\ .\]

Conversely, suppose \(k\in\NN\) is such that \(a^k\equiv1\pmod{n}\). Apply the Division Algorithm to get \(q,r\in\NN\) such that \(k=\ord_n(a)\cdot q+r\) and \(0\le r<\ord_n(a)\). Then \[1\equiv a^k=a^{\ord_n(a)\cdot q + r}=(a^{\ord_n(a)})^q\cdot a^r\equiv1^q\cdot a^r\equiv a^r\pmod{n}\ .\] But the definition of the order \(\ord_n(a)\) is that it is the smallest positive integer such that \(a\) to that power is congruent to 1. The only way for \(a^r\equiv1\pmod{n}\) and \(0\le r<\ord_n(a)\) to be true, then, is if \(r=0\). Thus \(k=\ord_n(a)\cdot q\) and \(\ord_n(a)\mid k\), as desired.

What this will mean is that when we work in the cyclic subgroup of \((\ZZ/n\ZZ)^*\) generated by some element \(a\), we should work with the powers of \(a\) as if the powers lived in \(\ZZ/(\ord_n(a))\ZZ\). That is:

Theorem \(\PageIndex{2}\)

Suppose \(n\in\NN\) and \(a\in\ZZ\) satisfy \(n\ge2\) and \(\gcd(a,n)=1\). Then \(a^j\equiv a^k\pmod{n}\) for \(j,k\in\NN\) iff \(j\equiv k\pmod{\ord_n(a)}\).

Proof

Again, one direction is very easy: if \(j,k\in\NN\) satisfy \(j\equiv k\pmod{\ord_n(a)}\) then \(\exists\ell\in\ZZ\) such that \(j=k+\ord_n(a)\cdot\ell\) from which we compute \[a^j=a^{k+\ord_n(a)\cdot\ell}=a^k\cdot (a^{\ord_n(a)})^\ell\equiv a^k\cdot1^\ell=a^k\pmod{n}\ .\]

Conversely, suppose \(j,k\in\NN\) are such that \(a^j\equiv a^k\pmod{n}\) and, without loss of generality, \(j\ge k\). Multiplying both sides of this congruence by \((a^{-1})^k\), which exists since \(\gcd(a,n)=1\), we get \(a^{j-k}\equiv1\pmod{n}\). Then by Theorem 5.1.1 we have \(\ord_n(a)\mid(j-k)\) or \(j\equiv k\pmod{\ord_n(a)}\).

Example \(\PageIndex{1}\)

The rows in Table 5.0.1 bear out Theorems 5.1.1 and 5.1.2: each cyclic subgroup (row) has a number of elements which divides the corresponding \(\phi(n)\), and powers of the generator \(a\) are only defined up to \(\ord_n(a)\).

It also seems that some of the smaller cyclic subgroups sometimes occur as a subset of a larger cyclic subgroup. So in mod \(n=7\), if \(a=3\) and \(b=a^2\equiv2\), then we have the containment \(\left<b\right>\subset\left<a\right>\), where \(\left<b\right>\) consists of half of the elements of \(\left<a\right>\), namely the even powers of \(a\): \[\left<b\right>=\left\{b,\ b^2,\ b^3\right\}=\left\{2,\ 4,\ 1\right\}=\left\{3^2,\ 3^4,\ 3^6\right\}\subset\left\{3,\ 3^2,\ 3^3,\ 3^4,\ 3^5,\ 3^6\right\}=\left<a\right>\] Looking instead at \(c=3^3\equiv6\), we still have \(\left<c\right>\subset\left<a\right>\), but now \(\left<c\right>\) consists of one third of the elements of \(\left<a\right>\), the powers of \(a\) which are multiples of \(3\): \[\left<c\right>=\left\{c,\ c^2\right\}=\left\{6,\ 1\right\}=\left\{3^3,\ 3^6\right\}\subset\left\{3,\ 3^2,\ 3^3,\ 3^4,\ 3^5,\ 3^6\right\}=\left<a\right>\]

The last part of this example seems to be asking for a general statement about what size subset of a cyclic subgroup \(\left<a\right>\) is formed of the cyclic subgroup \(\left<a^k\right>\) for some \(k\in\NN\). This size will just be the order of that element \(a^k\), so we need the following

Theorem \(\PageIndex{3}\)

Suppose \(n\in\NN\) and \(a\in\ZZ\) satisfy \(n\ge2\) and \(\gcd(a,n)=1\). Then \(\forall k\in\NN\), \(ord_n(a^k)=\dfrac{\ord_n(a)}{\gcd(\ord_n(a),k)}\)

Proof

Fix some \(k\in\NN\) and let \(r=\ord(a^k)\) and \(s=\ord(a)\); with this notation, what we are trying to prove is that \(\displaystyle r=\dfrac{s}{\gcd(s,k)}\).

We shall repeatedly use in the proof the fact that since a \(\gcd\) is a divisor, \(\gcd(s,k)\mid s\) and \(\gcd(s,k)\mid k\), which means in turn that both \(\displaystyle\dfrac{s}{\gcd(s,k)},\dfrac{k}{\gcd(s,k)}\in\NN\).

Now to the proof.

The definition of order is that \(r\) is the smallest natural number such that \((a^k)^r\equiv1\pmod{n}\). Notice that \[(a^k)^{\dfrac{s}{\gcd(s,k)}}=(a^s)^{\dfrac{k}{\gcd(s,k)}}= 1^{\dfrac{k}{\gcd(s,k)}}\equiv1\pmod{n}\ .\] By Theorem 5.1.1, we conclude that \(\displaystyle r\bigm|\left(\dfrac{s}{\gcd(s,k)}\right)\).

Smallest or not, since \(a^{kr}=(a^k)^r\equiv1\pmod{n}\), \(s\mid kr\) by Theorem 5.1.1, so \(\exists m\in\NN\) such that \(m s = kr\). Dividing both sides by \(\gcd(s,k)\), we get an equation of natural numbers \[m \left(\dfrac{s}{\gcd(s,k)}\right)=\left(\dfrac{k}{\gcd(s,k)}\right) r;\] which means \[\dfrac{s}{\gcd(s,k)}\Bigm|\left(\dfrac{k}{\gcd(s,k)}\right)r\ .\] By Theorem 1.5.1, \(\displaystyle\gcd\left(\dfrac{s}{\gcd(s,k)},\dfrac{k}{\gcd(s,k)}\right)=1\), so Euclid’s Lemma 2.1.1 tells us that \(\displaystyle\dfrac{s}{\gcd(s,k)}\bigm|r\).

We have shown that \(r\) and \(\displaystyle\dfrac{s}{\gcd(s,k)}\) divide each other. But that means they are equal, which is what we were trying to prove.

Exercise \(\PageIndex{1}\)

1. Suppose \(n\in\NN\) satisfies \(n\ge2\). Prove that if there exists \(a\in(\ZZ/n\ZZ)^*\) such that \(\ord_n(a)=n-1\), then \(n\) is prime.

2. Suppose \(p\) is an odd prime and \(a\in(\ZZ/p\ZZ)^*\). Prove that if \(\exists k\in\NN\) such that \(\ord_p(a)=2k\) then \(a^k\equiv-1\pmod{p}\). [Hint: look at the proof of Lemma 3.2.1.]

3. Suppose \(n\in\NN\) satisfies \(n\ge2\) and \(a,b\in\ZZ/n\ZZ\) are both relatively prime to \(n\). Prove that \[\ord_n(ab)\mid\ord_n(a)\ord_n(b)\ .\]

4. Prove that there are infinitely many primes congruent to \(1 \text{ mod } 4\), by filling in the details of the following outline:

1. Prove: if an odd prime \(p\) and \(n\in\ZZ\) are such that \(n^2\equiv-1\pmod{p}\), then \(4\mid\phi(p)\) [use a theorem in this section]. Why is it necessary to exclude the even prime here?
2. Therefore for \(n\in\ZZ\), the odd prime divisors of \(n^2+1\) are congruent to \(1 \text{ mod } 4\).
3. Now assume for contradiction’s sake that there are only finitely many primes \(p_1,\dots,p_n\) congruent to \(1 \text{ mod } 4\) and consider the number \((2p_1\cdot\dots\cdot p_n)^2+1\). Apply the previous step....