Prev: I am Isaac Newton, do I need to always wear a chastity belt all my life?
Next: relativity puzzle
From: Arturo Magidin on 19 Apr 2010 11:05
On Apr 19, 7:31 am, "charlescalculus_robertobag...(a)hotmail.com"
<charlescalculus_robertobag...(a)hotmail.com> wrote:
> Hi,

Please provide quotes to give context to your reply. Not everyone
reads news the same way, and it is often difficult to look back on
previous posts while maintaining a view on the current one. *QUOTE*
enough of the previous post to provide context for your replies.

Your original post began:

>> I know how to show that the number of generators of a cyclic group G, |G| =
>> n is $\phi(n)$, Euler's totient function as follows.

> I have shown that if (r,n) = 1, then a^r is a generator of a group G with
> |G| = n. It is plain that a^n is a generator.

Actually, no. It is plain that it is *not* a generator unless n=1.
Because if |G|=n, then by Lagrange's Theorem it follows that if a is
in G, then a^n=1. And 1 is not the generator of any group except the
trivial group.

> As I have shown this,

You have shown that a^n is a generator? That would be an amazing
result, indeed!


> then it must be that the number of generators is the number of r relatively > prime to n, which is exactly equal to the totient function.

Your argument was:

"Suppose that |G|=n, and let a be a generator. If r is an integer such
that gcd(r,n)=1, then a^r is a generator of G."

I agree with this. This shows that the number of generators is *at
least* phi(n), because for each integer r, gcd(n,r)=1, and 1<= r <= n,
you have a generator, and they are all distinct.

