MHB The automorphic group is abelian

[mathmari]

Hey!

I want to show that $\text{Aut}(\mathbb{Z}_n)$ is an abelian group of order $\phi (n)$.

We have that $\mathbb{Z}_n$ is cyclic and it is generated by one element.

Does it have $\phi (n)$ possible generators? (Wondering)

Let $h\in \text{Aut}(\mathbb{Z}_n)$.
Then $h(k)=h(1+1+\dots +1)=h(1)+h(1)+\dots +h(1)=kh(1)$, since $\mathbb{Z}_n$ is cyclic with generator $1$ under the addition and $h$ is an homomorphism.

Since $h(1)\in \mathbb{Z}_n$, let $h(1)=a$, we have the mapping $$k\mapsto ak$$

Do we take two elements $h_1,h_2\in\text{Aut}(\mathbb{Z}_n)$ and show that $$h_1(i)\cdot h_2(j)=h_2(j)\cdot h_1(i)$$ ? (Wondering)

We have $$h_1(i)\cdot h_2(j)=ih_1(1)jh_2(1)$$ How could we continue? (Wondering)

Or do we have to show that this group is isomorphic to an abelian group? (Wondering)

 

[I like Serena]

Do we take two elements $h_1,h_2\in\text{Aut}(\mathbb{Z}_n)$ and show that $$h_1(i)\cdot h_2(j)=h_2(j)\cdot h_1(i)$$ ? (Wondering)

We have $$h_1(i)\cdot h_2(j)=ih_1(1)jh_2(1)$$ How could we continue? (Wondering)

Or do we have to show that this group is isomorphic to an abelian group? (Wondering)

Hey mathmari! (Smile)

Not quite.
The operation in $\text{Aut}(\mathbb{Z}_n)$ is function composition.
So we need to verify if $h_1 \circ h_2=h_2\circ h_1$.
That is, that for any $i \in \mathbb{Z}_n$, we have $h_1(h_2(i)) = h_2(h_1(i))$. (Thinking)

 

[mathmari]

The operation in $\text{Aut}(\mathbb{Z}_n)$ is function composition.
So we need to verify if $h_1 \circ h_2=h_2\circ h_1$.
That is, that for any $i \in \mathbb{Z}_n$, we have $h_1(h_2(i)) = h_2(h_1(i))$. (Thinking)

Ah ok... (Thinking)

So, we have the following:

$$h_1(h_2(i)) =h_1(ih_2(1))=h_1(h_2(1)+h_2(1)+\dots +h_2(1))$$ We add $i$ times $h_2(1)$. Since $h_1$ is an homomorphism, we get $$h_1(h_2(1)+h_2(1)+\dots +h_2(1))=h_1(h_2(1))+h_1(h_2(1))+\dots +h_1(h_2(1))=ih_1(h_2(1))$$

Since $h_2(1)\in \mathbb{Z}_n$ we have that $$h_1(h_2(1))=h_2(1)h_1(1)$$ right? (Wondering)

Therefore, $$h_1(h_2(i))=ih_1(h_2(1))=ih_2(1)h_1(1)$$ Calculating the other part, we get

$$h_2(h_1(i)) =h_2(ih_1(1))=h_2(h_1(1)+h_1(1)+\dots +h_1(1))=h_2(h_1(1))+h_2(h_1(1))+\dots +h_2(h_1(1))=ih_2(h_1(1))=ih_1(1)h_2(1)$$ Is everything correct so far? (Wondering) Does it stand that $h_2(1)h_1(1)=h_1(1)h_2(1)$ ? (Wondering)

 

[I like Serena]

$$h_2(h_1(i)) =h_2(ih_1(1))=h_2(h_1(1)+h_1(1)+\dots +h_1(1))=h_2(h_1(1))+h_2(h_1(1))+\dots +h_2(h_1(1))=ih_2(h_1(1))=ih_1(1)h_2(1)$$ Is everything correct so far? (Wondering)

Yes.
Note that it suffices to verify what happens to the generator(s). (Thinking)

Does it stand that $h_2(1)h_1(1)=h_1(1)h_2(1)$ ? (Wondering)

Yes, since we're talking about regular multiplication, which is abelian. (Nod)

 

[mathmari]

Yes.
Note that it suffices to verify what happens to the generator(s). (Thinking)

When $i$ is a generator then $h_1(i)$ and $h_2(i)$ are also generators, right? (Wondering)

To do the above we suppose $i$ to be a generator, right? (Wondering)

Yes, since we're talking about regular multiplication, which is abelian. (Nod)

What do you mean by "regular multiplication" ? (Wondering)

 

[johng1]

