5.1: More Properties of Multiplicative Order
( \newcommand{\kernel}{\mathrm{null}\,}\)
But first, we need some more facts about [multiplicative] order.
Theorem 5.1.1
Suppose n∈N and a∈Z satisfy n≥2 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:
- 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?
- Therefore for n\in\ZZ, the odd prime divisors of n^2+1 are congruent to 1 \text{ mod } 4.
- 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....