You have *not* shown, in the above, that there are *at most* phi(n)
generators; that is, you have not shown that if a^s is a generator of
G, then s must be relatively prime to n. (Yes, this is also true, and
it's pretty easy, but you have to *prove it*).

So, no. You have not provided a full proof that the number of
generators is *exactly* phi(n), you have only shown that it is *at
least* phi(n). Moreover, there apparently is still some confusion,
since twice now you have asserted that a^n will be a generator of the
group, something which is patently false in all interesting cases.

> My next problem is trying find an alternative method using lagrange's
> theorem to prove that $\phhi(n)$ is the number of generators.

I would suggest that you first complete the proof you have begun.

> This is what i'm trying to find out, which I don't know.

You can use Lagrange's Theorem to show that the number is *at most*
phi(n): if d|n, then n = dk; by Lagrange's Theorem, a^n = 1, so
(a^d)^k = 1. Use this to conclude that the subgroup generated by a^d
cannot be everything.

I think the problem here is that you are not really noticing that your
argument so far is incomplete; you are not trying to find a *new
complete proof* using Lagrange's Theroem, you are trying to *finish
your first proof* using Lagrange's Theorem to establish to other
inequality. You have only established one so far.

--
Arturo Magidin
From: Pubkeybreaker on 19 Apr 2010 12:01
On Apr 19, 11:05 am, Arturo Magidin <magi...(a)member.ams.org> wrote:
> On Apr 19, 7:31 am, "charlescalculus_robertobag...(a)hotmail.com"
>
> <charlescalculus_robertobag...(a)hotmail.com> wrote:
> > Hi,
>
> Please provide quotes to give context to your reply. Not everyone
> reads news the same way, and it is often difficult to look back on
> previous posts while maintaining a view on the current one. *QUOTE*
> enough of the previous post to provide context for your replies.
>
> Your original post began:
>
> >> I know how to show that the number of generators of a cyclic group G, |G| =
> >> n is $\phi(n)$, Euler's totient function as follows.
> > I have shown that if (r,n) = 1, then a^r is a generator of a group G with
> > |G| = n. It is plain that a^n is a generator.
>
> Actually, no. It is plain that it is *not* a generator unless n=1.
> Because if |G|=n, then by Lagrange's Theorem it follows that if a is
> in G, then a^n=1. And 1 is not the generator of any group except the
> trivial group.
>
> > As I have shown this,
>
> You have shown that a^n is a generator? That would be an amazing
> result, indeed!
>
> > then it must be that the number of generators is the number of r relatively > prime to n, which is exactly equal to the totient function.
>
> Your argument was:
>
> "Suppose that |G|=n, and let a be a generator. If r is an integer such
> that gcd(r,n)=1, then a^r is a generator of G."
>
> I agree with this. This shows that the number of generators is *at
> least* phi(n), because for each integer r, gcd(n,r)=1, and 1<= r <= n,
> you have a generator, and they are all distinct.
>
> You have *not* shown, in the above, that there are *at most* phi(n)
> generators; that is, you have not shown that if a^s is a generator of
> G, then s must be relatively prime to n. (Yes, this is also true, and
> it's pretty easy, but you have to *prove it*).
>
> So, no. You have not provided a full proof that the number of
> generators is *exactly* phi(n), you have only shown that it is *at
> least* phi(n). Moreover, there apparently is still some confusion,
> since twice now you have asserted that a^n will be a generator of the
> group, something which is patently false in all interesting cases.
>
> > My next problem is trying find an alternative method using lagrange's
> > theorem to prove that $\phhi(n)$ is the number of generators.
>
> I would suggest that you first complete the proof you have begun.
>
> > This is what i'm trying to find out, which I don't know.
>
> You can use Lagrange's Theorem to show that the number is *at most*
> phi(n): if d|n, then n = dk; by Lagrange's Theorem, a^n = 1, so
> (a^d)^k = 1. Use this to conclude that the subgroup generated by a^d
> cannot be everything.
>
> I think the problem here is that you are not really noticing that your
> argument so far is incomplete; you are not trying to find a *new
> complete proof* using Lagrange's Theroem, you are trying to *finish
> your first proof* using Lagrange's Theorem to establish to other
> inequality. You have only established one so far.

Isn't it easier simply to observe that all cyclic groups of order N
are
isomorphic?

Now, we just map our multiplicative cyclic group of order N to the
ADDITIVE cyclic
group of Z/NZ. We now observe in this latter group that ax = 1 has a
solution
iff (a,N) = 1. Thus, the generators of our additive group are
precisely those
integers for which (a,N) = 1, and there are phi(N) of them.
From: Arturo Magidin on 20 Apr 2010 13:11
On Apr 20, 9:12 am, "charlescalculus_robertobag...(a)hotmail.com"
<charlescalculus_robertobag...(a)hotmail.com> wrote:

PLEASE QUOTE at least parts of the post you are replying to, to
provide context!

You are posting, apparently, from MathForum.After clicking on "Reply",
and before you start writing, click on the button that reads "Quote
original". It's on top of the reply box, on the right of the spell
check button. Then feel free to edit it down to remove stuff that does
not matter (e.g., signatures) and pare it down to its essential, but
please provide *some* context to your reply.

You are trying to prove that the number of generators of a cyclic
group of order n is phi(n). You used Bezout's Theorem to show that if
r is relatively prime to n, then a^r is a generator. You then asserted
that this completed the proof, and asked about an "alternative proof"
using Lagrange's Theorem. I pointed out that you had only shown that
the number of generators was *at least* phi(n), and suggested that
perhaps what you were looking for was a proof of the converse
inequality ("at most phi(n)") using Lagrange's Theorem.

[.edited for grammar.]

> So if I prove the converse, that is if a^r is a generator then (n,r) = 1 then I have that the number of generators equals exactly phi(n)?

Well, yes. If you prove that, then you will show that the number of
generators is at most phi(n); put together with your argument showing
that it is at least phi(n), that gives equality. (Technically, there
is a bit of stuff going on behind the scenes implicitly, to argue that
you only need to concern yourself with values of r that lie between 0
and n, but we are taking that as granted).

--
Arturo Magidin
From: Arturo Magidin on 19 Apr 2010 14:08
On Apr 19, 11:01 am, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
> On Apr 19, 11:05 am, Arturo Magidin <magi...(a)member.ams.org> wrote:
>
>
>
> > On Apr 19, 7:31 am, "charlescalculus_robertobag...(a)hotmail.com"
>
> > <charlescalculus_robertobag...(a)hotmail.com> wrote:
> > > Hi,
>
> > Please provide quotes to give context to your reply. Not everyone
> > reads news the same way, and it is often difficult to look back on
> > previous posts while maintaining a view on the current one. *QUOTE*
> > enough of the previous post to provide context for your replies.
>
> > Your original post began:
>
> > >> I know how to show that the number of generators of a cyclic group G, |G| =
> > >> n is $\phi(n)$, Euler's totient function as follows.
> > > I have shown that if (r,n) = 1, then a^r is a generator of a group G with
> > > |G| = n. It is plain that a^n is a generator.
>
> > Actually, no. It is plain that it is *not* a generator unless n=1.
> > Because if |G|=n, then by Lagrange's Theorem it follows that if a is
> > in G, then a^n=1. And 1 is not the generator of any group except the
> > trivial group.
>
> > > As I have shown this,
>
> > You have shown that a^n is a generator? That would be an amazing
> > result, indeed!
>
> > > then it must be that the number of generators is the number of r relatively > prime to n, which is exactly equal to the totient function.
>
> > Your argument was:
>
> > "Suppose that |G|=n, and let a be a generator. If r is an integer such
> > that gcd(r,n)=1, then a^r is a generator of G."
>
> > I agree with this. This shows that the number of generators is *at
> > least* phi(n), because for each integer r, gcd(n,r)=1, and 1<= r <= n,
> > you have a generator, and they are all distinct.
>
> > You have *not* shown, in the above, that there are *at most* phi(n)
> > generators; that is, you have not shown that if a^s is a generator of
> > G, then s must be relatively prime to n. (Yes, this is also true, and
> > it's pretty easy, but you have to *prove it*).
>
> > So, no. You have not provided a full proof that the number of
> > generators is *exactly* phi(n), you have only shown that it is *at
> > least* phi(n). Moreover, there apparently is still some confusion,
> > since twice now you have asserted that a^n will be a generator of the
> > group, something which is patently false in all interesting cases.
>
> > > My next problem is trying find an alternative method using lagrange's
> > > theorem to prove that $\phhi(n)$ is the number of generators.
>
> > I would suggest that you first complete the proof you have begun.
>
> > > This is what i'm trying to find out, which I don't know.
>
> > You can use Lagrange's Theorem to show that the number is *at most*
> > phi(n): if d|n, then n = dk; by Lagrange's Theorem, a^n = 1, so
> > (a^d)^k = 1. Use this to conclude that the subgroup generated by a^d
> > cannot be everything.
>
> > I think the problem here is that you are not really noticing that your
> > argument so far is incomplete; you are not trying to find a *new
> > complete proof* using Lagrange's Theroem, you are trying to *finish
> > your first proof* using Lagrange's Theorem to establish to other
> > inequality. You have only established one so far.
>
> Isn't it easier simply to observe that all cyclic groups of order N
> are
> isomorphic?
>
> Now, we just map our multiplicative cyclic group of order N to the
> ADDITIVE cyclic
> group of Z/NZ.  We now observe in this latter group that  ax = 1 has a
> solution
> iff (a,N) = 1.

And how do you prove that? If you are able to simply invoke it, then
there is no point in going over to the additive cyclic group: just
start with <a> of order n. Then a^r is a generator if and only if
there exists k such that a=(a^r)^k = a^{rk}, which holds if and only
if 1 = rk (mod n), which exists if and only if rx=1 (mod N) has a
solution, which holds if and only if gcd(r,N)=1. No need to establish
that "all cyclic groups of order N are isomorphic" to the additive
cyclic group explicitly.

But if you are not able to simply invoke this result, then you need to
prove it. That is, you need to show that

ax = 1 (mod N) has a solution if and only if gcd(a,N)=1.

(of course, you cannot invoke that ax=b (mod N) has a solution if and
only if gcd(a,N)|b).

--
Arturo Magidin
First  |  Prev  | 
Pages: 1 2
Prev: I am Isaac Newton, do I need to always wear a chastity belt all my life?
Next: relativity puzzle