# 5.1: More Properties of Multiplicative Order

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

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

This page titled 5.1: More Properties of Multiplicative Order is shared under a CC BY-SA license and was authored, remixed, and/or curated by Jonathan A. Poritz.