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