# Maximum order of integers coprime to a prime $p$

The following is a lemma I read online, but I don't understand part of the proof.

Let $d$ be the maximum possible order among integers $a$ prime to $p$. Then for any integer $a$ not divisible by $p$, the order of $a$ divides $d$.

Proof: Let $b$ be an element of order $d$, let $k$ be the order of $a$, and let $g=\gcd(k,d)$. Then $a^g$ has order $k/(k,g)=k/g$, and $k/g$ is relatively prime to $d$. Therefore $ba^g$ has order $d\cdot k/g$, which by maximality of $d$ implies that $k/g=1$. Hence $k|d$.

The one part I don't understand is how $k/g$ and $d$ are relatively prime. If I take $d=6$, $k=4$, $g=2$, then $k/g$ and $d$ are not relatively prime. However, I've gone through a few cases for small primes, and such a situation as never arisen, so there must be some constraints on which values $k$ and $d$ can take. Could someone please explain this?

-
How are you defining order? If I understand your question correctly, g divides k so gcd(k/g,d)=1 follows from gcd(k,d)=1 – WWright Oct 15 '10 at 4:56
I define order to be for any integer $a$ relatively prime to $p$, $a$ has order $k$ if $k$ is the least positive integer such that $a^k\equiv 1\pmod{p}$. How do you know that $gcd(k,d)=1$? – yunone Oct 15 '10 at 5:03
Do you have a link to the original? The reason you can't find counterexamples is that in reality k divides d (what you are trying to prove) and so you will always find that gcd(k,d) = k. – Aryabhata Oct 15 '10 at 5:11
Yes, here is where I found it: math.berkeley.edu/~molsson/Lec-Notes-1.pdf The particular lemma is near the very end. – yunone Oct 15 '10 at 5:15
@xdfm: There are errors in that pdf. For instance Lemma 4 is false. Consider a = 2, a' = 4 mod 5. We have k=4, k'=2, but order of 8 = a.a' is not 8 = k.k'. If you are taking that course, I suggest you talk to the professor. – Aryabhata Oct 15 '10 at 5:35

Below is the key theorem as it applies to arbitrary finite abelian groups. See my post here for an example of how it is applied to deduce the more general result that a finite multiplicative subgroup of a domain is cyclic. The lemma is famous as "Herstein's hardest problem" - see the note below.

THEOREM $\rm\quad\quad\: maxord(G)\ =\ expt(G)\$ for a finite abelian group $\rm\: G\:,\$ i.e.

$\rm\quad\ \ max\ \{ ord(g) : \: g \in G\}\ =\ min\ \{ n>0 : \: g^n = 1\ \:\forall\ g \in G\}$

Proof $\ \:$ By the lemma below, $\rm\: S\: =\: \{ ord(g) : \:g \in G \}$ is a finite set of naturals closed under$\rm\ lcm\:$.

Hence every elt $\rm\ s \in S\:$ is a divisor of the max elt $\rm\: m\:$ [else $\rm\: lcm(s,m) > m\:$],$\$ so $\rm\ m = expt(G)\:$.

LEMMA $\$ A finite abelian group $\rm\:G\:$ has an lcm-closed order set, i.e. with $\rm\: o(X) =$ order of $\rm\: X$

$\rm\quad\quad\quad\quad\ \ X,Y \in G\ \Rightarrow\ \exists\ Z \in G:\ o(Z) = lcm(o(X),o(Y))$

Proof$\ \$ By induction on $\rm o(X)\: o(Y)\:.\$ If it's $\:1\:$ then trivially $\rm\:Z = 1\:$. $\$ Otherwise

write $\rm\ o(X) =\: AP,\: \ o(Y) = BP',\ \ P'|P = p^m > 1\:,\$ prime $\rm\: p\:$ coprime to $\rm\: A,B$

Then $\rm\: o(X^P) = A,\ o(Y^{P'}) = B\:.\$ By induction there's a $\rm\: Z\:$ with $\rm \: o(Z) = lcm(A,B)$

so $\rm\ o(X^A\: Z)\: =\: P\ lcm(A,B)\: =\: lcm(AP,BP')\: =\: lcm(o(X),o(Y))\:$.

NOTE $\ \$ This lemma was presented as problem 2.5.11, p. 41 in the first edition of Herstein's popular textbook "Topics in Algebra". In the 2nd edition Herstein added the following note (problem 2.5.26, p.48)

Don't be discouraged if you don't get this problem with what you know of group theory up to this stage. I don't know anybody, including myself, who has done it subject to the restriction of using material developed so far in the text. But it is fun to try. I've had more correspondence about this problem than about any other point in the whole book."

-
Thanks for your response, it is a bit over my head as of now. Thanks for mentioning the book in which this result is found, I'll be sure to look into it. – yunone Oct 16 '10 at 2:08
@xdfm: Don't let the notation scare you - at the heart the proof uses only elementary number theory. Wherever you see "group" you can simply think of the set of nonzero integers modulo p. Please feel free to ask questions and I'll be happy to elborate. – Bill Dubuque Oct 16 '10 at 2:16