 |
|
| Science Forum Index » Mathematics Forum » Problem with a theorem |
|
Page 1 of 1 |
|
| Author |
Message |
| Andersen |
 Posted: Thu Aug 04, 2005 11:07 am |
|
|
|
Guest
|
I have Fraleigh's Abstract Algebra book and fail to understand the proof
of the following theorem.
Theorem.
Let G be a cyclic group with n elements and generated by a. Let b\inG
and let b=a^s. Then b generates a cyclic subgroup H of G containing n/d
elements, where d is the GCD of n and s.
Proof.
That b generates a cyclic subgroup H of G is known from Theorem 3.2. We
need show only that H has n/d elements. Following the argument of the
preceding case, you can see that H has as many elements as the smallest
power of b that gives the identity. Now b=a^s and b^m=e if and only if
(a^s)^m=a^(ms)=e, or if and only if n divides ms. What is the smallest
value of m such that n divides ms? *** If d is the largest number
dividing both n and s, then in the expression n=d(n/d), the d factor of
n will divide the s factor of ms. No prime factors of n/d can be
absorbed by s in addition to the factor d, since we chose d as the
largest integer dividing both n and s. Thus all of n/d must be absorbed
in m, so the smallest such m is m=n/d []
---
I stop following/understanding the theorem from the point I marked with
three stars ***.
What does absorbed mean here? Maybe you have a better proof which tells
the size of a cyclic subgroup of a finite cyclic group.
regards,
Andersen |
|
|
| Back to top |
|
|
|
| Ed Hook |
| Posted: Thu Aug 04, 2005 2:01 pm |
|
|
|
Guest
|
Andersen wrote:
[quote:d5c7b10066]I have Fraleigh's Abstract Algebra book and fail to understand the proof
of the following theorem.
Theorem.
Let G be a cyclic group with n elements and generated by a. Let b\inG
and let b=a^s. Then b generates a cyclic subgroup H of G containing n/d
elements, where d is the GCD of n and s.
Proof.
That b generates a cyclic subgroup H of G is known from Theorem 3.2. We
need show only that H has n/d elements. Following the argument of the
preceding case, you can see that H has as many elements as the smallest
power of b that gives the identity. Now b=a^s and b^m=e if and only if
(a^s)^m=a^(ms)=e, or if and only if n divides ms. What is the smallest
value of m such that n divides ms? *** If d is the largest number
dividing both n and s, then in the expression n=d(n/d), the d factor of
n will divide the s factor of ms. No prime factors of n/d can be
absorbed by s in addition to the factor d, since we chose d as the
largest integer dividing both n and s. Thus all of n/d must be absorbed
in m, so the smallest such m is m=n/d []
---
I stop following/understanding the theorem from the point I marked with
three stars ***.
What does absorbed mean here? Maybe you have a better proof which tells
the size of a cyclic subgroup of a finite cyclic group.
[/quote:d5c7b10066]
You're right that the proof as presented isn't very
easy to follow -- rather than trying to explain the
author's squishy terminology, let me attempt a different
presentation: if m is the order of a^s in G, then you
know that ms has to be a multiple of n. Since it's clearly
a multiple of s, the order of a^s is a common multiple
of n, s. In fact, it must be the _least_ common multiple
of n, s - denoted [n,s] - since a^[n,s] = e (because
the order of a is n). But one learns early on in number
theory that (n,s)[n,s] = ns where (n,s) is what's called d
up above. Taking the last step, [n,s] = (n/d)s from which
it follows that the order of a^s is, in fact, n/d.
[quote:d5c7b10066]regards,
Andersen[/quote:d5c7b10066] |
|
|
| Back to top |
|
|
|
| Andersen |
| Posted: Fri Aug 05, 2005 1:31 am |
|
|
|
Guest
|
Ed Hook wrote:
[quote:148aa3df92]
You're right that the proof as presented isn't very
easy to follow -- rather than trying to explain the
author's squishy terminology, let me attempt a different
presentation: if m is the order of a^s in G, then you
know that ms has to be a multiple of n. Since it's clearly
a multiple of s, the order of a^s is a common multiple
of n, s. In fact, it must be the _least_ common multiple
of n, s - denoted [n,s] - since a^[n,s] = e (because
the order of a is n). But one learns early on in number
theory that (n,s)[n,s] = ns where (n,s) is what's called d
up above. Taking the last step, [n,s] = (n/d)s from which
it follows that the order of a^s is, in fact, n/d.
[/quote:148aa3df92]
Thanks. But what does "m is the order of a^s in G"?
regards,
Andersen |
|
|
| Back to top |
|
|
|
| Bill Dubuque |
| Posted: Fri Aug 05, 2005 1:44 am |
|
|
|
Guest
|
Andersen <andersen_800@hotmail.com> wrote:
[quote:1d55f21202]
I have Fraleigh's Abstract Algebra book and fail to understand the proof
of the following theorem.
Theorem.
Let G be a cyclic group with n elements and generated by a. Let b\inG
and let b=a^s. Then b generates a cyclic subgroup H of G containing n/d
elements, where d is the GCD of n and s.
Proof.
That b generates a cyclic subgroup H of G is known from Theorem 3.2. We
need show only that H has n/d elements. Following the argument of the
preceding case, you can see that H has as many elements as the smallest
power of b that gives the identity. Now b=a^s and b^m=e if and only if
(a^s)^m=a^(ms)=e, or if and only if n divides ms. What is the smallest
value of m such that n divides ms? *** If d is the largest number
dividing both n and s, then in the expression n=d(n/d), the d factor of
n will divide the s factor of ms. No prime factors of n/d can be
absorbed by s in addition to the factor d, since we chose d as the
largest integer dividing both n and s. Thus all of n/d must be absorbed
in m, so the smallest such m is m=n/d
[/quote:1d55f21202]
It's much more simply expressed in terms of fractions.
We seek the smallest multiple m of the fraction s/n
that makes it integral. This is clearly the denominator
of the fraction in lowest terms (via Euclid's Lemma).
To reduce s/n to lowest terms divide the top and bottom
through by their gcd d := (s,n). What remains as the
denominator of the reduced fraction is n/d which,
as argued above, is the sought value of m.
--Bill Dubuque |
|
|
| Back to top |
|
|
|
| quasi |
| Posted: Fri Aug 05, 2005 3:32 am |
|
|
|
Guest
|
On Fri, 05 Aug 2005 09:31:14 +0200, Andersen
<andersen_800@hotmail.com> wrote:
[quote:a676ea1a54]Ed Hook wrote:
You're right that the proof as presented isn't very
easy to follow -- rather than trying to explain the
author's squishy terminology, let me attempt a different
presentation: if m is the order of a^s in G, then you
know that ms has to be a multiple of n. Since it's clearly
a multiple of s, the order of a^s is a common multiple
of n, s. In fact, it must be the _least_ common multiple
of n, s - denoted [n,s] - since a^[n,s] = e (because
the order of a is n). But one learns early on in number
theory that (n,s)[n,s] = ns where (n,s) is what's called d
up above. Taking the last step, [n,s] = (n/d)s from which
it follows that the order of a^s is, in fact, n/d.
Thanks. But what does "m is the order of a^s in G"?
regards,
Andersen
[/quote:a676ea1a54]
The order of an element x in a group G is the least positive integer m
such that x^m=1.
So the statement "m is the order of a^s in G" means m is the least
positive integer such that (a^s)^m=1. Of course, by the laws of
exponents for groups, (a^s)^m=a^ms.
quasi |
|
|
| Back to top |
|
|
|
| Andersen |
| Posted: Fri Aug 05, 2005 8:15 am |
|
|
|
Guest
|
Ed Hook wrote:
[quote:585784de00]
You're right that the proof as presented isn't very
easy to follow -- rather than trying to explain the
author's squishy terminology, let me attempt a different
presentation: if m is the order of a^s in G, then you
know that ms has to be a multiple of n. Since it's clearly
a multiple of s, the order of a^s is a common multiple
of n, s. In fact, it must be the _least_ common multiple
of n, s - denoted [n,s] - since a^[n,s] = e (because
the order of a is n). But one learns early on in number
theory that (n,s)[n,s] = ns where (n,s) is what's called d
up above. Taking the last step, [n,s] = (n/d)s from which
it follows that the order of a^s is, in fact, n/d.
[/quote:585784de00]
Ok, almost there. What does this mean:
"But one learns early on in number theory that (n,s)[n,s] = ns where
(n,s) is what's called d up above. Taking the last step, [n,s] = (n/d)s
from which it follows that the order of a^s is, in fact, n/d."
What is (n,s)[n,s] = ns. I do not understand the notation (n,s), I know
you introduced [n,s] as the least common multiple of n and s.
regards,
Andersen |
|
|
| Back to top |
|
|
|
| A N Niel |
| Posted: Fri Aug 05, 2005 8:58 am |
|
|
|
Guest
|
[quote:2c42c16be3]
Ok, almost there. What does this mean:
"But one learns early on in number theory that (n,s)[n,s] = ns where
(n,s) is what's called d up above. Taking the last step, [n,s] = (n/d)s
from which it follows that the order of a^s is, in fact, n/d."
What is (n,s)[n,s] = ns. I do not understand the notation (n,s), I know
you introduced [n,s] as the least common multiple of n and s.
[/quote:2c42c16be3]
(n,s) = greatest common divisor of n and s
[n,s] = least common multiple of n and s
their product is the same as the product of n times s, (n,s)[n,s] = ns . |
|
|
| Back to top |
|
|
|
| Ed Hook |
| Posted: Fri Aug 05, 2005 8:59 am |
|
|
|
Guest
|
Andersen wrote:
[quote:4fd87bb7e1]Ed Hook wrote:
You're right that the proof as presented isn't very
easy to follow -- rather than trying to explain the
author's squishy terminology, let me attempt a different
presentation: if m is the order of a^s in G, then you
know that ms has to be a multiple of n. Since it's clearly
a multiple of s, the order of a^s is a common multiple
of n, s. In fact, it must be the _least_ common multiple
of n, s - denoted [n,s] - since a^[n,s] = e (because
the order of a is n). But one learns early on in number
theory that (n,s)[n,s] = ns where (n,s) is what's called d
up above. Taking the last step, [n,s] = (n/d)s from which
it follows that the order of a^s is, in fact, n/d.
Ok, almost there. What does this mean:
"But one learns early on in number theory that (n,s)[n,s] = ns where
(n,s) is what's called d up above. Taking the last step, [n,s] = (n/d)s
from which it follows that the order of a^s is, in fact, n/d."
What is (n,s)[n,s] = ns. I do not understand the notation (n,s), I know
you introduced [n,s] as the least common multiple of n and s.
[/quote:4fd87bb7e1]
OK - '(n,s)' is the standard notation for the greatest common
divisor of n, s. So the result that I'm using is the fact that
the product of the greatest common divisor and the least common
multiple of n and s is equal to ns. (This follows most easily from
the Fundamental Theorem of Arithmetic. Write down the prime
factorizations of n and s:
n = p_1^m_1 p_2^m_2 ... p_k^m_k
s = p_1^r_1 p_2^r_2 ... p_k^r_k
where I've chosen to express both in terms of the _same_ set of
primes -- you can always do this, since p^0 = 1. Then
(n,s) = p_1^min(m_1,r_1) p_2^min(m_2,r_2) ... p_k^min(m_k,r_k)
[n,s] = p_1^max(m_1,r_1) p_2^max(m_2,r_2) ... p_k^max(m_k,r_k)
and
ns = p_1^{m_1+r_1} p_2^{m_2+r_2} ... p_k^{m_k+r_k} .
Since min(a,b) + max(a,b) = a+b, the claim follows.)
What's really going on here: You know that a^n = e _and_ that
a^r = e iff r is a multiple of n (that's what it _means_ to say
that the order of a is n). If, then, m is the order of a^s in G,
a^{ms} = (a^s)^m = e, so you know that ms must be a multiple of
n. SInce ms is obviously a multiple of s, ms is a _common_
multiple of n, s. This leads you to the observation that
a^[n,s] = e and that no _smaller_ multiple of s has this property.
Hence, [n,s]/s _is_ the order of a^s in G. But (by the fact proved
up above) [n,s]/s = n/(n,s) ... which is what you wanted to prove.
Hope some of that helped ... |
|
|
| Back to top |
|
|
|
| Andersen |
| Posted: Fri Aug 05, 2005 10:02 am |
|
|
|
Guest
|
quasi wrote:
[quote:9500d23415]
This is an example of why, in my opinion, you should study some
elementary number theory before studying modern algebra. So many of
the simple concepts relating to primes, divisibility, congruences are
invoked as needed in modern algebra that, without a firm grounding in
these number theory basics, many proofs in modern algebra will seem
mysterious when they are actually quite natural.
[/quote:9500d23415]
You might be right. Nevertheless, I am reading "A First Course in
Abstract Algebra" by John B. Fraleigh (3rd Ed) and I have studied
everything in it, sequentially up to page 60, where I stumbled on this
proof that I did not understand. The book does not say number theory is
required, in fact it says it is self-contained.
regards,
Andersen |
|
|
| Back to top |
|
|
|
| Bill Dubuque |
| Posted: Fri Aug 05, 2005 10:13 am |
|
|
|
Guest
|
Bill Dubuque <wgd@nestle.csail.mit.edu> wrote:
[quote:3c8fbfde46]Andersen <andersen_800@hotmail.com> wrote:
I have Fraleigh's Abstract Algebra book and fail to understand the proof
of the following theorem.
Theorem.
Let G be a cyclic group with n elements and generated by a. Let b\inG
and let b=a^s. Then b generates a cyclic subgroup H of G containing n/d
elements, where d is the GCD of n and s.
Proof.
That b generates a cyclic subgroup H of G is known from Theorem 3.2. We
need show only that H has n/d elements. Following the argument of the
preceding case, you can see that H has as many elements as the smallest
power of b that gives the identity. Now b=a^s and b^m=e if and only if
(a^s)^m=a^(ms)=e, or if and only if n divides ms. What is the smallest
value of m such that n divides ms? *** If d is the largest number
dividing both n and s, then in the expression n=d(n/d), the d factor of
n will divide the s factor of ms. No prime factors of n/d can be
absorbed by s in addition to the factor d, since we chose d as the
largest integer dividing both n and s. Thus all of n/d must be absorbed
in m, so the smallest such m is m=n/d
It's much more simply expressed in terms of fractions.
We seek the smallest multiple m of the fraction s/n
that makes it integral. This is clearly the denominator
of the fraction in lowest terms (via Euclid's Lemma).
To reduce s/n to lowest terms divide the top and bottom
through by their gcd d := (s,n). What remains as the
denominator of the reduced fraction is n/d which,
as argued above, is the sought value of m.
[/quote:3c8fbfde46]
Perhaps I should have emphasized the group-theoretic viewpoint.
Above I chose a specific *concrete* model of the *abstract*
cyclic group of order n, namely the subgroup of Q/Z generated
by the fraction 1/n. Being an additive group, it may be viewed
as a "logarithmic" image of the multiplicative cyclic group.
In particular, powers become multiples with the consequence
that things become *linear*: the power a^s maps to s(1/n)
and the problem reduces to computing the order of s/n (mod 1),
i.e. the smallest natural m such that m(s/n) is an integer.
But this becomes trivial once we reduce s/n to lowest terms.
Say s/n = a/b with a,b coprime. Then ma/b integral implies
b divides ma, but b coprime a, so b divides m by Euclid's Lemma,
and the smallest such m>0 is clearly b, as I claimed before.
Contrast this simple proof with the fumbling proof by Fraleigh.
Notice how the choice of the concrete model has allowed us to
convert the problem to a context where we can apply our wealth
of intuitive knowledge about fractions and their number theory.
--Bill Dubuque |
|
|
| Back to top |
|
|
|
| Andersen |
| Posted: Fri Aug 05, 2005 10:43 am |
|
|
|
Guest
|
Ed Hook wrote:
[quote:217ca694d3]OK - '(n,s)' is the standard notation for the greatest common
divisor of n, s. So the result that I'm using is the fact that
the product of the greatest common divisor and the least common
multiple of n and s is equal to ns. (This follows most easily from
the Fundamental Theorem of Arithmetic. Write down the prime
factorizations of n and s:
n = p_1^m_1 p_2^m_2 ... p_k^m_k
s = p_1^r_1 p_2^r_2 ... p_k^r_k
where I've chosen to express both in terms of the _same_ set of
primes -- you can always do this, since p^0 = 1. Then
(n,s) = p_1^min(m_1,r_1) p_2^min(m_2,r_2) ... p_k^min(m_k,r_k)
[n,s] = p_1^max(m_1,r_1) p_2^max(m_2,r_2) ... p_k^max(m_k,r_k)
and
ns = p_1^{m_1+r_1} p_2^{m_2+r_2} ... p_k^{m_k+r_k} .
Since min(a,b) + max(a,b) = a+b, the claim follows.)
What's really going on here: You know that a^n = e _and_ that
a^r = e iff r is a multiple of n (that's what it _means_ to say
that the order of a is n). If, then, m is the order of a^s in G,
a^{ms} = (a^s)^m = e, so you know that ms must be a multiple of
n. SInce ms is obviously a multiple of s, ms is a _common_
multiple of n, s. This leads you to the observation that
a^[n,s] = e and that no _smaller_ multiple of s has this property.
Hence, [n,s]/s _is_ the order of a^s in G. But (by the fact proved
up above) [n,s]/s = n/(n,s) ... which is what you wanted to prove.
Hope some of that helped ...
[/quote:217ca694d3]
This was excellent. Thank you. I followed all the way through and also
learned some extra tricks. I'll keep in mind that you can view any two
arbitrary numbers as powers of the same set of primes. Also the
algorithm for calculating gcd and lcd based on the factorization was new
to me (though I am sure these are very elementary facts).
best regards,
Andersen |
|
|
| Back to top |
|
|
|
| quasi |
| Posted: Fri Aug 05, 2005 11:32 am |
|
|
|
Guest
|
On Fri, 05 Aug 2005 16:15:52 +0200, Andersen
<andersen_800@hotmail.com> wrote:
[quote:1e8b02c010]Ed Hook wrote:
You're right that the proof as presented isn't very
easy to follow -- rather than trying to explain the
author's squishy terminology, let me attempt a different
presentation: if m is the order of a^s in G, then you
know that ms has to be a multiple of n. Since it's clearly
a multiple of s, the order of a^s is a common multiple
of n, s. In fact, it must be the _least_ common multiple
of n, s - denoted [n,s] - since a^[n,s] = e (because
the order of a is n). But one learns early on in number
theory that (n,s)[n,s] = ns where (n,s) is what's called d
up above. Taking the last step, [n,s] = (n/d)s from which
it follows that the order of a^s is, in fact, n/d.
Ok, almost there. What does this mean:
"But one learns early on in number theory that (n,s)[n,s] = ns where
(n,s) is what's called d up above. Taking the last step, [n,s] = (n/d)s
from which it follows that the order of a^s is, in fact, n/d."
What is (n,s)[n,s] = ns. I do not understand the notation (n,s), I know
you introduced [n,s] as the least common multiple of n and s.
regards,
Andersen
[/quote:1e8b02c010]
This is an example of why, in my opinion, you should study some
elementary number theory before studying modern algebra. So many of
the simple concepts relating to primes, divisibility, congruences are
invoked as needed in modern algebra that, without a firm grounding in
these number theory basics, many proofs in modern algebra will seem
mysterious when they are actually quite natural.
quasi |
|
|
| Back to top |
|
|
|
| quasi |
| Posted: Fri Aug 05, 2005 11:32 am |
|
|
|
Guest
|
On Fri, 05 Aug 2005 18:02:25 +0200, Andersen
<andersen_800@hotmail.com> wrote:
[quote:aa38bbf009]quasi wrote:
This is an example of why, in my opinion, you should study some
elementary number theory before studying modern algebra. So many of
the simple concepts relating to primes, divisibility, congruences are
invoked as needed in modern algebra that, without a firm grounding in
these number theory basics, many proofs in modern algebra will seem
mysterious when they are actually quite natural.
You might be right. Nevertheless, I am reading "A First Course in
Abstract Algebra" by John B. Fraleigh (3rd Ed) and I have studied
everything in it, sequentially up to page 60, where I stumbled on this
proof that I did not understand. The book does not say number theory is
required, in fact it says it is self-contained.
regards,
Andersen
[/quote:aa38bbf009]
Yes, introductory Modern Algebra books try to be self contained in
that way, but they usually don't do enough Number Theory, hence the
student with no prior study of Number Theory typically has
insufficient intuition and confidence when concepts of Number Theory
are brought into play.
You could study Number Theory and Modern Algebra in parallel, nothing
wrong with that. Each enhances the appreciation and understanding of
the other.
quasi |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sun Nov 29, 2009 10:44 am
|
|