$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.1: More Properties of Multiplicative Order

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

$$\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....