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 ak≡1(modn) for k∈N iff ordn(a)∣k.
- Proof
-
One direction is very easy: if k∈N satisfies ordn(a)∣k then ∃d∈N such that k=ordn(a)⋅d and thus ak=aordn(a)⋅d=(aordn(a))d≡1d=1(modn) .
Conversely, suppose k∈N is such that ak≡1(modn). Apply the Division Algorithm to get q,r∈N such that k=ordn(a)⋅q+r and 0≤r<ordn(a). Then 1≡ak=aordn(a)⋅q+r=(aordn(a))q⋅ar≡1q⋅ar≡ar(modn) . But the definition of the order ordn(a) is that it is the smallest positive integer such that a to that power is congruent to 1. The only way for ar≡1(modn) and 0≤r<ordn(a) to be true, then, is if r=0. Thus k=ordn(a)⋅q and ordn(a)∣k, as desired.
What this will mean is that when we work in the cyclic subgroup of (Z/nZ)∗ generated by some element a, we should work with the powers of a as if the powers lived in Z/(ordn(a))Z. That is:
Theorem 5.1.2
Suppose n∈N and a∈Z satisfy n≥2 and gcd(a,n)=1. Then aj≡ak(modn) for j,k∈N iff j≡k(modordn(a)).
- Proof
-
Again, one direction is very easy: if j,k∈N satisfy j≡k(modordn(a)) then ∃ℓ∈Z such that j=k+ordn(a)⋅ℓ from which we compute aj=ak+ordn(a)⋅ℓ=ak⋅(aordn(a))ℓ≡ak⋅1ℓ=ak(modn) .
Conversely, suppose j,k∈N are such that aj≡ak(modn) and, without loss of generality, j≥k. Multiplying both sides of this congruence by (a−1)k, which exists since gcd(a,n)=1, we get aj−k≡1(modn). Then by Theorem 5.1.1 we have ordn(a)∣(j−k) or j≡k(modordn(a)).
Example 5.1.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 ϕ(n), and powers of the generator a are only defined up to ordn(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=a2≡2, then we have the containment ⟨b⟩⊂⟨a⟩, where ⟨b⟩ consists of half of the elements of ⟨a⟩, namely the even powers of a: ⟨b⟩={b, b2, b3}={2, 4, 1}={32, 34, 36}⊂{3, 32, 33, 34, 35, 36}=⟨a⟩ Looking instead at c=33≡6, we still have ⟨c⟩⊂⟨a⟩, but now ⟨c⟩ consists of one third of the elements of ⟨a⟩, the powers of a which are multiples of 3: ⟨c⟩={c, c2}={6, 1}={33, 36}⊂{3, 32, 33, 34, 35, 36}=⟨a⟩
The last part of this example seems to be asking for a general statement about what size subset of a cyclic subgroup ⟨a⟩ is formed of the cyclic subgroup ⟨ak⟩ for some k∈N. This size will just be the order of that element ak, so we need the following
Theorem 5.1.3
Suppose n∈N and a∈Z satisfy n≥2 and gcd(a,n)=1. Then ∀k∈N, ordn(ak)=ordn(a)gcd(ordn(a),k)
- Proof
-
Fix some k∈N and let r=ord(ak) and s=ord(a); with this notation, what we are trying to prove is that r=sgcd(s,k).
We shall repeatedly use in the proof the fact that since a gcd is a divisor, gcd(s,k)∣s and gcd(s,k)∣k, which means in turn that both sgcd(s,k),kgcd(s,k)∈N.
Now to the proof.
The definition of order is that r is the smallest natural number such that (ak)r≡1(modn). Notice that (ak)sgcd(s,k)=(as)kgcd(s,k)=1kgcd(s,k)≡1(modn) . By Theorem 5.1.1, we conclude that r|(sgcd(s,k)).
Smallest or not, since akr=(ak)r≡1(modn), s∣kr by Theorem 5.1.1, so ∃m∈N such that ms=kr. Dividing both sides by gcd(s,k), we get an equation of natural numbers m(sgcd(s,k))=(kgcd(s,k))r; which means sgcd(s,k)|(kgcd(s,k))r . By Theorem 1.5.1, gcd(sgcd(s,k),kgcd(s,k))=1, so Euclid’s Lemma 2.1.1 tells us that sgcd(s,k)|r.
We have shown that r and sgcd(s,k) divide each other. But that means they are equal, which is what we were trying to prove.
Exercise 5.1.1
1. Suppose n∈N satisfies n≥2. Prove that if there exists a∈(Z/nZ)∗ such that ordn(a)=n−1, then n is prime.
2. Suppose p is an odd prime and a∈(Z/pZ)∗. Prove that if ∃k∈N such that ordp(a)=2k then ak≡−1(modp). [Hint: look at the proof of Lemma 3.2.1.]
3. Suppose n∈N satisfies n≥2 and a,b∈Z/nZ are both relatively prime to n. Prove that ordn(ab)∣ordn(a)ordn(b) .
4. Prove that there are infinitely many primes congruent to 1 mod 4, by filling in the details of the following outline:
- Prove: if an odd prime p and n∈Z are such that n2≡−1(modp), then 4∣ϕ(p) [use a theorem in this section]. Why is it necessary to exclude the even prime here?
- Therefore for n∈Z, the odd prime divisors of n2+1 are congruent to 1 mod 4.
- Now assume for contradiction’s sake that there are only finitely many primes p1,…,pn congruent to 1 mod 4 and consider the number (2p1⋅⋯⋅pn)2+1. Apply the previous step....