Prev: I am Isaac Newton, do I need to always wear a chastity belt all my life?
Next: relativity puzzle
From: charlescalculus_robertobaggio on 18 Apr 2010 01:30
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. Please check these steps: Firstly, let a^n be a generator. Then a^n = e the identity.

Suppose (r,n) = 1. Then by Bezout's theorem there are x and y such that xr + yn = 1 =>

a^xr * a^yn = a^xr = a (As a^n = e, the identity) => a^r is a generator for (r,n) = 1 and the result follows.

How do I show this using lagrange's theorem? Are my steps above correct?
From: Timothy Murphy on 18 Apr 2010 07:23
charlescalculus_robertobaggio(a)hotmail.com wrote:

> 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. Please check these
> steps: Firstly, let a^n be a generator. Then a^n = e the identity.
>
> Suppose (r,n) = 1. Then by Bezout's theorem there are x and y such that xr
> + yn = 1 =>
>
> a^xr * a^yn = a^xr = a (As a^n = e, the identity) => a^r is a generator
> for (r,n) = 1 and the result follows.
>
> How do I show this using lagrange's theorem? Are my steps above correct?

Your argument seems fine to me.

You could also argue as follows.
Suppose the order of a^r is e.
Then a^{re} = 1 => n | re.
Since gcd(n,r) = 1 it follows from the Fundamental Theorem of Arithmetic
(Unique Factorisation in N) that n | e.

Of course one could argue that Bezout's Theorem is used
to prove the Fundamental Theorem,
but there are other ways of proving that.


--
Timothy Murphy
e-mail: gayleard /at/ eircom.net
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
From: Arturo Magidin on 18 Apr 2010 15:12
On Apr 18, 4:30 am, "charlescalculus_robertobag...(a)hotmail.com"
<charlescalculus_robertobag...(a)hotmail.com> wrote:
> 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. Please check these steps: Firstly, let a^n be a generator.

You mean "a", not "a^n".

> Then a^n = e the identity.
>
> Suppose (r,n) = 1. Then by Bezout's theorem there are x and y such that xr + yn = 1 =>
>
> a^xr * a^yn = a^xr = a (As a^n = e, the identity) => a^r is a generator for (r,n) = 1 and the result follows.

Better a = a^{xr+yn} = a^{xr} a^{yn} = a^{xr} = (a^r)^x, which implies
a^r is a generator since a lies in <a^r>. But your argument is of
course correct. You might also want to note that you are restricting
yourself to r that lies in {1,2,3,...,n}.

But you have not shown that the number of generators is exactly
phi(n): you have only shown that it is *at least* phi(n): that is, you
have shown that if r is any integer, 0<r<n, gcd(r,n)=1, then a^r is a
generator. But you have not yet shown that if a^x is a generator, then
x must be relatively prime to n.

> How do I show this using lagrange's theorem? Are my steps above correct?

How do you show what? The step you are missing, or the step you
already did?

--
Arturo Magidin
From: charlescalculus_robertobaggio on 19 Apr 2010 04:31
Hi, 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. As I have shown this, 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.

My next problem is trying find an alternative method using lagrange's theorem to prove that $\phhi(n)$ is the number of generators. This is what i'm trying to find out, which I don't know.
From: charlescalculus_robertobaggio on 20 Apr 2010 06:12
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)?

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