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?
 A: Below is the key theorem as it applies to arbitrary finite abelian groups. See below 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.
$\!\begin{align}{\bf Theorem}\quad\rm maxord(G)\ &\rm =\ expt(G)\ \ \text{for a finite abelian group $\rm\, G,\, $ i.e.}\\[.5em]
\rm \max\,\{ ord(g) : \: g \in G\}\ &=\rm\  \min\, \{ n>0 : \: g^n = 1\ \:\forall\ g \in G\} \end{align}$
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."


Below is excerpted from my sci.math post on Apr 29, 2002, as is the above Lemma.
Theorem $ $  A subgroup $G$ of the multiplicative group of a field is cyclic.
Proof $\  X^m = 1\,$ has $\#G$ roots by the above Lemma, with $\,m = {\rm maxord}(G) = {\rm expt}(G).\,$ Since a polynomial $\,P\,$  over a field satisfies
$\,\#{\rm roots}(P) \le \deg(P)\,$ we have $\,\#G \le m.\,$ But $\,m \le \#G\,$ because the maxorder $\,m <= \#G\,$ via $\,g^{\#G} = 1\,$ for all $\,g \in G\,$ (Lagrange's theorem). So $\,m = \#G = {\rm maxord}(G) \Rightarrow G\,$ has an elt of order $\,\#G,\,$ so $G$ is cyclic.
