Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 nN and aZ satisfy n2 and gcd(a,n)=1. Then ak1(modn) for kN iff ordn(a)k.

Proof

One direction is very easy: if kN satisfies ordn(a)k then dN such that k=ordn(a)d and thus ak=aordn(a)d=(aordn(a))d1d=1(modn) .

Conversely, suppose kN is such that ak1(modn). Apply the Division Algorithm to get q,rN such that k=ordn(a)q+r and 0r<ordn(a). Then 1ak=aordn(a)q+r=(aordn(a))qar1qarar(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 ar1(modn) and 0r<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 nN and aZ satisfy n2 and gcd(a,n)=1. Then ajak(modn) for j,kN iff jk(modordn(a)).

Proof

Again, one direction is very easy: if j,kN satisfy jk(modordn(a)) then Z such that j=k+ordn(a) from which we compute aj=ak+ordn(a)=ak(aordn(a))ak1=ak(modn) .

Conversely, suppose j,kN are such that ajak(modn) and, without loss of generality, jk. Multiplying both sides of this congruence by (a1)k, which exists since gcd(a,n)=1, we get ajk1(modn). Then by Theorem 5.1.1 we have ordn(a)(jk) or jk(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=a22, then we have the containment ba, 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=336, we still have ca, 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 kN. This size will just be the order of that element ak, so we need the following

Theorem 5.1.3

Suppose nN and aZ satisfy n2 and gcd(a,n)=1. Then kN, ordn(ak)=ordn(a)gcd(ordn(a),k)

Proof

Fix some kN 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)r1(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)r1(modn), skr by Theorem 5.1.1, so mN 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 nN satisfies n2. Prove that if there exists a(Z/nZ) such that ordn(a)=n1, then n is prime.

2. Suppose p is an odd prime and a(Z/pZ). Prove that if kN such that ordp(a)=2k then ak1(modp). [Hint: look at the proof of Lemma 3.2.1.]

3. Suppose nN satisfies n2 and a,bZ/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:

  1. Prove: if an odd prime p and nZ are such that n21(modp), then 4ϕ(p) [use a theorem in this section]. Why is it necessary to exclude the even prime here?
  2. Therefore for nZ, the odd prime divisors of n2+1 are congruent to 1 mod 4.
  3. Now assume for contradiction’s sake that there are only finitely many primes p1,,pn congruent to 1 mod 4 and consider the number (2p1pn)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.

  • Was this article helpful?

Support Center

How can we help?