6
$\begingroup$

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?

  • 0
    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)=12010-10-15
  • 0
    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$?2010-10-15
  • 0
    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.2010-10-15
  • 0
    Yes, here is where I found it: http://math.berkeley.edu/~molsson/Lec-Notes-1.pdf The particular lemma is near the very end.2010-10-15
  • 0
    @xdfm I'm sorry, I misread your post. There is no reason to say gcd(k,d)=12010-10-15
  • 0
    @WWright No worries, thanks for taking the time to look at it.2010-10-15
  • 2
    @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.2010-10-15
  • 0
    @WWright: You cannot prove gcd(k/g,d)=1, as xdfm notes: d=6,k=4,g=2. You also cannot prove that gcd(k/g,d) $\neq$ 1, as it is true when k divides d.2010-10-15
  • 0
    @Moron: I realized that I made the same error just as you were typing that :)2010-10-15
  • 0
    @Moron, I noticed in the proof of Lemma 4 that the author says (k,k')=1, so I think there is the assumption that the orders are coprime, but the author forgot to write this in the statement of the lemma.2010-10-15
  • 0
    @xdfm: Yes I guess that is just an omission, and they seem to be using that in Lemma 5, too.2010-10-15

1 Answers 1

3

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."

  • 0
    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.2010-10-16
  • 0
    @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.2010-10-16