Maybe the following will help. What you are trying to do is show that $Aut(Z_n)$ is isomorphic to $Z_n^{\ast}$, the multiplicative group of integers that are prime to n. This latter group is obviously abelian of order $\phi(n)$. So define $$f:Aut(Z_n)\rightarrow Z_n^{\ast}\text{ by }\,\forall h\in Aut(Z_n),\,\, f(h)\equiv h(1)\pmod{n}$$
It's pretty straight forward to show that f is indeed an isomorphism.

 

[Deveno]

Something that make prove to be of general use, here, is the following fact:

If $G = \langle a\rangle$ is a cyclic group of order $n$, then the order of $a^k$ (and thus the order of $\langle a^k \rangle$ as a subgroup of $G$) is:

$|a^k| = \dfrac{n}{\gcd(k,n)}$.

From which it is easy to see that $|a^k| = n \iff \gcd(k,n) = 1$.

I urge you to try to prove this basic result.

(For cyclic groups written additively as $\Bbb Z_n$, this becomes (using $a = 1$):

$|k| = \dfrac{n}{\gcd(k,n)}$, where $|k|$ is the least positive integer $t$ such that $kt = 0$ (mod $n$)).

For example, in $\Bbb Z_{24}$ we have:

$|16| = \dfrac{24}{\gcd(16,24)} = \dfrac{24}{8} = 3$, and in fact:

$16 \neq 0$ (mod 24)
$32 = 8 \neq 0$ (mod 24) (so the order of 16 is not 2)
$48 = 24 + 24 = 0 + 0 = 0$ (mod 24), so the order of 16 is indeed 3.

 

[mathmari]

If $G = \langle a\rangle$ is a cyclic group of order $n$, then the order of $a^k$ (and thus the order of $\langle a^k \rangle$ as a subgroup of $G$) is:

$|a^k| = \dfrac{n}{\gcd(k,n)}$.

I urge you to try to prove this basic result.

We have that $G=\langle a\rangle$ is a cyclic group of order $n$. That means that $a^n=e_G$.

Suppose that the order of $a^k$ is $m$. That means that $(a^k)^m=e_G \Rightarrow a^{km}=e_G$.

By Lagrange's theorem, we have that the order of a subroup divides the order of the group, so $m\mid n$.

How could we continue? (Wondering)

We have that $\mathbb{Z}_n$ is a cyclic group of order $n$.
I got stuck right now... How do we use the above formula to show that the order of $\text{Aut}(\mathbb{Z}_n)$ is $\phi (n)$ ? (Wondering)

 

[Deveno]

You'll have to be a bit clever.

You know that $m = \dfrac{n}{d}$ for some $d$. Good, that's a start.

But you haven't used any properties of the gcd, yet.

 

[mathmari]

We have that $G=\langle a\rangle$ is a cyclic group of order $n$. That means that $a^n=1$.

We have that $\gcd (k,n)$ divides $k$, so $\frac{k}{\gcd (k,n)}$ is an integer. So, $n$ divides $\frac{kn}{\gcd (k,n)}$.

Since $a^n=1$ and $n$ divides $\frac{kn}{\gcd (k,n)}$, we have that $a^{\frac{kn}{\gcd (k,n)}}=1 \Rightarrow (a^k)^{\frac{n}{\gcd (k,n)}}=1$.

To show that $\frac{n}{\gcd (k,n)}$ is the order of $a^k$, we have to show that there is no $x<\frac{n}{\gcd (k,n)}$ such that $(a^k)^x=1$.

Suppose there is such a $x<\frac{n}{\gcd (k,n)}$ such that $(a^k)^x=1$.

Then $(a^k)^x=1 \Rightarrow a^{kx}=1$.

$n$ must divide $kx$, that means that $\exists s\in \mathbb{Z} : kx=ns$.

Dividing the last equation by $\gcd (k,n)$ we get $$\frac{k}{\gcd (k,n)} x=\frac{n}{\gcd (k,n)}s$$
We have that $$\frac{n}{\gcd (k,n)}\mid \frac{n}{\gcd (k,n)}s \Rightarrow \frac{n}{\gcd (k,n)}\mid \frac{k}{\gcd (k,n)} x$$

We have that $\gcd \left (\frac{n}{\gcd (k,n)}, \frac{k}{\gcd (k,n)}\right )=1$, so it implies that $$\frac{n}{\gcd (k,n)}\mid x \Rightarrow \frac{n}{\gcd (k,n)}\leq x$$ That is a contradiction.

Therefore, $\frac{n}{\gcd (k,n)}$ is the smallest integer such that $(a^k)^{\frac{n}{\gcd (k,n)}}=1$.

Therefore, the order of $a^k$ is $\frac{n}{\gcd (k,n)}$.

Is this correct? (Wondering)

 

[mathmari]

The generators of $\mathbb{Z}_n$ are the elements of $\mathbb{Z}_n$ that have order $n$.

From the formula $$|k| = \dfrac{n}{\gcd(k,n)}$$ we have that an element $k$ of $\mathbb{Z}_n$ has order $n$ iff $\gcd(k,n)=1$.

There are $\phi (n)$ such elements.

Therefore, there are $\phi (n)$ generators of $\mathbb{Z}_n$, so the order of $\text{Aut}(\mathbb{Z}_n)$ is $\phi (n)$, right? (Wondering)

If $G = \langle a\rangle$ is a cyclic group of order $n$, then the order of $a^k$ (and thus the order of $\langle a^k \rangle$ as a subgroup of $G$) is:

$|a^k| = \dfrac{n}{\gcd(k,n)}$.

From which it is easy to see that $|a^k| = n \iff \gcd(k,n) = 1$.

I urge you to try to prove this basic result.

(For cyclic groups written additively as $\Bbb Z_n$, this becomes (using $a = 1$):

$|k| = \dfrac{n}{\gcd(k,n)}$, where $|k|$ is the least positive integer $t$ such that $kt = 0$ (mod $n$)).

Do we get the formula $|k| = \dfrac{n}{\gcd(k,n)}$ using as a generator of $\mathbb{Z}_n$ the element $1$ ? (Wondering)

 

[Deveno]

The generators of $\mathbb{Z}_n$ are the elements of $\mathbb{Z}_n$ that have order $n$.

From the formula $$|k| = \dfrac{n}{\gcd(k,n)}$$ we have that an element $k$ of $\mathbb{Z}_n$ has order $n$ iff $\gcd(k,n)=1$.

There are $\phi (n)$ such elements.

Therefore, there are $\phi (n)$ generators of $\mathbb{Z}_n$, so the order of $\text{Aut}(\mathbb{Z}_n)$ is $\phi (n)$, right? (Wondering)
Do we get the formula $|k| = \dfrac{n}{\gcd(k,n)}$ using as a generator of $\mathbb{Z}_n$ the element $1$ ? (Wondering)

Yes, since $k = k\cdot 1$.

 

[mathmari]

Ah ok... Thank you very much! (Mmm)

- - - Updated - - -

Yes, since we're talking about regular multiplication, which is abelian. (Nod)

Do you mean that since $h_1(1), h_2(1)\in \mathbb{Z}_n$ and $\mathbb{Z}_n$ is abelian we have that $$h_1(1)h_2(1)=h_2(1)h_1(1)$$ ? (Wondering)

 

[Deveno]

We have that $G=\langle a\rangle$ is a cyclic group of order $n$. That means that $a^n=1$.

We have that $\gcd (k,n)$ divides $k$, so $\frac{k}{\gcd (k,n)}$ is an integer. So, $n$ divides $\frac{kn}{\gcd (k,n)}$.

Since $a^n=1$ and $n$ divides $\frac{kn}{\gcd (k,n)}$, we have that $a^{\frac{kn}{\gcd (k,n)}}=1 \Rightarrow (a^k)^{\frac{n}{\gcd (k,n)}}=1$.

To show that $\frac{n}{\gcd (k,n)}$ is the order of $a^k$, we have to show that there is no $x<\frac{n}{\gcd (k,n)}$ such that $(a^k)^x=1$.

Suppose there is such a $x<\frac{n}{\gcd (k,n)}$ such that $(a^k)^x=1$.

Then $(a^k)^x=1 \Rightarrow a^{kx}=1$.

$n$ must divide $kx$, that means that $\exists s\in \mathbb{Z} : kx=ns$.

Dividing the last equation by $\gcd (k,n)$ we get $$\frac{k}{\gcd (k,n)} x=\frac{n}{\gcd (k,n)}s$$
We have that $$\frac{n}{\gcd (k,n)}\mid \frac{n}{\gcd (k,n)}s \Rightarrow \frac{n}{\gcd (k,n)}\mid \frac{k}{\gcd (k,n)} x$$

We have that $\gcd \left (\frac{n}{\gcd (k,n)}, \frac{k}{\gcd (k,n)}\right )=1$, so it implies that $$\frac{n}{\gcd (k,n)}\mid x \Rightarrow \frac{n}{\gcd (k,n)}\leq x$$ That is a contradiction.

Therefore, $\frac{n}{\gcd (k,n)}$ is the smallest integer such that $(a^k)^{\frac{n}{\gcd (k,n)}}=1$.

Therefore, the order of $a^k$ is $\frac{n}{\gcd (k,n)}$.

Is this correct? (Wondering)

Seems legit :P

 

[mathmari]

Thank you very much for your help! (Smile)